关于算法:看动画学算法之排序快速排序

4次阅读

共计 2617 个字符，预计需要花费 7 分钟才能阅读完成。

疾速排序也采纳的是分而制之的思维。那么疾速排序和归并排序的区别在什么中央呢？

归并排序是将所有的元素拆分成一个个排好序的数组，而后将这些数组再进行合并。

而疾速排序尽管也是拆分，然而拆分之后的操作是从数组中选出一个两头节点，而后将数组分成两局部。

右边的局部小于两头节点，左边的局部大于两头节点。

而后再别离解决右边的数组合左边的数组。

如果咱们有一个数组：29,10,14,37,20,25,44,15，怎么对它进行疾速排序呢？

先看一个动画：

咱们再剖析一下疾速排序的步骤。

咱们抉择的是最右边的元素 29 作为两头点元素，而后将数组分成三局部：[0, 14, 15, 20, 25],[29],[44, 37]。

两头节点 29 曾经排好序了，不须要解决。

接下来咱们再对左右别离进行疾速排序。最初就失去了一个所有元素都排序的数组。

咱们先来看最外围的局部 partition，如何将数组以两头节点为界，分成左右两局部呢？

咱们的最终后果，是要将 array 宰割成为三局部。

首先咱们抉择最左侧的元素作为两头节点的值。而后遍历数组中的其余元素。

如果 m =middleIndex，k= 要遍历的元素 index

思考两种状况，第一种状况是数组中的元素比两头节点的值要大。

这种状况下，m 不须要挪动，k+ 1 持续遍历即可。

第二种状况下，数组中的元素比两头节点的值要小。

因为 m 右边的元素都要比两头节点的值要小，所以这种状况下 m 须要 +1，即右移一位。

当初 m + 1 地位的元素要么还没有进行比拟，要么就是比两头节点的值要大，咱们能够奇妙的将 m + 1 地位的元素和 k 地位的元素调换地位，这样依然可能保障 m 左侧的元素要比两头节点的值要小。

将下面的剖析总结成 java 代码如下：

 private int partition(int[] array, int i, int j) {
        // 抉择最左侧的元素作为中心点,middleValue 就是中心点的值
        int middleValue = array[i];
        int middleIndex = i;
        // 从 i + 1 遍历整个数组
        for (int k = i+1; k <= j; k++) {
            // 如果数组元素小于 middleValue，示意 middleIndex 须要右移一位
            // 右移之后，咱们须要将小于 middleValue 的 array[k] 挪动到 middleIndex 的右边，// 最简略的方法就是替换 k 和 middleIndex 的值
            if (array[k] < middleValue) {
                middleIndex++;
                // 替换数组的两个元素
                swap(array, k , middleIndex);
            } // 如果数组元素大于等于 middleValue, 则持续向后遍历,middleIndex 值不变
        }
        // 最初将中心点放入 middleIndex 地位
        swap(array, i, middleIndex);
        return middleIndex;
    }

最初咱们须要将最左侧的元素和两头节点应该在的 index 的元素调换下地位，这样就将两头节点挪动到了两头地位，并返回两头地位。

再来看下 divide 的代码：

    public void doQuickSort(int[] array, int low, int high) {
        // 递归的完结条件
        if (low < high) {
            // 找出核心节点的值
            int middleIndex = partition(array, low, high);
            // 数组分成了三局部：// a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
            // 递归遍历左侧局部
            doQuickSort(array, low, middleIndex-1);
            // a[m] 是核心节点，曾经排好序了，不须要持续遍历
            // 递归遍历右侧局部
            doQuickSort(array, middleIndex+1, high);
            log.info("QuickSort 之后的数组:{}",array);
        }
    }

divide 的代码就很简略了，找到两头节点的地位之后，咱们再别离遍历数组的左右两边即可。最初失去排好序的数组。

下面的例子中，咱们的两头节点的抉择是数组的最左元素，为了保障排序的效率，咱们能够从数组中随机抉择一个元素来作为两头节点。

 private int partition(int[] array, int i, int j) {
        // 随机抉择一个元素作为中心点,middleValue 就是中心点的值
        int randomIndex=i+new Random().nextInt(j-i);
        log.info("randomIndex:{}",randomIndex);
        // 首先将 randomIndex 的值和 i 调换地位, 就能够复用 QuickSort 的逻辑
        swap(array, i , randomIndex);
        int middleValue = array[i];
        int middleIndex = i;
        // 从 i 遍历整个数组
        for (int k = i+1; k <= j; k++) {
            // 如果数组元素小于 middleValue，示意 middleIndex 须要右移一位
            // 右移之后，咱们须要将小于 middleValue 的 array[k] 挪动到 middleIndex 的右边，// 最简略的方法就是替换 k 和 middleIndex 的值
            if (array[k] < middleValue) {
                middleIndex++;
                // 替换数组的两个元素
                swap(array, k , middleIndex);
            } // 如果数组元素大于等于 middleValue, 则持续向后遍历,middleIndex 值不变
        }
        // 最初将中心点放入 middleIndex 地位
        swap(array, i, middleIndex);
        return middleIndex;
    }

下面的代码，咱们在分区的时候，先抉择出一个随机的节点，而后将这个随机的节点和最左侧的元素替换地位，前面的代码就能够重用下面的 QuickSort 的代码逻辑了。

从下面的剖析咱们能够看出，每次分区的工夫复杂度应该是 O(N)，而 divide 又近似二分法，所以总的工夫复杂度是 O(N logN)。

本文的代码地址：

learn-algorithm