6 交换排序—快速排序（Quick Sort）

基本思想

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

快速排序的示例：

（a）一趟排序的过程：

（b）排序的全过程

算法的实现：

递归实现：

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
void swap(int *a, int *b)  
{  
    int tmp = *a;  
    *a = *b;  
    *b = tmp;  
}  
int partition(int a[], int low, int high)  
{  
    int privotKey = a[low];                             //基准元素  
    while(low < high){                                   //从表的两端交替地向中间扫描  
        while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端  
        swap(&a[low], &a[high]);  
        while(low < high  && a[low] <= privotKey ) ++low;  
        swap(&a[low], &a[high]);  
    }  
    print(a,10);  
    return low;  
}  
void quickSort(int a[], int low, int high){  
    if(low < high){  
        int privotLoc = partition(a,  low,  high);  //将表一分为二  
        quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序  
        quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序  
    }  
}  
int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    cout<<"初始值：";  
    print(a,10);  
    quickSort(a,0,9);  
    cout<<"结果：";  
    print(a,10);  
}

分析

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的

但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。

为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

快速排序的改进

在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时,改进算法的性能最佳。算法思想如下：

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
void swap(int *a, int *b)  
{  
    int tmp = *a;  
    *a = *b;  
    *b = tmp;  
}  
int partition(int a[], int low, int high)  
{  
    int privotKey = a[low];                 //基准元素  
    while(low < high){                   //从表的两端交替地向中间扫描  
        while(low < high  && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端  
        swap(&a[low], &a[high]);  
        while(low < high  && a[low] <= privotKey ) ++low;  
        swap(&a[low], &a[high]);  
    }  
    print(a,10);  
    return low;  
}  
void qsort_improve(int r[ ],int low,int high, int k){  
    if( high -low > k ) { //长度大于k时递归, k为指定的数  
        int pivot = partition(r, low, high); // 调用的Partition算法保持不变  
        qsort_improve(r, low, pivot - 1,k);  
        qsort_improve(r, pivot + 1, high,k);  
    }   
}   
void quickSort(int r[], int n, int k){  
    qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序  
    //再用插入排序对基本有序序列排序  
    for(int i=1; i<=n;i ++){  
        int tmp = r[i];   
        int j=i-1;  
        while(tmp < r[j]){  
            r[j+1]=r[j]; j=j-1;   
        }  
        r[j+1] = tmp;  
    }   
}   
int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    cout<<"初始值：";  
    print(a,10);  
    quickSort(a,9,4);  
    cout<<"结果：";  
    print(a,10);  
}

7 归并排序(Merge Sort)

思想

将两个（或以上）有序表合并成一个新的有序表：

把待排序列分为若干子序列，每个子序列是有序的
再把有序子序列合并为整体有序序列

合并方法

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为n-i +1、n-m。

j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
//选取r[i]和r[j]较小的存入辅助数组rf
如果r[i]否则，rf[k]=r[j]； j++； k++；转⑵
//将尚未处理完的子表中元素存入rf
如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空
如果j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空
合并结束。

public class MergeSort {
  public static void mergeSort(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }
    mergeSort(arr, 0, arr.length - 1);
  }
  public static void mergeSort(int[] arr, int l, int r) {
    if (l == r) {
      return;
    }
    int mid = l + ((r - l) >> 1);
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
  }
  public static void merge(int[] arr, int l, int m, int r) {
    int[] help = new int[r - l + 1];
    int i = 0;
    int p1 = l;
    int p2 = m + 1;
    while (p1 <= m && p2 <= r) {
      help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= m) {
      help[i++] = arr[p1++];
    }
    while (p2 <= r) {
      help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
      arr[l + i] = help[i];
    }
  }
    /**
     *
     * @param arr
     */
  public static void comparator(int[] arr) {
    Arrays.sort(arr);
  }
    /**
     * for test
     * @param maxSize
     * @param maxValue
     * @return
     */
  public static int[] generateRandomArray(int maxSize, int maxValue) {
    int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
    for (int i = 0; i < arr.length; i++) {
      arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
    }
    return arr;
  }
    /**]
     *
     *  for test
     * @param arr
     * @return
     */
  public static int[] copyArray(int[] arr) {
    if (arr == null) {
      return null;
    }
    int[] res = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
      res[i] = arr[i];
    }
    return res;
  }
    /**
     * for test
     * @param arr1
     * @param arr2
     * @return
     */
  public static boolean isEqual(int[] arr1, int[] arr2) {
    if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
      return false;
    }
    if (arr1 == null && arr2 == null) {
      return true;
    }
    if (arr1.length != arr2.length) {
      return false;
    }
    for (int i = 0; i < arr1.length; i++) {
      if (arr1[i] != arr2[i]) {
        return false;
      }
    }
    return true;
  }
    /**
     * for test
     * @param arr
     */
  public static void printArray(int[] arr) {
    if (arr == null) {
      return;
    }
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
    /**
     * for test
     * @param args
     */
  public static void main(String[] args) {
    int testTime = 500000;
    int maxSize = 100;
    int maxValue = 100;
    boolean succeed = true;
    for (int i = 0; i < testTime; i++) {
      int[] arr1 = generateRandomArray(maxSize, maxValue);
      int[] arr2 = copyArray(arr1);
      mergeSort(arr1);
      comparator(arr2);
      if (!isEqual(arr1, arr2)) {
        succeed = false;
        printArray(arr1);
        printArray(arr2);
        break;
      }
    }
    System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    int[] arr = generateRandomArray(maxSize, maxValue);
    printArray(arr);
    mergeSort(arr);
    printArray(arr);
  }
}

归并的迭代算法

1个元素的表总是有序的。所以对n个元素的待排序列，每个元素可看成1个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1，其余子表长度均为2。再进行两两合并，直到生成n个元素按关键码有序的表。

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
{  
    int j,k;  
    for(j=m+1,k=i; i<=m && j <=n ; ++k){  
        if(r[j] < r[i]) rf[k] = r[j++];  
        else rf[k] = r[i++];  
    }  
    while(i <= m)  rf[k++] = r[i++];  
    while(j <= n)  rf[k++] = r[j++];  
    print(rf,n+1);  
}  
void MergeSort(ElemType *r, ElemType *rf, int lenght)  
{   
    int len = 1;  
    ElemType *q = r ;  
    ElemType *tmp ;  
    while(len < lenght) {  
        int s = len;  
        len = 2 * s ;  
        int i = 0;  
        while(i+ len <lenght){  
            Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并  
            i = i+ len;  
        }  
        if(i + s < lenght){  
            Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并  
        }  
        tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf  
    }  
}  
int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    int b[10];  
    MergeSort(a, b, 10);  
    print(b,10);  
    cout<<"结果：";  
    print(a,10);  
}

两路归并的递归算法

void MSort(ElemType *r, ElemType *rf,int s, int t)  
{   
    ElemType *rf2;  
    if(s==t) r[s] = rf[s];  
    else  
    {   
        int m=(s+t)/2;          /*平分*p 表*/  
        MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
        MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
        Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
    }  
}  
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
{   /*对顺序表*p 作归并排序*/  
    MSort(r, rf,0, n-1);  
}

8 桶排序/基数排序(Radix Sort)及计数排序

说基数排序前，我们先说桶排序，桶排序是稳定的。

思想

将阵列分到有限数量的桶里，再对每个桶再个别排序（有可能再使用别的排序或以递回方式继续使用桶排序）。

当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间O(N)。但桶排序并非比较排序，他不受 O(NlogN) 下限的影响。

简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的再排序。例如要对大小为[1…1000]范围内的n个整数A[1…n]排序：

把桶设为大小为10的范围
设集合B[1]存储[1…10]的整数，集合B[2]存储 (10…20]的整数，……集合B[i]存储( (i-1)10, i10]的整数，i = 1,2,…100
总共有 100个桶
对A[1…n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中
再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择或快排
依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。

假设有n个数字,m个桶,如果数字均匀分布,则每个桶里面均有n/m个数

如果对每个桶中的数字采用快排,那么整个算法的复杂度是：

O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)

当m接近n时，桶排序复杂度接近O(n) 。

以上复杂度的计算基于输入的n个数字是均匀分布。该假设条件是很强的，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序。

前面说的几大排序算法，大部分时间复杂度都是O（n^2）,也有部分排序算法O(nlogn)

而桶式排序却能实现O（n）时间复杂度

但桶排序的缺点是

空间复杂度较高,额外开销大
排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间
待排序的元素都要在一定的范围内等等
桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较，但前提是要知道待排序列的一些具体情况

分配排序思想：说白了就是进行多次的桶式排序。

基数排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序

它们的时间复杂度可达到线性阶：O(n)

实例

扑克牌中52 张牌

2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

对扑克牌按花色、面值进行升排

即两张牌，若花色不同，不论面值怎样，花色低的那张牌小于花色高的，只有在同花色情况下，大小关系才由面值的大小确定。这就是多关键码排序。

为得到排序结果，我们讨论两种排序方法。

方法1：先对花色排序，将其分为4 个组,再对每组分别按面值排序,最后，4 组连接
方法2

先给出13 个编号组(2 号，3 号，…，A 号)，将牌按面值依次放入对应的编号组，分成13 堆

再按花色给出4 个编号组(梅花、方块、红心、黑心)，将2号组中牌取出分别放入对应花色组，再将3 号组中牌取出分别放入对应花色组，……，这样，4 个花色组中均按面值有序，然后，将4 个花色组依次连接起来即可

设n 个元素的待排序列包含d 个关键码{k1，k2，…，kd}，则称序列对关键码{k1，k2，…，kd}有序是

指：对于序列中任两个记录r[i]和rj都满足下列有序关系：

其中k1 称为最主位关键码，kd 称为最次位关键码。

两种多关键码排序方法：

多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：

最高位优先(Most Significant Digit first)法，简称MSD 法：

1）先按k1 排序分组，将序列分成若干子序列，同一组序列的记录中，关键码k1 相等。

2）再对各组按k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd 对各子组排序后。

3）再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

最低位优先(Least Significant Digit first)法，简称LSD 法：

先从kd 开始排序，再对kd-1进行排序，依次重复，直到按k1排序分组分成最小的子序列后。
最后将各个子序列连接起来，便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

基于LSD方法的链式基数排序的基本思想

“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。

基数排序（radixsort）

1887年赫尔曼·何乐礼发明。

基数排序属“分配式排序”（distributionsort），又称“桶子法”（bucketsort）或binsort，顾名思义，通过键值的各个位的值，将要排序的元素分配至某些“桶”，达到排序的作用。

基数排序法的是效率高的稳定性排序法，是桶排序的扩展。

基本思想

将整数按位数切割成不同的数字，然后按每个位数分别比较。

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

低位先排序，然后收集；再按高位排序，然后再收集；依次类推，直到最高位。

有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前

基数排序基于分别排序，分别收集，所以是稳定的。

代码实现

import java.util.Arrays;
public class BucketSort {
  /**
   * only for 0~200 value
   * @param arr
   */
  public static void bucketSort(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
      max = Math.max(max, arr[i]);
    }
    int[] bucket = new int[max + 1];
    for (int i = 0; i < arr.length; i++) {
      bucket[arr[i]]++;
    }
    int i = 0;
    for (int j = 0; j < bucket.length; j++) {
      while (bucket[j]-- > 0) {
        arr[i++] = j;
      }
    }
  }
  // for test
  public static void comparator(int[] arr) {
    Arrays.sort(arr);
  }
  // for test
  public static int[] generateRandomArray(int maxSize, int maxValue) {
    int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
    for (int i = 0; i < arr.length; i++) {
      arr[i] = (int) ((maxValue + 1) * Math.random());
    }
    return arr;
  }
  // for test
  public static int[] copyArray(int[] arr) {
    if (arr == null) {
      return null;
    }
    int[] res = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
      res[i] = arr[i];
    }
    return res;
  }
  // for test
  public static boolean isEqual(int[] arr1, int[] arr2) {
    if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
      return false;
    }
    if (arr1 == null && arr2 == null) {
      return true;
    }
    if (arr1.length != arr2.length) {
      return false;
    }
    for (int i = 0; i < arr1.length; i++) {
      if (arr1[i] != arr2[i]) {
        return false;
      }
    }
    return true;
  }
  // for test
  public static void printArray(int[] arr) {
    if (arr == null) {
      return;
    }
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
  // for test
  public static void main(String[] args) {
    int testTime = 500000;
    int maxSize = 100;
    int maxValue = 150;
    boolean succeed = true;
    for (int i = 0; i < testTime; i++) {
      int[] arr1 = generateRandomArray(maxSize, maxValue);
      int[] arr2 = copyArray(arr1);
      bucketSort(arr1);
      comparator(arr2);
      if (!isEqual(arr1, arr2)) {
        succeed = false;
        printArray(arr1);
        printArray(arr2);
        break;
      }
    }
    System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    int[] arr = generateRandomArray(maxSize, maxValue);
    printArray(arr);
    bucketSort(arr);
    printArray(arr);
  }
}

总结

各种排序的稳定性，时间复杂度和空间复杂度总结：

我们比较时间复杂度函数的情况：

                         时间复杂度函数O(n)的增长情况

所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。

时间复杂度来说：

(1)平方阶(O(n2))排序各类简单排序:直接插入、直接选择和冒泡排序； (2)线性对数阶(O(nlog2n))排序　快速排序、堆排序和归并排序； (3)O(n1+§))排序,§是介于0和1之间的常数。

希尔排序 (4)线性阶(O(n))排序基数排序，此外还有桶、箱排序。

说明：

当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；

原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

稳定性：

排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。

稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

选择排序算法准则：

每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。

选择排序算法的依据

影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：

待排序的记录数目n的大小；
记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
关键字的结构及其分布情况；
对排序稳定性的要求。

设待排序元素的个数为n.

**1）**当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

堆排序：如果内存空间允许且要求稳定性的，

归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

2）当n较大，内存空间允许，且要求稳定性 =》归并排序

3）当n较小，可采用直接插入或直接选择排序。

直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。
直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序

**5）**一般不使用或不直接使用传统的冒泡排序。

**6）**基数排序它是一种稳定的排序算法，但有一定的局限性：

　　1、关键字可分解。 2、记录的关键字位数较少，如果密集更好　　3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。

八大排序算法Java实现（下）-快排、归排、基数排序

6 交换排序—快速排序（Quick Sort）

基本思想

分析

快速排序的改进

7 归并排序(Merge Sort)

思想

合并方法

归并的迭代算法

两路归并的递归算法

8 桶排序/基数排序(Radix Sort)及计数排序

思想

基数排序（radixsort）

基本思想

代码实现

总结

热门文章

最新文章

相关课程

相关电子书

相关实验场景