subject_59845.htm

vc

<p>
序号：59845 发表者：安妮 发表日期：2003-11-10 17:39:46
<br>主题：关于快速排序
<br>内容：我的这个排序结果不太正确，请高手们帮忙指正。<BR># include&lt;iostream.h&gt;<BR><BR>void swap(int &amp;a,int &amp;b)<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;int temp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;temp = a;<BR>&nbsp;&nbsp;&nbsp;&nbsp;a&nbsp;&nbsp;&nbsp;&nbsp;= b;<BR>&nbsp;&nbsp;&nbsp;&nbsp;b&nbsp;&nbsp;&nbsp;&nbsp;= temp;<BR>}<BR><BR>void QuickSort(int a[],int low,int high)<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;//存放中心索引及其值的局部变量及用于扫描的索引<BR>&nbsp;&nbsp;&nbsp;&nbsp;int pivot;<BR>&nbsp;&nbsp;&nbsp;&nbsp;int scanUp,scanDown;<BR>&nbsp;&nbsp;&nbsp;&nbsp;int mid;<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;//若元素个数小于2个，则返回<BR>&nbsp;&nbsp;&nbsp;&nbsp;if(high - low &lt;= 0)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return;<BR>&nbsp;&nbsp;&nbsp;&nbsp;else<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//若子表有2个元素，对其进行比较，并在必要时进行交换<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(high - low == 1)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(a[high] &lt; a[low])<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;swap(a[low],a[high]);<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;//取中心索引，并将其值赋给pivot<BR>&nbsp;&nbsp;&nbsp;&nbsp;mid = (low + high)/2;<BR>&nbsp;&nbsp;&nbsp;&nbsp;pivot = a[mid];<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;//交换pivot及第端元素的值并初始化扫描索引scanUp和scanDown<BR>&nbsp;&nbsp;&nbsp;&nbsp;swap(a[mid],a[low]);<BR>&nbsp;&nbsp;&nbsp;&nbsp;scanUp = low + 1;<BR>&nbsp;&nbsp;&nbsp;&nbsp;scanDown = high;<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;//定位错位元素；当scanDown &lt; scanUp时结束<BR>&nbsp;&nbsp;&nbsp;&nbsp;do<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//从低端子表往上扫描，当scanUp进入高端子表时或遇到大于pivot的元素时结束<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while(scanUp &lt;= scanDown &amp;&amp; a[scanUp] &lt;= pivot)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanUp++;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//从高端子表往下扫描，当scanDown指向的元素小于或等于pivot时停止<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while(pivot &lt; a[scanDown])<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanDown--;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//若两个索引还在各自的子表中，则表示2个元素错位，将2个元素换位<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(scanUp &lt; scanDown)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;swap(a[scanUp],a[scanDown]);<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;while(scanUp &lt; scanDown);<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;//将pivot拷贝到scanDown位置，分开2个子表<BR>&nbsp;&nbsp;&nbsp;&nbsp;a[low] = a[scanDown];<BR>&nbsp;&nbsp;&nbsp;&nbsp;a[scanDown] = pivot;<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;//若低端子表(low至scanDown－1)有2个或以上元素，则进行递归调用<BR>&nbsp;&nbsp;&nbsp;&nbsp;if(low &lt; scanDown - 1)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;QuickSort(a, low, scanDown - 1);<BR>&nbsp;&nbsp;&nbsp;&nbsp;//若高端子表(scanDown＋1至high)有2个或以上元素，则进行递归调用<BR>&nbsp;&nbsp;&nbsp;&nbsp;if(scanUp +1 &lt; high)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;QuickSort(a, scanUp + 1, high);<BR><BR>}<BR><BR><BR><BR>void main()<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;int a[5] = {6,4,3,2,0};<BR>&nbsp;&nbsp;&nbsp;&nbsp;QuickSort(a, 0, 4);<BR>&nbsp;&nbsp;&nbsp;&nbsp;for(int i=0; i&lt;=4;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&lt;&lt;a[i]&lt;&lt;&#34; &#34;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;cout&lt;&lt;endl;<BR>}
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
回复者：ljl 回复日期：2003-11-11 11:46:44
<br>内容：我看了半天也有点晕菜：）<BR><BR>你看看这里吧<BR><BR>http://www.vchelp.net/cndevforum/subject_view.asp?subject_id=17363&amp;forum_id=47<BR><BR>或者到这里搜一搜<BR><BR>http://expert.csdn.net/expert/forum.asp
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：安妮 回复日期：2003-11-11 13:27:04
<br>内容：谢了，好开心罗，第一次留言，这么快就有人回，谢谢大家的支持，给我不少鼓励！
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：安妮 回复日期：2003-11-11 13:56:13
<br>内容：也！看了上面的链接，我就把程序改好了，喜悦，再次谢谢这位热心肠的ljl！
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：ljl 回复日期：2003-11-11 14:03:36
<br>内容：那就给分吧：））<BR>我还“不小心”给你送了一门勋章（本来是想查询，写错了地方，还好，不是飞刀：））
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：安妮 回复日期：2003-11-12 09:32:24
<br>内容：呵呵，好啊！我点了将此回复作为正确答案，是不是就给你加分了。我还不是很清楚，见笑了。
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：安妮 回复日期：2003-11-12 10:00:37
<br>内容：我也不小心给了你一枚勋章，呵呵。
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>