Fork me on GitHub

常用排序算法

发表于 | | 阅读次数:

我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

排序算法答题可分为两种：

  • 一种是比较排序，时间复杂度O(nlogn)~ O(n^2)，主要有：冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。
  • 一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序,基数排序,桶排序等。
排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
简单选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
直接插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(nlogn)~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)~O(n) 不稳定

有一点我们很容量忽略的是排序算法的稳定性。
    排序算法稳定性的简单形式化定义为: 如果Ai= Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。
    对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
    例如，对于冒泡排序，原本是稳定的排序算法，如果将记录交换的条件改成A[i]>=A[i+ 1]，则两个相等的记录就会交换位置，从而编程不稳定的排序算法。
    其次，说一下排序算法稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位排序后元素的顺序在高位也相同时是不会改变的。

冒泡排序

    冒泡排序是一种极其简单的排序算法。它重复地走访过要排序的元素，依次比较相邻两个元素，如果它们的顺序错误就把它们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢”浮”到数列的顶端。
    冒泡排序算法的运作如下：

  • 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素回事最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一堆数字需要比较。

    由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。冒泡排序的代码如下:

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4};
    for(int i= 0, len= A.length- 1; i< len; i++){
        for(int j= 0, lens= A.length- 1- i; j< lens; j++){
            if(A[j]> A[j+ 1]){
                int temp= A[j];
                A[j]= A[j+ 1];
                A[j+ 1]= temp;
            }
        }
    }
    for(int i= 0, len= A.length; i< len; i++){
        System.out.print(A[i]+ (i== (len- 1)? "": " "));
    }
}

上述代码对序列{6, 5, 3, 1, 8, 7, 2, 4}进行冒泡排序的实现过程如下:
1

冒泡排序的改进: 鸡尾酒排序

    鸡尾酒排序，也叫定向冒泡排序，是冒泡排序的一种改进。此算法与冒泡排序的不同之处在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。它可以得到此冒泡排序稍微好一点的效能。
    鸡尾酒排序的代码如下:

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static void main(String[] args) {
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };
    int i, temp;
    int left= 0, right= A.length- 1, length= A.length;
    while (left< right){
        for(i= left; i< right; i++){
            if(A[i]> A[i+ 1]){
                temp= A[i];
                A[i]= A[i+ 1];
                A[i+ 1]= temp;
            }
        }
        right--;
        for(i= right; i> left; i--){
            if(A[i- 1]> A[i]){
                temp= A[i- 1];
                A[i- 1]= A[i];
                A[i]= temp;
            }
        }
        left++;
    }
    for(i= 0; i<= length- 1; i++){
        System.out.print(A[i]+ (i== (length- 1)? "": " "));
    }
}

    使用鸡尾酒排序为一列数字进行排序的过程如下图所示:
2
    以序列{2, 3, 4, 5, 1}为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。但是在乱数序列的状态下，鸡尾酒排序与冒泡排序的效率都很差劲。

选择排序

    选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小(大)元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小(最大)元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
    注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小(大)元素放到合适的位置；而选择排序每遍历一次都记住了当前最小(大)元素的位置，最后仅需一次交换操作即可将其放到合适的位置。
    选择排序的代码如下:

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void main(String[] args) {
    int A[] = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7};
    int i, j, temp;
    int length= A.length;
    
    for(i= 0; i< length- 1; i++){
        int k= i;
        for(j= k+ 1; j< length; j++){
            if(A[j]< A[k]){
                //记下目前找到的最小值所在的位置
                k= j;
            }
        }
        if(i!= k){
            temp= A[i];
            A[i]= A[k];
            A[k]= temp;
        }
    }
    for(i= 0; i<= length- 1; i++){
        System.out.print(A[i]+ (i== (length- 1)? "": " "));
    }
}

上述代码对序列{ 8, 5, 2, 6, 9, 3, 1, 4, 0, 7}进行选择排序的实现过程如下图:
3
    使用选择排序为一列数字进行排序的宏观过程。
4
选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。
比如序列: {5, 8, 5, 2, 9}，一次选择的最小元素是2，然后把2和第一个5进行交换，从而改变了两个元素5的相对次序。

插入排序

    插入排序是一种简单直观的排序算法。它的工作原理非常类似于我们抓扑克牌。
对于未排序数据(新抓到的牌)，在已排序序列(排好序的手牌)中从后向前扫描，找到相应位置并插入。
    插入排序在实现上，通常采用in-place排序(即只需用到O(1)的额外空间的排序)，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
具体算法描述如下:

  • 从第一个元素开始，该元素可以认为已经被排序。
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描。
  • 如果该元素(已排序)大于新元素，将该元素移到下一位置。
  • 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
  • 将新元素插入到该位置后
  • 重复步骤2~5

插入排序的代码如下:

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4};
    int i, j, temp;
    int length= A.length;
    for(i= 1; i< length; i++){
        for(j= i; j> 0&& A[j]< A[j- 1]; j--){
            temp= A[j];
            A[j]= A[j- 1];
            A[j- 1]= temp;
        }
    }
    for(i= 0; i<= length- 1; i++){
        System.out.print(A[i]+ (i== (length- 1)? "": " "));
    }
}

    上述代码对序列{6, 5, 3, 1, 8, 7, 2, 4}进行插入排序的实现过程如下:
5
    使用插入排序为一列数字进行排序的宏观过程:
6
    插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，比如量级小于千，那么插入排序还是一个不错的选择。插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序(通常为8个或以下)。

插入排序的改进: 二分插入排序

    对于插入排序，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的次数，我们称为二分插入排序。代码如下:

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void main(String[] args) {
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4};
    int i, j, temp;
    int length= A.length;
    for(i= 1; i< length; i++){
        //抓到一张扑克牌
        int get= A[i];
        //手牌是排好序的，可以用二分法
        int left= 0;
        //手牌左右边界进行初始化
        int right= i- 1;
        //采用二分法定位新牌的位置
        while (left<= right){
            int mid= (left+ right)/ 2;
            if(A[mid]> get){
                right= mid- 1;
            }else {
                left= mid+ 1;
            }
        }
        //将欲插入新牌位置右边的牌整体向右移动一个单位
        for(j= i- 1; j>= left; j--){
            A[j+ 1]= A[j];
        }
        //将抓到的牌插入手牌
        A[left]= get;
    }
    for(i= 0; i<= length- 1; i++){
        System.out.print(A[i]+ (i== (length- 1)? "": " "));
    }
}

    当长度较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所以当元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。

插入排序的更高效改进: 希尔排序

    希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。
    希尔排序是基于插入排序的以下两点性值而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

    希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排号的了(此时插入排序较快)。
    假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n^2)的排序(冒泡排序或直接插入排序)，可能会进行n次的比较和交换才能将该数据迁移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
    希尔排序的代码如下:

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void main(String[] args) {
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4};
    int i, j, temp;
    int length= A.length;
    int h= 0;
    while (h<= length){
        h= h* 3+ 1;
    }
    while (h>= 1){
        for(i= h; i< length; i++){
            j= i- h;
            int get= A[i];
            while (j>= 0&& A[j]> get){
                A[j+ h]= A[j];
                j= j- h;
            }
            A[j+ h]= get;
        }
        h= (h- 1)/ 3;
    }
    for(i= 0; i<= length- 1; i++){
        System.out.print(A[i]+ (i== (length- 1)? "": " "));
    }
}

7
    希尔排序是不稳定的排序算法，虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。
    比如序列: {3, 5, 10, 8, 7, 2, 8, 1, 20, 6}，h= 2时分成两个子序列{3, 10, 7, 8, 20}和{5, 8, 2, 1, 6}，未排序之前第二个子序列中的8在前面，限制对两个子序列进行插入排序，得到{3, 7, 8, 10, 20}和{1, 2, 5, 6, 8}，即{3, 1, 7, 2, 8, 5, 10, 6, 20, 8}，两个8的相对次序发生了改变。

归并排序

    归并排序是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)，1945年由冯·诺伊曼首次提出。
    归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。
    归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作，归并操作步骤如下:

  • 申请空间，使其大小为两个已经排好序序列之和，该空间用来存放合并后的序列。
  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置。
  • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
  • 重复步骤3，直到某一指针到达序列尾。
  • 将另一序列剩下的所有元素直接赋值到合并序列尾。

归并排序的代码如下:

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}

8
    使用归并排序为一列数字进行排序的宏观过程:
9
    归并排序除了可以对数组进行排序，还可以高效的求出数组之和(即单调和)以及数组中的逆序对。

堆排序

    堆排序是指利用这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构(通常堆是通过一维数组来实现的)，并满足性质: 以最大堆(也叫大根堆、大顶堆)为例，其中父节点的值总是大于它的孩子节点。
    我们可以很容易的定义堆排序的过程:

  • 由输入的无序数组构造一个最大堆，作为初始的无序区。
  • 把堆顶元素(最大值)和堆尾元素互换。
  • 把堆(无序区)的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整。
  • 重复步骤2，直到堆的尺寸为1

堆排序的代码如下:

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public static void main(String[] args) {
    int A[] = {6, 5, 3, 1, 8, 7, 2, 4};
    int i, j, temp;
    int length = A.length;
    int h = 0;
    HeapSort(A, length);
    for(i= 0; i<= length- 1; i++){
        System.out.print(A[i]+ (i== (length- 1)? "": " "));
    }
}
static void Swap(int A[], int i, int j) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
// 从A[i]向下进行堆调整
static void Heapify(int A[], int i, int size)
{
    // 左孩子索引
    int left_child = 2 * i + 1;
    // 右孩子索引
    int right_child = 2 * i + 2;
    // 选出当前结点与其左右孩子三者之中的最大值
    int max = i;
    if (left_child < size && A[left_child] > A[max]) {
        max = left_child;
    }
    if (right_child < size && A[right_child] > A[max]) {
        max = right_child;
    }
    if (max != i) {
        // 把当前结点和它的最大(直接)子节点进行交换
        Swap(A, i, max);
        // 递归调用，继续从当前结点向下进行堆调整
        Heapify(A, max, size);
    }
}
// 建堆，时间复杂度O(n)
static int BuildHeap(int A[], int n)
{
    int heap_size = n;
    // 从每一个非叶结点开始向下进行堆调整
    for (int i = heap_size / 2 - 1; i >= 0; i--){
        Heapify(A, i, heap_size);
    }
    return heap_size;
}
static void HeapSort(int A[], int n) {
    // 建立一个最大堆
    int heap_size = BuildHeap(A, n);
    // 堆（无序区）元素个数大于1，未完成排序
    while (heap_size > 1){
        // 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素
        // 此处交换操作很有可能把后面元素的稳定性打乱，所以堆排序是不稳定的排序算法
        Swap(A, 0, --heap_size);
        // 从新的堆顶元素开始向下进行堆调整，时间复杂度O(logn)
        Heapify(A, 0, heap_size);
    }
}

堆排序算法的演示:
10
    动画中在排序过程之前简单的表现了创建堆的过程以及堆的逻辑结构。
堆排序是不稳定的排序算法，不稳定发生在堆顶元素与A[i]交换的时刻。
    比如序列: {9, 5, 7, 5}，堆顶元素是9，堆排序下一步将9和第二个5进行交换，得到序列{5, 5, 7, 9}，再进行堆调整得到{7, 5, 5, 9}，重复之前的操作最后得到{5, 5, 7, 9}从而改变了两个5的相对次序。

快速排序

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。
    快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为:

  • 从序列中挑出一个元素，作为”基准”。
  • 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面(相同的数可以到任一边)，这个称为分区操作。
  • 对每个分区递归进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

快速排序的代码如下:

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Test_2 {
    public static void main(String[] args) {
        int A[] = {6, 5, 3, 1, 8, 7, 2, 4};
        int i, j, temp;
        int length = A.length;
        int h = 0;
        QuickSort(A, 0, length- 1);
        for(i= 0; i<= length- 1; i++){
            System.out.print(A[i]+ (i== (length- 1)? "": " "));
        }
    }
    static void Swap(int A[], int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
    // 划分函数
    static int Partition(int A[], int left, int right)
    {
        // 这里每次都选择最后一个元素作为基准
        int pivot = A[right];
        // tail为小于基准的子数组最后一个元素的索引
        int tail = left - 1;
        // 遍历基准以外的其他元素
        for (int i = left; i < right; i++)
        {
            // 把小于等于基准的元素放到前一个子数组末尾
            if (A[i] <= pivot)
            {
                Swap(A, ++tail, i);
            }
        }
        // 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组
        Swap(A, tail + 1, right);
        // 该操作很有可能把后面元素的稳定性打乱，所以快速排序是不稳定的排序算法
        // 返回基准的索引
        return tail + 1;
    }
    static void QuickSort(int A[], int left, int right)
    {
        if (left >= right) {
            return;
        }
        // 基准的索引
        int pivot_index = Partition(A, left, right);
        QuickSort(A, left, pivot_index - 1);
        QuickSort(A, pivot_index + 1, right);
    }
}

    使用快速排序法对一列数字进行排序的过程:
11
快速排序是不稳定的排序算法，不稳定发生在基准元素与A[tail+1]交换的时刻。
    比如序列: {1, 3, 4, 2, 8, 9, 8, 7, 5}，基准元素是5，一次划分操作后5要和第一个8进行交换，从而改变了两个元素8的相对次序。

Java系统提供的Arrays.sort函数。对于基础类型，底层使用快速排序。对于非基础类型，底层使用归并排序。请问是为什么？

答：这是考虑到排序算法的稳定性。对于基础类型，相同值是无差别的，排序前后相同值的相对位置并不重要，所以选择更为高效的快速排序，尽管它不是稳定的排序算法；而对于非基础类型，排序前后相等实例的相对位置不宜改变，所以选择稳定的归并排序。

Your support will encourage me to continue to create!