0%

算法：快排遇到的坑

Posted on Edited on In Valine:

前几天在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所对应的数已经被交换了，自然得不出正确结果。

被坑了一个多钟，好蠢啊我