排序算法

快速排序算法

原理

采用分而治之的思想，每次递归，pivot记住左边都比它小，右边都比它大。

举个例子：

数组 A[p...r]:

1. 分解：A[p..q-1] A[q+1..r]，使得 A[p...q-1]<A[q]<A[q+1..r]；
2. **解决：**递归调用快排，对子数组A[p..q-1]，A[q+1..r]排序；
3. 合并：子问题相互独立的，因此用分治算法就可以了。

具体步骤：

1. 选择一个元素作为基准pivot(通常取分区的第一个或者最后一个)；
2. 执行重排数列，使得比pivot小的排左边，比pivot大的排右边，这个过程中pivot这个元素所在的坑会不断地被与它对比的元素置换，看起来就像是挖坑填数；
3. 递归的，使用相同的方式，重排左右两边的子序列。

对比扫描过程分2种：

• **挖坑排序：**2头向中间扫描，先从后向前找，再从前向后找。
• 单向扫描

挖坑排序

排序执行流程

以下是首轮比较的过程，2头向中间扫描，先从后向前找，再从前向后找。：

[23] 04 06 08 43 12 78 13 21
21 04 06 08 43 12 78 13 [23]
21 04 06 08 43 12 78 13 [23]
21 04 06 08 43 12 78 13 [23]
21 04 06 08 43 12 78 13 [23]
21 04 06 08 43 12 78 13 [23]
21 04 06 08 [23] 12 78 13 43
21 04 06 08 [23] 12 78 13 43
21 04 06 08 13 12 78 [23] 43
21 04 06 08 13 12 78 [23] 43
21 04 06 08 13 12 78 [23] 43
21 04 06 08 13 12 [23] 78 43

[21 04 06 08 13 12] 23 [78 43]

可以发现[23]这个坑一直在被替换填充。

网上给了很多算法的动态图来展示算法的执行执行流程，不过或许根据现有的数据，自己在脑海中发挥你的想象力让数字动起来也挺有趣的。

爱因斯坦对想象力极为推崇，他曾说过：想象力比知识更重要，因为知识是有限的，而想象力概括着世界上的一切并推动着进步。

激发你的想象力会有更好的记忆效果哦。(嗯，不上动图的借口很有说服力)

实现代码

public class QuickSort extends Sort {

    @Override
    public void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    /**
     * 快速排序算法
     * @param array 待排序数组区间
     * @param left 数组区间开始元素
     * @param right 数组区间结束元素
     */
    private void quickSort(int[] array, int left, int right) {
        // 防守,避免死循环
        if (left < right) {
            // 根据基准进行排序, 使得比pivot小的排左边，比pivot大的排右边,
            // pivotIndex 为基准元素最终的数组下标
            int pivotIndex = partition(array, left, right);
            // 递归调用两边
            quickSort(array, left, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, right);
        }
    }

    /**
     * 分区, 以选择的基准元素pivot将数组划分为比基准元素大的和比基准元素小的两个分区。
     * @param array
     * @param start
     * @param end
     * @return
     */
    private int partition(int[] array, int start, int end) {
        int seekStart = start;
        int seekEnd = end;
        int holeValue = array[seekStart];
        while (seekStart < seekEnd) {
            // 从后向前扫描对比替换前边的坑
            while (seekStart < seekEnd && array[seekEnd] >= holeValue) {
                seekEnd --;
            }
            // 找到之后, array[seekEnd]为新的坑
            if (seekStart < seekEnd) {
                array[seekStart] = array[seekEnd];
                // 前边的坑被填掉了,下标加1
                seekStart++;
            }
            // 从前向后扫描对比替换后边的坑
            while (seekStart < seekEnd && array[seekStart] <= holeValue) {
                seekStart ++;
            }
            // 找到之后, array[seekStart]为新的坑
            if (seekStart < seekEnd) {
                array[seekEnd] = array[seekStart];
                // 后边的坑被填掉了,下标减1
                seekEnd --;
            }
        }
        // 排序完成, 把原来的坑值赋值给最新的那个坑
        array[seekStart] = holeValue;
        return seekStart;
    }

}

单向扫描

排序执行流程

以下是首轮比较的过程，单向从前向后找，找到小的元素则往基准元素前面插队：

[23] 04 06 08 43 12 78 13 21
04 [23] 06 08 43 12 78 13 21
04 [23] 06 08 43 12 78 13 21
04 06 [23] 08 43 12 78 13 21
04 06 [23] 08 43 12 78 13 21
04 06 08 [23] 43 12 78 13 21
04 06 08 [23] 43 12 78 13 21
04 06 08 [23] 43 12 78 13 21
04 06 08 12 [23] 43 78 13 21
04 06 08 12 [23] 43 78 13 21
04 06 08 12 [23] 43 78 13 21
04 06 08 12 13 [23] 43 78 21
04 06 08 12 13 [23] 43 78 21
04 06 08 12 13 21 [23] 43 78

可以发现[23]这个坑一直在被替换填充。

关键是找出基准元素后边比基准元素小的元素后，把该元素往基准元素前面插入，然后基准元素到该元素之间的所有元素往后移动一格。

实现代码

/**
 * 快速排序算法
 *
 * Created by arthinking on 9/3/2019.
 */
public class QuickSort extends Sort {

    @Override
    public void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    /**
     * 快速排序算法
     * @param array 待排序数组区间
     * @param left 数组区间开始元素
     * @param right 数组区间结束元素
     */
    private void quickSort(int[] array, int left, int right) {
        // 防守,避免死循环
        if (left < right) {
            // 根据基准进行排序, 使得比pivot小的排左边，比pivot大的排右边,
            // pivotIndex 为基准元素最终的数组下标
            int pivotIndex = partition(array, left, right);
            // 递归调用两边
            quickSort(array, left, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, right);
        }
    }

    /**
     * 分区, 以选择的基准元素pivot将数组划分为比基准元素大的和比基准元素小的两个分区。
     * @param array
     * @param start
     * @param end
     * @return
     */
    private int partition(int[] array, int start, int end) {
        int pivotIndex = start;
        int seekEnd = end;
        int holeValue = array[pivotIndex];

        for (int seekIndex = pivotIndex+1; seekIndex <= seekEnd; seekIndex++) {
            // 如果后面的元素小于基准元素, 则往基准元素前面插队
            if(array[seekIndex] < array[pivotIndex]) {
                array[pivotIndex] = array[seekIndex];
                // pivotIndex+1 到 seekIndex(不包括seekIndex)之间的元素往后移动, 在 pivotIndex后面腾出一个位置来放基准元素
                for (int temp = seekIndex; temp > pivotIndex + 1; temp --) {
                    array[temp] = array[temp - 1];
                }
                // privotIndex 下一个元素处填入基准元素
                pivotIndex++;
                array[pivotIndex] = holeValue;
            }
        }
        return pivotIndex;
    }

}

为了让代码好理解一点，现在我们通过重构手法调整一下partition方法的代码，效果如下：

/**
  * 分区, 以选择的基准元素pivot将数组划分为比基准元素大的和比基准元素小的两个分区。
  * @param array
  * @param start
  * @param end
  * @return
  */
 private int partition(int[] array, int start, int end) {
     int pivotIndex = start;
     int seekEnd = end;
     int holeValue = array[pivotIndex];

     for (int seekIndex = pivotIndex+1; seekIndex <= seekEnd; seekIndex++) {
         // 如果后面的元素小于基准元素, 则往基准元素前面插队
         if(array[seekIndex] < array[pivotIndex]) {
             pivotIndex = insertSeekBeforePivot(array, pivotIndex, holeValue, seekIndex);
         }
     }
     return pivotIndex;
 }

 private int insertSeekBeforePivot(int[] array, int pivotIndex, int holeValue, int seekIndex) {
     array[pivotIndex] = array[seekIndex];
     // pivotIndex+1 到 seekIndex(不包括seekIndex)之间的元素往后移动, 在 pivotIndex后面腾出一个位置来放基准元素
     backwardArray(array, pivotIndex, seekIndex);
     // privotIndex 下一个元素处填入基准元素
     pivotIndex++;
     array[pivotIndex] = holeValue;
     return pivotIndex;
 }

 private void backwardArray(int[] array, int start, int end) {
     // 该方法等价于: System.arraycopy(array, start + 1, array, start + 1 + 1, end - (start + 1));
     for (int temp = end; temp > start + 1; temp --) {
         array[temp] = array[temp - 1];
     }
 }

练习时间：

ok，了解了算法的实现原理以及实现细节之后，打开开发环境，根据自己脑海中的印象，重新写一遍试试看吧！

温馨提示

理解好了处理流程，那么写伪代码还是比较容易的，但是如果要一次性写对就不那么容易了，特别是临界值比较容易处理错。如果发现不正确，可以在写完代码之后通过debug查看哪一步临界值弄错了，再梳理一下逻辑重新调整代码。

References

Learn-Algorithms