算法(第四版)之快速排序

素颜马尾好姑娘i 2021-12-15 09:53 232阅读 0赞

快速排序是目前使用最广泛的排序, 同时也是目前最快的排序,它也体现了分治的思想:将数组分成两部分, 并分别独立地进行排序. 和归并排序不同的是, 归并排序是将两个有序的数组合并为一个有序的大数组, 而快排则是当小数组有序时, 大数组就自然有序了

快速排序是用一个数v将数组切分, v左边的数全都小于v, v右边的数全都大于v, 在将小数组继续切分, 直到不能再分为止, 这样数组就有序了:

![1621057-20190516180734927-2145152639.png][]

我们先写排序主体:

1     public static void sort(int[] a, int lo, int hi) {
    2         if(hi <= lo) return;
    3         int j =  partition(a, lo, hi);
    4         sort(a, lo, j-1);
    5         sort(a, j+1, hi);
    6     }

然后写切分函数partition():

1     private static int partition(int[] a, int lo, int hi) { //普通的快排
     2         int i = lo, j = hi + 1;
     3         int v = a[lo];
     4         while(true) {
     5             while(a[++i] < v) 
     6                 if(i == hi) break;
     7             while(a[--j] > v) 
     8                 if(j == lo) break;
     9             if(i >= j) break;
    10             int tmp = a[i];
    11             a[i] = a[j];
    12             a[j] = tmp;
    13         }
    14         int tmp = a[lo];
    15         a[lo] = a[j];
    16         a[j] = tmp;
    17         return j;
    18     }

当然, 这不是最优的代码, 还有更优的解决方案, 那就是将数组切分为三部分, 大于v, 等于v和小于v的三部分:

1 　　private static void quick3way(int[] a, int lo, int hi) { //三项切分的快速排序
     2         if(hi <= lo)
     3             return;
     4         int lt = lo, i = lo+1, gt = hi;
     5         int v = a[lo];
     6         while(i <= gt) {
     7             if(a[i] < v) {
     8                 int tmp = a[i];
     9                 a[i++] = a[lt];
    10                 a[lt++] = tmp;
    11             } else if(a[i] > v) {
    12                 int tmp = a[i]; 
    13                 a[i] = a[gt];
    14                 a[gt--] = tmp;
    15             } else i++;
    16         }
    17         quick3way(a, lo, lt-1);
    18         quick3way(a, gt+1, hi);
    19     }

![1621057-20190516182150862-251716439.png][]

可以预见, 在含有大量相同元素的情况下, 三项切分对快排的性能会有很大提升

普通的快速排序时间复杂度为O(nlogn), 三项快排的时间复杂度在O(n)和O(nlogn)之间, 但他们的空间复杂度都为O(lgn), 他们都频繁的使用了递归调用

转载于:https://www.cnblogs.com/qq1914808114/p/10877279.html

[1621057-20190516180734927-2145152639.png]: /images/20211214/dd526007be92460cb1d6ac047f1483be.png
[1621057-20190516182150862-251716439.png]: /images/20211214/5fbfaa5ffe684c958e4e995f2cbac802.png