经典排序算法系列5-快速排序

Quick Sort 快速排序

需求

对N个整数升序排序

思路

和归并排序一样，也是用的分治思想，但实现思路和归并排序不一样。

在数组中任意选取一个元素作为分区点（这里选择最后一个元素），将小于分区点的元素放到分区点左边，大于分区点的元素放到分区点右边。递归对左边部分和右边部分排序，直至待排序的子序只有1个元素（即每个子序都是有序的），排序结束。

算法评判

• 时间复杂度

  

• 空间复杂度

  

  只需要常量级的辅助空间，所以也叫原地排序

• 稳定性

  结论：不稳定

代码实现如下

public void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int from, int to) {
        int pivotIndex = partition(arr, from, to);
      //说明左半部分还有多个元素，递归之
        if (pivotIndex > from) {
            sort(arr, from, pivotIndex - 1);
        }
      //说明右半部分还有多个元素，递归之
        if (pivotIndex < to) {
            sort(arr, pivotIndex + 1, to);
        }
    }


        //返回最后一个元素（分区元素）在分区后所在的位置，其实相当于数小于分区元素的个数
    private int partition(int[] arr, int from, int to) {
        int pivotIndex = from;
        //以最后一个元素为分区点
        int pivot = arr[to];
        for (int j = from; j < to; j++) {
          //将左半部分的元素往前挪，同时将分区下标往后提升一位
            if (arr[j] < pivot) {
                if(pivotIndex!=j){//这里只是一个小小的优化，避免无意义地赋值操作
                    swap(arr, pivotIndex, j);
                }
                pivotIndex++;
            }
        }
      //将分区元素放到真正的位置pivotIndex上，在前面，小于分区元素的元素都挪到pivotIndex前面去了，所以从pivotIndex到to-1这些元素都是大于分区元素的
        swap(arr, pivotIndex, to);
        return pivotIndex;

    }

快速排序的难点在于分区函数的实现，上面的方法一下难以看懂，先从简单的方式开始，再次明确下分区函数的功能，将小于分区元素的元素放在左边，大于的放在右边，最后返回分区元素所在的位置。不考虑空间复杂度的情况下，先为左右两部分分别申请一个空数组，逐个遍历，放入各自的数组。最后将左边数组、分区元素和右边数组回填到原数组中。

后面再组织语言，借助插入排序思想 本质上将左半部分的元素往前挪，

关于稳定性，对于[6，8，6，2，9],第一次分区会出现第一个6和2对换，两个6的相对次序被改变了，所以快速排序是不稳定的。

拓展

利用快速排序思想，在时间复杂度下找出第K大元素

思路：还是利用分区，最后一个元素作为分区元素，当分区后得到[0,p-1]， p和[p+1,n]三部分，比较第三部分元素个数和K-1

1. 大于，递归在[p+1,n]序列中找

2. 等于,p就是所找的第K大元素下标

3. 小于，递归在[0,p-1]中找第K-m大元素(m是第三部分元素的个数)

复杂度计算：，等比数列求和得,所以时间复杂度是

再拓展，一般找第K大元素，还可以利用堆排序，先对前K个元素构建一个小顶堆，遍历剩余的n-K个元素，如果大于对等元素，则将堆顶元素替换出来，调整堆。最后堆顶元素就是第K大元素。

时间复杂度，n-k+1次调整堆，具体调整堆的时间复杂度是多少，且看堆排序