[数据结构与算法]快速排序算法

快速排序（Quick Sort），也称分区交换排序，是对冒泡排序的改进，由 C.R.A.Hoare 于1962年提出的一种分区交换方法。在冒泡排序中，记录的比较和移动是在相邻的位置进行的，记录每次交换只能消除一个逆序，因而总的比较和移动次数较多。在快速排序中，通过分区间的一次交换能消除多个逆序。实际上，快速排序名副其实，它是目前最快的内部排序算法

快速排序适用于数据较多且基本无序的情况。因为排序过程中存在大跨度的数据移动，所以快速排序是一种不稳的排序算法

快速排序基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

1. 在待排序的序列中，选取一个元素作为枢轴（pivot），通过该值将数组分成左右两部分
2. 凡是元素小于枢轴的移动至枢轴之前，凡是元素大于枢轴的均移动至枢轴之后。一趟排序之后，记录序列根据枢轴最终的位置，划分为两个子序列 L（Left） 和 R（Right），使得 L 子序列中的所有元素值小于或等于枢轴，R 中所有元素值都大于等于枢轴
3. 对子序列 L 和 R 分别继续进行快速排序，直至子序列中只有一个元素为止
4. 上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了

测试用例： 使用快速排序算法将数组 { 36，80，45，66，22，9，16，36 } 进行升序排序

第一次详细对比过程

排序趟数结果

代码实现

/**
 * 一趟快速排序
 * 结论: 每进行一次快速排序,至少有一个元素找到最终位置
 * @param nums 数组
 * @param low 低位
 * @param high 高位
 * @return 返回低位与高位相同的点
 */
public int partition(int[] nums, int low, int high) {
    int temp = nums[low];   // 参考值(pivot的值),将nums数组中的第一个元素挖空
    while (low != high){
        // 从高点位方向开始
        while (low < high && nums[high] >= temp) high--;    // 当高位点的元素大于或等于参考值时,高位点自减,直至出现高位点元素小于参考值
        if (low < high) { nums[low] = nums[high]; low++;}   // 如果此时低位点小于高位点,将此时高位点的元素赋值到低位点的位置,低位点自增
        // 再从低点位方向开始
        while (low < high && nums[low] <= temp) low++;  // 当低位点的元素大于或等于参考值时,自减,直至出现低位点元素大于参考值
        if (low < high) { nums[high] = nums[low]; high--;}  // 如果此时低位点小于高位点,将此时低位点的元素赋值到高位点的位置,高位点自增
    }
    nums[low] = temp;
    // 返回枢轴pivot的位置
    return low;
}

/**
 * 递归实现每次快速排序
 * @param nums 数组
 * @param low 低位
 * @param high 高位
 * @return 返回排列好的数组
 */
public int[] quickSort(int[] nums, int low, int high) {
    int pivot;
    if (low >= high) return null;

    pivot = partition(nums, low, high);     // 第一次划分,返回枢轴位置
    quickSort(nums, low, pivot-1);      // 对枢轴左边一半快速排序
    quickSort(nums, pivot+1, high);     // 对枢轴右边一半快速排序
    return nums;
}

时间复杂度： 假设处理的数据规模大小为$n$，运行时间为$T(n)$

1. 当把$n$分为两半时，那么处理大小为$\frac{n}{2}$子数组花费时间为：$T(\frac{n}{2})$
2. 合并花费时间与数据规模成正比：$n$
3. 所以处理规模大小为$n$的数据所需要花费两个大小为$\frac{n}{2}$的子数组加上合并花费的时间，即$T(n)=2T(\frac{n}{2})+n$

对于快速排序算法，最好的情况就是每次分割都能够从数组的中间分割，这样分割$logn$次就行了，此时的时间复杂度为$O(nlogn)$

但也有可能会出现一种极端的情况，每次分割的时候，枢轴左边的元素个数都为0，而右边都为$n?1$个。这个时候，就需要分割$n$次了。而每次分割整理的时间复杂度为$O(n)$，所以最坏的时间复杂度为$O(n^2)$

空间复杂度：快速排序每次递归都需要一个元素大小的辅助空间用于比较和存放最终的位置，所以空间复杂度为$O(n)$