排序 - 交换排序 [2 -- 快速排序]

雨点打透心脏的1/2处 2022-01-12 15:59 244阅读 0赞

“傻文，如果你也跟我一样没有耐性，看我的文章吧，专为没有耐性的朋友准备”

研究了几天这个快速排序的算法，可能我比较笨，断断续续加起来估计超过5个小时的时间了。

因为我很没有耐性，所以总是看一点忘一点。

从我本身来说 我觉得这个算法的逻辑性还是很强的，阅读时真的需要保持清醒，因为我不确定我能说的足够清楚让大家一次明白。

好，我准备先讲一下快速排序的算法描述。

其实快速排序和冒泡排序属于同一大类：交换排序中，主要思想都是把一个大数和一个小数交换位置，以这种方法来使数组逐渐有序。

今天我们待排序的数组是 \{6,8,4,3,5,9,11,7\}

在排序之前我先说下大致思路：

1. 选择一个数字作为支点；

2. 把小于支点的放到支点的左面，大于支点的放到右面；

3. 分别对支点的左右两部分，再对每一部分分别做\#1和\#2。那什么时候结束呢？我们试着讨论一下。

下面我具体说说到底这个算法是如何执行的。

我还是想打断一下，因为第一步是选择一个“支点”, 这个支点的选择通常有3种方法：

1. 第一个元素

2. 中间的元素

3. 最后一个元素

我们讨论前两种，算法大同小异，只是执行过程还是有细微的不同。

好吧开始，我们选择第一个元素作为支点。

我们会分几趟来完成整个排序，第一趟的目标是把数组以支点为中心，左右两边分开。是这样的：

1. 支点选择为6；

2. 我们会从左右两边同时开始比较；

3. 比较最右面的元素，7,  7 大于 6，故他理所当然应该在右面，没有问题；

4. 继续从右面往左走，11 也大于 6，不用理会；

5. 9 大于 6，继续；

6. 5, 5 大于 6吗？否，故，停下来，我们需要记住这个**右位置**的元素 ：5；

7. 这时我们再从左面开始，因为我们选择了6作为支点，这个元素我们不考虑，直接看他下一个元素：8；

8. 8 小于 6吗？（注意，这里的条件变成了小于，前面是大于！原因很简单，左面的应该比支点小，右面的应该比支点大）否，故停下来，我们也记住这个**左位置**的元素： 8！

9. 两边都停下来了，这时怎么办？交换！

10. 好的，在停下来的地方，我们交换他们，左面的 8  和 右面的 5 进行交换，交换后数组变为：\{6,5,4,3,8,9,11,7\}；

11. 不要太高兴，这一趟还没完呢，我们要继续从刚才右位置开始往左走，这个很简单了，下一个元素是 3, 3 大于 6吗？否，故再次停下来；

12. 从左面继续，左位置下一个元素是4, 4 小于 6吗？是的，继续；

13. 下一个元素是3, 3 小于 6 吗？是的，... 咦？刚才我们不是已经比较过3跟6的关系了吗？“嗯，是的，在第\#11步的时候，我们比较过，但是因为 3 大于 6不成立，我们停了下来。”;

14. 对！这就是我们这一趟排序停止的一个条件：从左右两边同时往中间走，在某个位置“碰头”了（左位置已经等于右位置 或者 左位置已经大于右位置，这两种都算碰头吧），这时我们就可以停下来这一趟排序了；

15. 但我们需要做一件事情，那就是把支点跟这个停下来的位置做交换，交换后我们得到的数组为\{3,5,4,6,8,9,11,7\}。

停下来观察一下，我们选择了 6 为支点，此时左面为 3， 5， 4； 右面为 8， 9， 11， 7

很明显，左面 < 支点 < 右面，这个关系成立了。

我们离目标近了一步！

下面呢，分别对左右两部分再进行上面的步骤。

先说左面吧：

我们要排序的数组为： 3,5,4

我们还选择第一个元素：3 作为支点。

1. 从右面开始，4 大于 3吗？是的，继续；

2, 5 大于 3 吗？是的，继续；

3, 3 大于 3 吗？否，停下来（我们说这种情况的停位置在元素： 3，下面会再提到“停位置”）；

4. 从左面开始，5 大于 3 ？。。。 啊哦！左位置（此时指向元素5）已经大于右位置（此时指向元素3）了，这一趟又停了。

5. 所以我们得到了：3,5,4, 支点右面的元素 5， 4 都是大于支点的，而左面没有元素了，所以我们只需要考虑右面部分的排序就行了；

继续对右面部分 5， 4 进行排序：

1. 选择5作为支点；

2. 从右面开始往左走，4大于5吗？否，停下来（我们说这个停位置在：4，下面还会提到“停位置”）；

3. 从左面往右走，4？噢！又碰头了，这一趟又结束了；

4. 我们将支点跟停下来的位置进行交换，得到 4, 5

所以整个左面部分就排序完成了：3, 4, 5。

停！

我想你一定不满意了，你会说：你好像没有说清楚什么时候交换什么时候不交换啊！

是的！

你注意到这一点了，很好！

分两种情况：

一种情况是：

尚未碰头的时候，从右往左遍历时发现了有比支点小的值，而从左往右遍历时发现了有比支点大的值，而此时还没有碰头，是一定要交换的！

另一种情况：

我们在对整个数组做一趟快速排序的时候，我们在最后做了支点和停位置（6 和 3 交换了）元素的交换；

在对左面部分做快速排序时，我们没有对支点和停位置（3 和 3 没有交换），呵呵 也不需要交换对吧，因为他们指向了同一个元素；

在最后一趟快速排序的时候，也做了支点和停位置（5 和 4 交换了）的交换。

嗯？有什么规律吗？

其实这个规律不太容易被发现，但稍微悉心就能看到：如果从右位置停下来的时候跟支点重合，那就不做交换，如果停下来的位置还没到支点位置，那就交换。

再回头看看，是不是呢？

对右面部分8， 9， 11， 7的排序我就不啰嗦了，想必你一定很清楚了。

我们来说说Java算法实现吧！

public class QuickSort {
    
      public static void quickSort(int[] sort, int start, int end) {
        // 这个条件很容易理解吧，当只有一个元素的时候 start == end, 
        // 而我们知道 一个元素的数组就是有序的不需要排序
        if (end > start) {
          // 找到支点，一分为二
          int p = partition(sort, start, end);
          // 快排左半部分
          quickSort(sort, start, p - 1);
          // 快排右半部分
          quickSort(sort, p + 1, end);
        }
      }
      
      /**
       * 找到分割点
       * @return
       */
      public static int partition(int[] sort, int start, int end) {
        int p = start;
        int pValue = sort[p];
        
        int left = start;
        int right = end + 1;
        for (;;) {
          // 从右面往左走，直到某个值小于或等于支点停止
          while (sort [--right] > pValue) {
            if (right <= left) break;
          }
          
          // 从左面往右走，直到某个值大于或等于支点停止
          while (sort[++left] < pValue ) {
            if (left >= right) break;
          }
          
          // 左位置大于等于右位置说明已经碰头了
          // 如果还没有碰头，
          //从右往左遍历时发现了有比支点小的值，
          // 而从左往右遍历时发现了有比支点大的值，而此时还没有碰头，是一定要交换的！
          if (left >= right) 
            break;
          else 
            // 没碰头时的交换
            swap(sort, left, right);
        }
        
        // 如果右面的停位置等于支点位置，则不交换
        if (right == p) {
          return right;
        }
        else {
          // 右面的停位置不等于支点位置，则需要交换
          swap(sort, p, right);
          return right;
        }
      }
      
      // 交换
      private static void swap(int[] sort, int left, int right) {
        int tmp = 0;
        tmp = sort[left];
        sort[left] = sort[right];
        sort[right] = tmp;
      }
    
      // For test
      public static void main(String[] args) {
        int[] sort = {6,8,4,3,5,9,11,7};
        quickSort(sort, 0, sort.length - 1);
        for (int i : sort) {
          System.out.print(i + ", ");
        }
      }
    
    }

复杂度：

时间复杂度：O(n*logn)

空间复杂度：O(1)

在下一篇中，我们继续讨论下，如果选择数组的中间元素为支点，是怎么样的情况。