文章目录

十大算法>排序算法
快速排序
- - 描述
  - 实现
  - 示例
  - 注意点
  - 算法评估
  - 优化
  - - - 优化1
      - 优化2
      - 优化3
      - 优化4
      - 两路快排
      - 三路快排
参考资料

十大算法>排序算法

算法>排序算法	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	排序方式	稳定性
插入排序	n^2	n	1	in	稳定
冒泡排序	n^2	n	1	in	稳定
选择排序	n^2	n^2	1	in	不稳定
快速排序	n^2	nlog(2, n)	log(2, n)	in	不稳定
归并排序	nlog(2, n)	nlog(2, n)	n	out	稳定
希尔排序	n^2	n	1	in	不稳定
堆排序	nlog(2, n)	nlog(2, n)	1	in	不稳定
桶排序	n+k	n	n+k	out	稳定
计数排序	n+k	n+k	k	out	稳定
基数排序	n*k	n*k	n+k	out	稳定

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行

快速排序

描述

思路

①从序列中选择一个轴点元素(pivot)，假设每次选择0位置的元素为轴点元素

②利用pivot将序列分割成2个子序列

将小于pivot的元素放在pivot前面(左侧)
将大于pivot的元素放在pivot后面(右侧)
等于pivot的元素放哪边都可以

③对子序列进行①②操作，直到不能再分割(子序列中只剩下1个元素)

快速排序本质

逐渐将每一个元素变为轴点元素

在这里插入图片描述

实现

确定轴点元素位置的本质就相当于挖坑填数。

对挖坑填数，确定轴点位置，使用的主要思想是双指针:
- 1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
- 2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
- 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
- 4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
- 5.返回[begin,end]范围的轴点元素

java">class QuickSort {

    public void sort(int[] arr, int begin, int end) {

        if (end - begin < 1) {
            return;
        }

        // 确定轴点位置
        int mid = pivotIndex(arr, begin, end);
        
        // 打印信息
        System.out.println("-------------分割线------------------");
        System.out.println("本次开始位置：" + begin);
        System.out.println("本次结束位置：" + end);
        System.out.println("本次轴元素位置：" + mid);
        System.out.println("本次轴元素数值：" + arr[mid]);
        System.out.println("本次数组：" + Arrays.toString(arr));
        
        // 对子序列进行快速排序
        sort(arr, begin, mid - 1);
        sort(arr, mid + 1, end);
    }

    // 构造出[begin,end]范围的轴点元素
    public int pivotIndex(int[] arr, int begin, int end) {
        int pivot = arr[begin];      //arr[begin]即arr[begin]就是第一个坑

        while (begin < end) {
            // 重点 arr[i]与pivot的比较中，不使用等号 
            // 从右向左找小于x的数来填arr[begin]
            while (begin < end && arr[end] > pivot) {
                end--;
            }


            if (begin < end) {
                arr[begin] = arr[end]; //将arr[end]填到arr[begin]中，arr[end]就形成了一个新的坑
                begin++;
            }

            // 从左向右找大于或等于x的数来填arr[end]
            while (begin < end && arr[begin] < pivot) {
                begin++;
            }

            if (begin < end) {
                //将arr[begin]填到arr[end]中，arr[begin]就形成了一个新的坑
                arr[end] = arr[begin];
                end--;
            }
        }
        //退出时，begin等于end。将pivot填到这个坑中。
        arr[begin] = pivot;
        return begin;
    }


}

示例

java">待排序的数组：[44, 55, 10, 30, 99, 56, 17, 75, 70, 21, 58, 53, 82, 59, 88, 43, 47, 54, 72, 50]
-------------分割线------------------
本次开始位置：0
本次结束位置：19
本次轴元素位置：5
本次轴元素数值：44
本次数组：[43, 21, 10, 30, 17, 44, 56, 75, 70, 99, 58, 53, 82, 59, 88, 55, 47, 54, 72, 50]
-------------分割线------------------
本次开始位置：0
本次结束位置：4
本次轴元素位置：4
本次轴元素数值：43
本次数组：[17, 21, 10, 30, 43, 44, 56, 75, 70, 99, 58, 53, 82, 59, 88, 55, 47, 54, 72, 50]
-------------分割线------------------
本次开始位置：0
本次结束位置：3
本次轴元素位置：1
本次轴元素数值：17
本次数组：[10, 17, 21, 30, 43, 44, 56, 75, 70, 99, 58, 53, 82, 59, 88, 55, 47, 54, 72, 50]
-------------分割线------------------
本次开始位置：2
本次结束位置：3
本次轴元素位置：2
本次轴元素数值：21
本次数组：[10, 17, 21, 30, 43, 44, 56, 75, 70, 99, 58, 53, 82, 59, 88, 55, 47, 54, 72, 50]
-------------分割线------------------
本次开始位置：6
本次结束位置：19
本次轴元素位置：11
本次轴元素数值：56
本次数组：[10, 17, 21, 30, 43, 44, 50, 54, 47, 55, 53, 56, 82, 59, 88, 58, 99, 70, 72, 75]
-------------分割线------------------
本次开始位置：6
本次结束位置：10
本次轴元素位置：7
本次轴元素数值：50
本次数组：[10, 17, 21, 30, 43, 44, 47, 50, 54, 55, 53, 56, 82, 59, 88, 58, 99, 70, 72, 75]
-------------分割线------------------
本次开始位置：8
本次结束位置：10
本次轴元素位置：9
本次轴元素数值：54
本次数组：[10, 17, 21, 30, 43, 44, 47, 50, 53, 54, 55, 56, 82, 59, 88, 58, 99, 70, 72, 75]
-------------分割线------------------
本次开始位置：12
本次结束位置：19
本次轴元素位置：17
本次轴元素数值：82
本次数组：[10, 17, 21, 30, 43, 44, 47, 50, 53, 54, 55, 56, 75, 59, 72, 58, 70, 82, 99, 88]
-------------分割线------------------
本次开始位置：12
本次结束位置：16
本次轴元素位置：16
本次轴元素数值：75
本次数组：[10, 17, 21, 30, 43, 44, 47, 50, 53, 54, 55, 56, 70, 59, 72, 58, 75, 82, 99, 88]
-------------分割线------------------
本次开始位置：12
本次结束位置：15
本次轴元素位置：14
本次轴元素数值：70
本次数组：[10, 17, 21, 30, 43, 44, 47, 50, 53, 54, 55, 56, 58, 59, 70, 72, 75, 82, 99, 88]
-------------分割线------------------
本次开始位置：12
本次结束位置：13
本次轴元素位置：12
本次轴元素数值：58
本次数组：[10, 17, 21, 30, 43, 44, 47, 50, 53, 54, 55, 56, 58, 59, 70, 72, 75, 82, 99, 88]
-------------分割线------------------
本次开始位置：18
本次结束位置：19
本次轴元素位置：19
本次轴元素数值：99
本次数组：[10, 17, 21, 30, 43, 44, 47, 50, 53, 54, 55, 56, 58, 59, 70, 72, 75, 82, 88, 99]
排序结果：[10, 17, 21, 30, 43, 44, 47, 50, 53, 54, 55, 56, 58, 59, 70, 72, 75, 82, 88, 99]

Process finished with exit code 0

注意点

与轴点相等的元素的处理

java">待排序的数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：0
本次结束位置：19
本次轴元素位置：10
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：0
本次结束位置：9
本次轴元素位置：5
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：0
本次结束位置：4
本次轴元素位置：2
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：0
本次结束位置：1
本次轴元素位置：1
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：3
本次结束位置：4
本次轴元素位置：4
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：6
本次结束位置：9
本次轴元素位置：8
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：6
本次结束位置：7
本次轴元素位置：7
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：11
本次结束位置：19
本次轴元素位置：15
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：11
本次结束位置：14
本次轴元素位置：13
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：11
本次结束位置：12
本次轴元素位置：12
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：16
本次结束位置：19
本次轴元素位置：18
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------分割线------------------
本次开始位置：16
本次结束位置：17
本次轴元素位置：17
本次轴元素数值：0
本次数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
排序结果：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Process finished with exit code 0

算法评估

在轴点左右元素数量比较均匀的情况下，同时也是最好的情况

T(n)= 2* T(n/2) + 0(n) = 0(nlogn)
如果轴点左右元素数量极度不均匀，最坏情况
T(n)= T(n- 1) + 0(n) = 0(n2)
为了降低最坏情况的出现概率, 一般采取的做法是
随机选择轴点元素
最好、平均时间复杂度: 0(nlogn)
最坏时间复杂度: 0(n^2)
由于递归调用的缘故,空间复杂度: log(2,n)

优化

这里只简要陈列优化思路，具体优化细节请查阅参考资料。(或者等我有时间做笔记吧)

优化1

基点的选择随机化，尽量避免最坏的情况出现

java">private int __partioner ( int arr[], int L, int R ) {

        // 将基点的选择随机化
        int rand = (new Random().nextInt(R + 1)) + L;

        // 交换最左侧和随机点的元素
        int tmp = arr[rand];
        arr[rand] = arr[L];
        arr[L] = tmp;
 
        int v = arr[L];

        // [L + 1, j] < v ; [j + 1, i) > v;
        int j = L;

        for ( int i = L + 1; i <= R; i++ ) {
            if ( arr[i] < v) {
                // 交换 arr[i] 和 arr [j + 1]
                int tmp = arr[j + 1];
                arr[j + 1] = arr[i];
                arr[i] = tmp;
                j++;
            }
        }
        // 交换 arr[j]  和arr[L]
        int tmp = arr[j];
        arr[j] = arr[L];
        arr[L] = tmp;

        return j;
    }

优化2

减小递归的深度，转而使用选择排序

当分区的规模达到一定小时，便停止快速排序算法。即快速排序算法的最终产物是一个“几乎”排序完成的有序数列。

数列中有部分元素并没有排到最终的有序序列的位置上，但是这种元素并不多。可以对这种“几乎”完成排序的数列使用插入算法>排序算法进行排序以最终完成整个排序过程。

因为插入排序对于这种“几乎”完成的排序数列有着接近线性的复杂度。

java">private __quickSorted( int arr[], int L, int R) {
        // 减小递归的深度，转而使用 选择排序
        if ( R - L <= 15) {
            insertSorted(arr, L, R);
            return;
        }


        // 将基点移动到最终位置的方法
        int p = __partioner(arr, L, R);

        // 递归拆分数组
        __quickSorted(arr, L, p - 1);
        __quickSorted(arr, p + 1, R);
    }


        // 减小递归的深度转而使用选择排序
    private void insertSorted(int arr[], int L, int R) {

        for (int i = L + 1; i <= R; i++) {
            int i = arr[i];
            int j;
            for (j = i; j > L && arr[j - 1] > e; j--) {
                arr[j] = arr[j - 1];
            }
        }
        return;
    }

优化3

在递归排序子分区的时候，总是选择优先排序那个最小的分区。这个选择能够更加有效的利用存储空间从而从整体上加速算法的执行。

对于快速排序算法来说，实际上大量的时间都消耗在了分区上面，尤其是当要分区的所有的元素值都相等时，一般的快速排序算法就陷入了最坏的一种情况，也即反复的交换相同的元素并返回最差的中轴值。

对于这种情况的改进办法

将分区分为三块而不是原来的两块：一块是小于中轴值的所有元素，一块是等于中轴值的所有元素，另一块是大于中轴值的所有元素。（三路快排）
另一种简单的改进方法是，当分区完成后，如果发现最左和最右两个元素值相等的话就避免递归调用而采用其他的算法>排序算法来完成。

优化4

三平均分区法

选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。通过比较选出其中的中值。

取这3个值的好处是在实际问题中，出现近似顺序数据或逆序数据的概率较大，此时中间数据必然成为中值，而也是事实上的近似中值。万一遇到正好中间大两边小（或反之）的数据，取的值都接近最值，那么由于至少能将两部分分开，实际效率也会有2倍左右的增加，而且利于将数据略微打乱，破坏退化的结构。

两路快排

在最基础的版本中，考虑到了e>v,e<v，而e=v的情况没有考虑。

其实实际上把等于v这种情况包含进了大于v的情况里面了，那么会出现什么问题？

不管是当条件是大于等于还是小于等于v，当数组中重复元素非常多的时候，等于v的元素太多，那么就将数组分成了极度不平衡的两个部分，因为等于v的部分总是集中在数组的某一边。

那么一种优化的方式便是进行双路快排。

解决排序的数组中存在多数重复元素的情况

java">public void quickSorted ( int arr[] ) {

        int n = arr.length - 1;            // 闭区间 [0...n]
        __quickSorted (arr, 0, n);
    }

    private __quickSorted( int arr[], int L, int R) {

        // 减小递归的深度，转而使用 选择排序
        if ( R - L <= 15) {
            insertSorted(arr, L, R);
            return;
        }

        // 将基点移动到最终位置的方法
        int p = __partioner(arr, L, R);

        // 递归拆分数组
        __quickSorted(arr, L, p - 1);
        __quickSorted(arr, p + 1, R);
    }

    private int __partioner ( int arr[], int L, int R ) {

        // 将基点的选择随机化
        int rand = (new Random().nextInt(R + 1)) + L;

        // 交换最左侧和随机点的元素
        int tmp = arr[rand];
        arr[rand] = arr[L];
        arr[L] = tmp;

        int v = arr[L];

        // 两路快排的实现过程
        int i = L + 1;
        int j = R ;

        while (true) {
            while (i <= R && arr[i] < v ){
                i++;
            }
            while (j >= L + 1 && arr[j] > v) {
                j--;
            }
            if (i > j) {
                break;
            }

            // 交换 i 和 j 的位置
            int tmp arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        int tmp arr[L];
        arr[L] = arr[j];
        arr[j] = tmp;

        return j;
    }

    // 减小递归的深度转而使用选择排序
    private void insertSorted(int arr[], int L, int R) {

        for (int i = L + 1; i <= R; i++) {
            int i = arr[i];
            int j;
            for (j = i; j > L && arr[j - 1] > e; j--) {
                arr[j] = arr[j - 1];
            }
        }
        return;
    }

三路快排

主要用于应对有大量重复元素的情况。

双路快排将整个数组分成了小于v，大于v的两部分，而三路快排则是将数组分成了小于v，等于v，大于v的三个部分。

java">public class QuickSort3Ways {

    // 递归使用快速排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r){

        // 对于小规模数组, 使用插入排序
        if( r - l <= 15 ){
            InsertionSort.sort(arr, l, r);
            return;
        }

        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr, l, (int)(Math.random()*(r-l+1)) + l );

        Comparable v = arr[l];

        int lt = l;     // arr[l+1...lt] < v
        int gt = r + 1; // arr[gt...r] > v
        int i = l+1;    // arr[lt+1...i) == v
        while( i < gt ){
            if( arr[i].compareTo(v) < 0 ){
                swap( arr, i, lt+1);
                i ++;
                lt ++;
            } else if( arr[i].compareTo(v) > 0 ){
                swap( arr, i, gt-1);
                gt --;
            } else{ 
                // arr[i] == v
                i ++;
            }
        }

        swap( arr, l, lt );

        sort(arr, l, lt-1);
        sort(arr, gt, r);
    }

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

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

}