经典排序算法总结

作者: 爱听故事的人想会讲故事 | 来源:发表于2017-07-10 17:00 被阅读0次

本文主要整理了九种经典的内部排序算法。

1.冒泡排序

原理：

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

步骤：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序.gif

实现：

 public static void sort(Comparable[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j].compareTo(arr[j+1]) > 0) {
                    swap(arr,j,j+1);
                }
            }
        }
    }

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

算法优化：

优化1：某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可。
优化2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。

2.选择排序

原理：

选择排序是一种简单直观的排序算法。

步骤：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。

选择排序.gif

实现：

public static void sort(Comparable[] arr ){
            int n=arr.length;
            for ( int i=0;i<n;i++){
                int minIndex =i;
                for ( int j=i+1;j<n;j++){
                    if (arr[j].compareTo( arr[minIndex])<0){
                        minIndex=j;
                    }
                    swap(arr,i,minIndex);
                }
            }
        }
private static void swap(Object[] arr, int i, int j ){
            Object t=arr[i];
            arr[i]=arr[j];
            arr[j]=t;
        }

3.插入排序

原理：

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

步骤：

从第一个元素开始，该元素可以认为已经被排序。

取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置后。
重复步骤2~5

插入排序.gif

实现：

 public static void sort(Comparable[] arr, int l, int r) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j>0; j--) {
                if (arr[j].compareTo(arr[j-1])<0){
                    swap( arr, j , j-1);
               }else
                    break;
          }
       }

4.希尔排序

原理：

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序（此时就是简单的插入排序了）。

步骤：

先取一个正整数 d1(d1 < n)，把全部记录分成 d1 个组，所有距离为 d1 的倍数的记录看成一组，然后在各组内进行插入排序。

然后取 d2(d2 < d1)。
重复上述分组和排序操作；直到取 di = 1(i >= 1) 位置，即所有记录成为一个组，最后对这个组进行插入排序。一般选 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。

希尔排序.gif

实现：

  public static void sort(Comparable[] arr){

        int n = arr.length;

        // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
        int h = 1;
        while (h < n/3) h = 3*h + 1;

        while (h >= 1) {  //控制按不同组距进行插入排序
            // h-sort the array
            for (int i = h; i < n; i++) {
                // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
                Comparable e = arr[i];
                int j = i;
                for ( ; j >= h && e.compareTo(arr[j-h]) < 0 ; j -= h)
                    arr[j] = arr[j-h];
                arr[j] = e;
            }
            h /= 3;
        }
    }

5.归并排序

原理：

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
归并操作(Merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。

步骤：

迭代法(自底向上)

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。

设定两个指针，最初位置分别为两个已经排序序列的起始位置。
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
重复步骤3直到某一指针到达序列尾。
将另一序列剩下的所有元素直接复制到合并序列尾。

递归法(自顶向下)

将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素。

将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
重复步骤2，直到所有元素排序完毕

归并排序.gif

实现：

迭代法

 private static void merge(Comparable[] arr, int l, int mid, int r) {
        Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid+1;
        for( int k = l ; k <= r; k ++ ){
            if( i > mid ){  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j-l]; j ++;
            }
            else if( j > r ){   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i-l]; i ++;
            }
            else if( aux[i-l].compareTo(aux[j-l]) < 0 ){  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i-l]; i ++;
            }
            else{  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j-l]; j ++;
            }
        }
    }

    public static void sort(Comparable[] arr){
        int n = arr.length;
        for (int sz = 1; sz < n; sz *= 2)
            for (int i = 0; i < n - sz; i += sz+sz) //sz+zs将i移到下一个分组
                // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
                merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1)); //当左后一个一组组长不足sz时将i+sz+sz-1与n-1进行比较

    }

递归法（自顶向下）

 // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private static void merge(Comparable[] arr, int l, int mid, int r){
        Comparable[] aux = Arrays.copyOfRange(arr, l,r+1);
        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l , j = mid + 1;
        for (int k = l; k <= r ; k++) {
            if( i > mid ){  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j-l]; j ++;
            }
            else if( j > r ){   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i-l]; i ++;
            }
            else if( aux[i-l].compareTo(aux[j-l]) < 0 ){  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i-l]; i ++;
            }
            else{  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j-l]; j ++;
            }
        }
    }

    private static void sort( Comparable[] arr , int l, int r){

        if (l >= r)
            return;
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid+1, r);
        merge(arr, l, mid, r);
    }

6.快速排序

原理：

快速排序，又称划分交换排序。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(nlogn)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤：

从数列中挑出一个元素，称为"基准"（pivot）。

重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序(1).gif

快速排序(2).gif

实现：

  private static int partition(Comparable[] arr, int l, int r){
        //随机在arr[l……r]范围中 选择一个数值作为标定点pivot，进行简单优化
        swap(arr, l ,(int)( Math.random()*( r - l + 1))+l);

        Comparable  copy = arr[l];
        int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
        for (int i = l+1 ; i <= r; i++) {
            if (arr[i].compareTo(copy) < 0) {
                j++;
                swap(arr, j, i);
            }
        }
            swap(arr, l, j);
            return j;
    }

    private static void swap(Object[] arr, int i, int j){
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    // 递归使用快速排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r){
        if ( l >= r)
            return;
        int p = partition(arr, l, r);
        sort(arr, l, p-1);
        sort(arr, p+1, r);
    }

算法优化

小数组时，切换到插入排序。对于小数组，快排比插入排序要慢；
三路快排，主要是对于有重复元素的情况下，将数组切分为三部分，分别是小于，等于和大于切分元素的数组元素。

 // 三路快排的实现
  private static void sort(Comparable[] arr, int l, int r){
        Comparable copy = arr[l];
        // 对于小规模数组, 使用插入排序
        if( r - l <= 15 ){
            InsertionSort.sort(arr,l,r);
            return;
        }
        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr , l ,(int)(Math.random() * (r - l + 1)) +1);

        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(copy)<0 ){
                swap(arr,i ,lt+1);
                i++;
                lt++;
            }
           else if ( arr[i].compareTo(copy)>0 ){
                swap( arr, i, gt-1);
                gt--;
            }
            else {
               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;
    }

7.堆排序

原理：

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

步骤：

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：

父节点i的左子节点在位置(2i+1);
父节点i的右子节点在位置(2i+2);
子节点i的父节点在位置floor((i-1)/2)。

在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：

最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

堆排序.gif

实现：

 public class HeapSort {
    private HeapSort() {}
    public static void sort(Comparable[] arr){
        int n = arr.length;
        for (int i = (n-1-1)/2; i >=0 ; i--) {
            shiftDown(arr, n ,i);
        }
        //依次取出最大元素放在数组最后，对剩下数据重新建立最大堆
        for (int i = n-1; i >0 ;i--) {
            swap(arr,0, i);
            shiftDown(arr, i, 0);
        }
    }
    // 交换堆中索引为i和j的两个元素
    private static void swap(Object[] arr, int i, int j){
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    private static void shiftDown(Comparable[] arr, int n, int k){
        while( 2*k+1 < n ){
            int j = 2*k+1;
            if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 )
                j += 1;
            if( arr[k].compareTo(arr[j]) >= 0 )break;
            swap( arr, k, j);
            k = j;
        }
    }

8.基数排序

原理：

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

步骤：

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。

从最低位开始，依次进行一次排序。
这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序.jpg

实现：

public class RadixSort
{
    public static void sort(int[] number, int d) //d表示最大的数有多少位
    {
        intk = 0;
        intn = 1;
        intm = 1; //控制键值排序依据在哪一位
        int[][]temp = newint[10][number.length]; //数组的第一维表示可能的余数0-9
        int[]order = newint[10]; //数组orderp[i]用来表示该位是i的数的个数
        while(m <= d)
        {
            for(inti = 0; i < number.length; i++)
            {
                intlsd = ((number[i] / n) % 10);
                temp[lsd][order[lsd]] = number[i];
                order[lsd]++;
            }
            for(inti = 0; i < 10; i++)
            {
                if(order[i] != 0)
                    for(intj = 0; j < order[i]; j++)
                    {
                        number[k] = temp[i][j];
                        k++;
                    }
                order[i] = 0;
            }
            n *= 10;
            k = 0;
            m++;
        }
    }
    public static void main(String[] args)
    {
        int[]data =
        {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
        RadixSort.sort(data, 3);
        for(inti = 0; i < data.length; i++)
        {
            System.out.print(data[i] + "");
        }
    }
}

9.计数排序

原理：

计数排序（Counting sort）是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

步骤：

找出待排序的数组中最大和最小的元素。

统计数组中每个值为i的元素出现的次数，存入数组 C 的第 i 项。
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）。
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

计数排序.gif

实现：

public class CountingSort {
    public static void main(String[] argv) {
        int[] A = CountingSort.countingSort(new int[]{16, 4, 10, 14, 7, 9, 3, 2, 8, 1});
        Utils.print(A);
    }

    public static int[] countingSort(int[] A) {
        int[] B = new int[A.length];
        // 假设A中的数据a'有，0<=a' && a' < k并且k=100
        int k = 100;
        countingSort(A, B, k);
        return B;
    }

    private static void countingSort(int[] A, int[] B, int k) {
        int[] C = new int[k];
        // 计数
        for (int j = 0; j < A.length; j++) {
            int a = A[j];
            C[a] += 1;
        }
        Utils.print(C);
        // 求计数和
        for (int i = 1; i < k; i++) {
            C[i] = C[i] + C[i - 1];
        }
        Utils.print(C);
        // 整理
        for (int j = A.length - 1; j >= 0; j--) {
            int a = A[j];
            B[C[a] - 1] = a;
            C[a] -= 1;
        }
    }
}


//针对c数组的大小，优化过的计数排序
public class CountSort{
    public static void main(String []args){
        //排序的数组
        int a[] = {100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 95};
        int b[] = countSort(a);
        for(int i : b){
            System.out.print(i + "  ");
        }
        System.out.println();
    }
    public static int[] countSort(int []a){
        int b[] = new int[a.length];
        int max = a[0], min = a[0];
        for(int i : a){
            if(i > max){
                max = i;
            }
            if(i < min){
                min = i;
            }
        }
        //这里k的大小是要排序的数组中，元素大小的极值差+1
        int k = max - min + 1;
        int c[] = new int[k];
        for(int i = 0; i < a.length; ++i){
            c[a[i]-min] += 1;//优化过的地方，减小了数组c的大小
        }
        for(int i = 1; i < c.length; ++i){
            c[i] = c[i] + c[i-1];
        }
        for(int i = a.length-1; i >= 0; --i){
            b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素
        }
        return b;
    }
}

各种排序算法比较复杂度比较

各种排序算法比较复杂度比较.png

参考文章

维基百科