前几天在LeetCode做题，遇到要排序，于是很自然地手写了个快排，然后无论怎样都
得不到想要的结果，检查了其他部分没问题后开始怀疑排序写错了，但是查了好久也没查出个所以然，甚至各种画流程图，最后去讨教大神，还争论了挺久，才了解自己错在哪，在此记录一下
这是我写的快排；
这样的写法得出结果是错的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public static void sort(int[] a,int low,int high){
int start = low;
int end = high;
int p = low；
while(end>start){
while(end>start&&a[end]>=a[p])
end--;
if(a[end]<=a[p]){
int temp = a[end];
a[end] = a[start];
a[start] = temp;
}
start++;
if(a[start]>=a[p]){
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
}
if(start>low) sort(a,low,start-1);
if(end<high) sort(a,end+1,high);
}
|
这是正确写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public static void sort(int[] a,int low,int high){
int start = low;
int end = high;
int p = low;
int key = a[p];
while(end>start){
while(end>start&&a[end]>=key)
end--;
if(a[end]<=key){
int temp = a[end];
a[end] = a[start];
a[start] = temp;
}
while(end>start&&a[start]<=key)
start++;
if(a[start]>=key){
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
}
if(start>low) sort(a,low,start-1);
if(end<high) sort(a,end+1,high);
}
|
看出区别了吗
对，正确做法应该是要把a[p]即待排序的值赋给一个变量key而不能在循环里直接使用，即作为比较基准的那个数应该在一次执行中是保持不变的，但是如果直接使用a[p]来表示这个基准的话，因为if函数里执行了交换，虽然我们p位置没有改变，但p所对应的数已经被交换了，自然得不出正确结果。
被坑了一个多钟，好蠢啊我