关卡6：快速排序(Quick Sort)

本文内容是对快速排序的梳理和总结，本文内容包括：

快速排序(Quick Sort)

排序算法十大经典方法

冒泡排序：比较相邻元素并交换，每一轮将最大的元素移动到最后。
选择排序：每一轮选出未排序部分中最小的元素，并将其放在已排序部分的末尾。
插入排序：将未排序部分的第一个元素插入到已排序部分的合适位置
希尔排序：改进的插入排序，将数据分组排序，最终合并排序
归并排序：将序列拆分成子序列，分别排序后合并，递归完成
快速排序：选定一个基准值，将小于基准值的元素放在左边，大于基准值的元素放在右边，递归排序
堆排序：将序列构建成一个堆，然后一次将堆顶元素取出并调整堆
计数排序：统计每个元素出现的次数，再按照元素大小输出
桶排序：将数据分到一个或多个桶中，对每个桶进行排序，最后输出
基数排序：按照元素的位数从低到高进行排序，每次排序只考虑一位

快速排序(Quick Sort)

快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。

快速排序的基本思想：通过一趟排序将待排序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。

算法步骤

快速排序使用分治法策略来把一个序列分为较小和较大的 2 个子序列，然后递回地排序两个子序列。具体算法描述如下：

从序列中随机挑出一个元素，做为 “基准”(pivot)；
重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个操作结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地把小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。

图解算法

如果下图不动，点击这里查看在线的图解

代码实现

public static void main(String[] args) {
    int[ ] data = { 19 , 22 , 98 , 100 , 56 , 77 , 45 , 72 , 0 , -1 };
    quickSort(data,0,data.length-1);
}
private static int partition(int[] arr, int startIndex, int endIndex) {
    int pivot = arr[startIndex];
    int leftPoint = startIndex;
    int rightPoint = endIndex;
    while (leftPoint < rightPoint) {
        // 从右向左找出比pivot小的数据
        while (leftPoint < rightPoint && arr[rightPoint] > pivot) {
            rightPoint--;
        }
        // 从左向右找出比pivot大的数据
        while (leftPoint < rightPoint  && arr[leftPoint] <= pivot) {
            leftPoint++;
        }
        // 没有过界则交换
        if (leftPoint < rightPoint) {
            int temp = arr[leftPoint];
            arr[leftPoint] = arr[rightPoint];
            arr[rightPoint] = temp;
        }
    }
    // 最终将分界值与当前指针数据交换
    arr[startIndex] = arr[rightPoint];
    arr[rightPoint] = pivot;
    // 返回分界值所在下标
    return rightPoint;
}
public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
        int position = partition(array, low, high);
        quickSort(array, low, position - 1);
        quickSort(array, position + 1, high);
    }
}

算法分析

稳定性 ：不稳定
时间复杂度 ：最佳：O(nlogn)，最差：O(n²)，平均：O(nlogn)
空间复杂度 ：O(nlogn)

开发喵星球