首页 > 代码库 > 转：快速排序的一个小问题没想明白，求助各位
转：快速排序的一个小问题没想明白，求助各位
转自：http://bbs.csdn.net/topics/390797415
提问如下：
1 void QuickSort(int a[],int left,int right) 2 { 3 if(left > right) return ; 4 int i = left, j = right, temp = a[left]; 5 while(i != j) 6 { 7 while(i < j && a[j] >= temp) j--; //注意这两个while 8 while(i < j && a[i] <= temp) i++; //注意这两个while 9 10 if(i < j)11 {12 int t = a[i];13 a[i] = a[j];14 a[j] = t;15 }16 17 }18 a[left] = a[i];19 a[i] = temp;20 21 QuickSort(a,left,i-1);22 QuickSort(a,i+1,right);23 }
我开始写的时候是先i++后j--，但是这样出来的结果不对，而先j--后i++就没问题，结果是对的，但是我不明白是为啥，谁能给说一下，谢谢
回答：
（题外话：代码功能归根结底不是别人帮自己看或讲解或注释出来的；而是被自己静下心来花足够长的时间和精力亲自动手单步或设断点或对执行到某步获得的中间结果显示或写到日志文件中一步一步分析出来的。提醒：再牛×的老师也无法代替学生自己领悟和上厕所！单步调试和设断点调试是程序员必须掌握的技能之一。）
支点是 a[left]，即左边第一个数。
最终结果是：i左边的都比支点小，右边的比它大。
1.先--j,后++i，则因为++i 时保证了i<j，故如果j<=i 时，i不再变动。
2.反之，先++i，则可能因为if(i < j)不成立，于是下面swap不执行，导致 i 并不满足最终结果。
eg: 4 8 1 5 7
1. a). temp = 4, j = 2, i = 1, a[i] = 8, a[j] = 1; -> 4 1 8 5 7
b). j = 1, i = 1; ->结束
2. a). i = 1, j =2, a[i] = 8, a[j] = 1; -> 4 1 8 5 7
b). i = 2, j = 2; ->结束 这样交换的支点就不对了(8)
总结：之前我好像也犯过这个错误。修正后的代码如下。
1 #include "stdafx.h" 2 #include <iostream> 3 void Swap(int &a, int &b) 4 { 5 int temp = a; 6 a = b; 7 b = temp; 8 } 9 10 int Partition(int a[], int l, int r)11 {12 int i = l, j = r, pivot = a[l];13 while(i < j)14 {15 while(i < j && a[j] >= pivot) --j;16 while(i < j && a[i] <= pivot) ++i; 17 Swap(a[i], a[j]);18 } 19 Swap(a[l], a[i]);20 return i;21 }22 23 void QuickSort(int a[], int l, int r)24 {25 if(l >= r) return;26 int s = Partition(a, l, r);27 QuickSort(a, l, s - 1);28 QuickSort(a, s + 1, r);29 }30 31 int _tmain(int argc, _TCHAR* argv[])32 {33 int a[] = {4,8,3,7,1,5,6,2};34 QuickSort(a, 0, sizeof(a)/sizeof(int) - 1);35 36 int b[] = {5,3,1,9,8,2,4,7};37 QuickSort(b, 0, sizeof(b)/sizeof(int) - 1);38 39 system("pause");40 return 0;41 }
转：快速排序的一个小问题没想明白，求助各位
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。