排序 - 交换排序 [3 -- 快速排序，中间元素为支点]

快来打我* 2022-01-10 10:55 250阅读 0赞

**开始前，送一句话给自己：不要等朋友们都成功了，才想起自己需要努力。**

上次我们讲了快速排序的大致思想以及选择第一个元素作为支点来进行快速排序的具体步骤和算法实现，今天我们讲如果选择了中间的元素作为支点是什么情况。

待排序数组：\{8, 4, 6, 5, 9, 11, 7\}

数组下标从0到6.

(0 + 6) / 2 = 3, 那么支点的下标为3，对应的元素为5.

有了上节的思想这个我就不说那么多废话了。步骤如下：

1. 支点为5；另外，我们强调下，这里我们对数组从下标 0 开始 到下标 6 结束进行快速排序；

2. 从左右两边开始比较，我们先讨论右面部分，7 大于 5， 过；11 大于 5， 过； 9 大于 5； 过；5 不大于 5，停！右停元素为5，下标为3；

3. 从左面开始，8 不小于 5，停下来！左停元素为8，下标为0；

4. 左停元素（下标为 0） 小于 右停元素（下标为 3），则交换，交换后数组变为：\{ **5,** 4, 6,**8,** 9, 11, 7\}，此时做另外一个操作：左停元素下标++（++后结果为1），右停元素下标--（--后结果为2）；

5. 继续从右停元素开始同支点比较大小；

6. 右停元素下标此时为2，即值为6的元素，6 大于 5，过；下一个是4, 4 不大于 5，停！右停元素为4，下标为 1；

7. 左停元素下标此时为1，即值为4的元素，4 小于 5，过；下一个是6, 6 不小于 5，停！左停元素为6，下标为 2；

8. 此时左停元素下标 （2）大于 右停元素下标（1），故第一趟快速排序完成，此时，记下来左停元素下标为 2，和右停元素下标为 1。

9. 此时数组为 \{5,4,6,8,9,11,7\}

等等！你会想：你不是说选择支点后，每一趟排序都会以支点为轴，得到 左面 < 支点 < 右面 的序列吗？怎么这个不符合？！

是的，这就是我想说的选择了中间元素作为支点同选择第一个元素作为支点的不同之处（更恰当的说，是与我上篇文章中所述算法不同）。

在上篇文章中我们选择了首位元素作为支点，每一趟排序后我们都可以得到以支点为中心的左右两部分，而在这而发生了些许不同。

那如何处理呢？

因为我们第一趟快速排序的起始下标为 0 ，而这个下标呢，他小于了第一趟快排后的 右停元素 1.

那么我们需要对数组从下标 0 开始到下标 1 结束进行递归的快速排序。

那么很明显，这时候要排序的数组为 \{5，4\}, 就是 \#9 中所指数组的前两个元素（下标分别为0 和 1）。

这个如何进行快速排序呢？待排序数组 \{5, 4\}.

支点选择：(0 + 1) / 2 = 0.

1. 支点为5。 我们对数组从下标0 开始到 下标 1 结束，进行快速排序；

2. 从左右两面进行比较，先从右面开始，4 不大于 5，停下！右停元素为 4，下标为 1；

3. 从左面开始，5 不小于 5，停！左停元素为 5，下标为 0；

4. 左停元素下标 0 小于 右停元素下标 1，交换！交换后数组变为 \{4, 5\}，同时，左停元素下标++（++后结果为1），右停元素--（--后结果为0）；

5. 此时左停元素下标 1 大于 右停元素下标 0 了，故停止；

6. 此时数组为\{4,5\}

那么，我们再看下这个时候我们还需要再进行递归吗？

需要进行递归的条件是：开始下标 < 上次结束时的右停元素下标；

而我们当前的状况是，开始下标为0，右停元素下标为0,0 不小于 0，故无需进行再次递归。

对第一趟快排的右面部分我就不详细说了，右面部分是\{6,8,9,11,7\}。

好了，我们来说下他的算法实现吧：

/**
       * Quick sort helper method and implement quick sort
       * 
       * @param array the array to sort
       * @param sorting start start index of the array
       * @param end sorting end index of array
       */
      public static void quickSort(int[] array, int start, int end) {
        
        // Select a pivot, we use the middle element value. Other options
        // can be used.
        int pivot = array[(start + end) / 2];
        
        // Use two scan pointers
        int leftIndex = start;
        int rightIndex = end;
        
        // Swap to make larger at right and smaller at left
        while (leftIndex <= rightIndex) {
          
          // Skip those larger ones at right side because they are in correct position
          while (array[rightIndex] > pivot) {
            rightIndex--;
          }
          
          // Skip those smaller ones at left side because they are in correct position
          while (array[leftIndex] < pivot) {
            leftIndex++;
          }
          
          // Swap
          if (leftIndex <= rightIndex) {
            int temp = array[leftIndex];
            array[leftIndex] = array[rightIndex];
            array[rightIndex] = temp;
            leftIndex++;
            rightIndex--;
          }
        }
        
        // Recursively sort left side and right side, at this time, leftIndex
        // is already on the right side of rightIndex
        if (start < rightIndex) {
          quickSort(array, start, rightIndex);
        }
        
        if (leftIndex < end) {
          quickSort(array, leftIndex, end);
        }
      }

如果我没有讲清楚，或者你没有看清楚，请留言。

下次准备说说选择排序的改进算法：堆排序。

Good night.