Sort Algorithm

发表于 | 更新于: | 分类于 | | 阅读次数:
字数统计: 4,151 | 阅读时长 ≈ 17

以下内容并非本人全部原创，主要来自以下博客（如果有侵犯其他人权益，你找他们就行）：

概述

  • 内部排序：数据记录在内存中排序
  • 外部排序：内存不够用的情况下借助外存的排序

排序的种类

八大排序

  1. 插入排序
    • 直接插入排序
    • 希尔排序
  2. 选择排序
    • 简单选择排序
    • 堆排序
  3. 交换排序
    • 快速排序
    • 冒泡排序
  4. 基数排序(桶排序)
  5. 归并排序

排序种类

时间复杂度的算法：快速排序，堆排序，归并排序；在数据量大的时候，快速排序是目前公认的最好的排序算法，数据顺序越混乱平均时间越短，是非稳定排序

复杂度分析

biao1
biao2

插入排序

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

具体算法描述：

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

直接插入排序

要点：设立哨兵，用于临时存储和判断边界

示例：
shili

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insertSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int piv = nums[i];
        int j = i - 1;
        // nums[j] > piv 保证了排序是稳定的
        while (j >= 0 && nums[j] > piv) {
            nums[j + 1] = nums[j];
            j --;
        }
        nums[j + 1] = piv;
    }
}

插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，比如量级小于千，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

dongtu

二分插入

在查找时，使用二分查找，减少查找的时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void insertSortBin(vector<int>& nums){
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int piv = nums[i];
        int left = 0;
        int right = i - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (mid < piv) {
                left = mid + 1;
            }
            if (mid > piv) {
                right = mid - 1;
            }
        }
        for (int j = i - 1; j >= left; j--) {
            nums[j + 1] = nums[j];
        }
        nums[left] = piv;
    }
}

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

希尔排序

希尔排序又叫缩小增量排序

示例：
shili

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void shellInsertSort(vector<int>& nums, int dk) {
    int n = nums.size();
    for (int i = dk; i < n; i ++) {
        int piv = nums[i];
        int j = i - dk;
        while (j >= 0 && nums[j] > piv) {
            nums[j + dk] = nums[j];
            j -= dk;
        }
        nums[j + dk] = piv;
    }
}
void shellSort(vector<int>& nums) {
    int n = nums.size();
    dk = n / 2;
    while (dk) {
        shellInsertSort(nums, dk);
        dk / 2;
    }
}

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

选择排序

选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

　　注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

简单选择排序

基本思想：依次选出最小的数与排列靠前的数交换

示例：

shili

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void selectSort(vector<int>& nums) {
    int n = nums.size();
    
    for (int i = 0; i < n; i ++) {
        int k = i;
        for (int j = i + 1; j < n; j ++) {
            if (nums[j] < nums[k]) k = j;
        }
        if (k != i) {
            int tmp = nums[k];
            nums[k] = nums[i];
            nums[i] = tmp;
        }
    }
}

xx

改进——二元选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void selectionSortTwo(vector<int>& nums) {
    int n = nums.size();
    int left = 0;
    int right = n - 1;
    for (int i = 0; i < n / 2; i ++) {
        int min = left, max = left;
        
        for (int j = left + 1; j <= right; j++) {
            if (nums[j] > nums[max]) max = j;
            if (nums[j] < nums[min]) min = j;
        }
        int tmp = nums[right];
        nums[right] = nums[max];
        nums[max] = tmp;
        right --;
        tmp = nums[left];
        nums[left] = nums[min];
        nums[min] = tmp;
        left ++;
    }
}

堆排序

两个过程：建堆+取堆顶后重建

  • 建堆示例：

shili
shuoming

  • 取堆顶后重建示例：

shili

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
//最大堆
void adHeap(vector<int>& nums, int pos, int n) {
    int child = pos * 2 + 1;
    //int n = nums.size();
    
    while (child < n) {
        int tmp = nums[pos];
        if (child + 1 < n && nums[child] < nums[child + 1]) 
            ++ child;
        
        if (nums[child] > nums[pos]) {
            nums[pos] = nums[child];
            pos = child;
            child = 2 * s + 1;
        }
        else break;
        nums[pos] = tmp;
    }
}
void bulidHeap(vector<int>& nums) {
    int n = nums.size();
    for (int i = n / 2 - 1; i >= 0; -- i) {
        adHeap(nums, i);
    }
}
void heapSort(vector<int>& nums) {
    for (int i = nums.size() - 1; i >= 0; i --) {
        int tmp = nums[i]; nums[i] = nums[0]; nums[0] = tmp;
        adHeap(nums, 0, i + 1);
    }
}

设树的深度为。从根到叶的筛选，元素比较次数至多次，交换记录至多 次。所以，在建好堆后，排序过程中的筛选次数不超过下式：

交换排序

冒泡排序

两两比较，发现小号，往上冒泡

示例：

shili

1
2
3
4
5
6
7
8
9
10
11
12
void bubbleSort(vector<int>& nums) {
    int n = nums.size() - 1;
    for (int i = n; i >= 0; -- i) {
        for (int j = n; j >= i + 1; -- j) {
            if (nums[j - 1] > nums[j]) {
                int tmp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = tmp;
            }
        }
    }
}

xx

冒泡改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubbleSort_1(vector<int>& nums) {
    int n = nums.size() - 1;
    while(n > 0) {
        int pos = 0;
        for (int j = 0; j < n; j ++) {
            if (nums[j] > nums[j + 1]) {
                pos = j;
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
        n = pos;
    }
}

鸡尾酒排序

双向冒泡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void cockTailSort(vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left < right) {
        for (int i = left; i < right; i ++) {
            if (A[i] > A[i + 1]) {
                int tmp = A[i];
                A[i] = A[i + 1];
                A[i + 1] = tmp;
            }
        }
        right --;
        for (int i = right; i > left; i --) {
            if (A[i - 1] > A[i]) {
                int tmp = A[i - 1];
                A[i - 1] = A[i];
                A[i] = A[i - 1];
            }
        }
        left ++;
    }
}

快速排序

快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为：

  1. 从序列中挑出一个元素，作为”基准”(pivot).
  2. 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
  3. 对每个分区递归地进行步骤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
void quickSort(vector<int>& nums, int i, int j) {
    int piv = nums[left];
    int left = i;
    int idx = i;
    int right = j;
    while(i < j) {
        while(j  > i && piv < nums[j]) {
            j --;
        }
        if (j > i) {
            nums[i] = nums[j];
        }
        while(i < j && piv > nums[i]) {
            i ++;
        }    
        if (i < j) {
            nums[j] = nums[i];
        }
    }
    nums[i] = piv;
    quickSort(nums, left, i - 1);
    quickSort(nums, i + 1, right);
    
}

快速排序是不稳定的排序算法，不稳定发生在基准元素与A[tail+1]交换的时刻。

比如序列：{1, 3, 4, 2, 8, 9, 8, 7, 5}，基准元素是5，一次划分操作后5要和第一个8进行交换，从而改变了两个元素8的相对次序。

基数排序

基数排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：
实例:

扑克牌中52 张牌，可按花色和面值分成两个字段，其大小关系为：

花色： 梅花< 方块< 红心< 黑心
面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

若对扑克牌按花色、面值进行升序排序，得到如下序列：
0 1

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

为得到排序结果，我们讨论两种排序方法。
方法1：先对花色排序，将其分为4 个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序，最后，将4 个组连接起来即可。
方法2：先按13 个面值给出13 个编号组(2 号，3 号，…，A 号)，将牌按面值依次放入对应的编号组，分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心)，将2号组中牌取出分别放入对应花色组，再将3 号组中牌取出分别放入对应花色组，……，这样，4 个花色组中均按面值有序，然后，将4 个花色组依次连接起来即可。

设n 个元素的待排序列包含d 个关键码，则称序列对关键码${k_1, k_2, \cdots, k_d}$有序是指：对于序列中任两个记录r[i]和r[j]都满足下列有序关系：

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

两种多关键码排序方法：

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

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

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

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

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

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

  1. 先从 开始排序，再对进行排序，依次重复，直到按排序分组分成最小的子序列后。

  2. 最后将各个子序列连接起来，便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

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

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

基数排序:

是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

归并排序

归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。

归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作，归并操作步骤如下：

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾
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
// merge 函数
void mergeFunc(vector<int>& nums, int left, int mid, int right) {
	int i = left;
    int j = mid + 1;
    int n = right - left + 1;
    vector<int> tmp(n, 0);
    int k = 0;
    while (i <= mid && j <= right) {
    	if (nums[i] > nums[j]) {
        	tmp[k] = nums[j];
            j ++;
        }
        else {
        	tmp[k] = nums[i];
            i ++;
        }
        k ++;
    }
    while (i <= mid) {
        tmp[k] = nums[i];
        i ++;
        k ++;
    }
    while (j <= right) {
        tmp[k] = nums[j];
        j ++;
        k ++;
    }
    nums(tmp.begin(), tmp.end());
}
// 递归法
void mergeSortRecursion(vector<int>& nums, int left, int right) {
	if (left == right) return;
    int mid = (right - left) / 2;
    mergeSortRecursion(nums, left, mid);
    mergeSortRecursion(nums, mid + 1, right);
    mergeFunc(nums, left, mid, right);
}
// 迭代法
void mergeSortIter(vector<int>& nums) {
	int n = nums.size();
    int left, right;
    for (int i = 1; i < n; i *= 2) {
    	left = 0;
        while(left + i < n) {
        	int mid = left + i - 1;
        	right = mid + i < len ? mid + i : len - 1;
            mergeFunc(nums, left, mid, right);
            left = right + 1;
        }
    }
}

总结

时间复杂度：

  1. 平方阶排序
    　　各类简单排序:直接插入、直接选择和冒泡排序；
  2. 线性对数阶排序
    　　快速排序、堆排序和归并排序；
  3. 排序,是介于0和1之间的常数。
    希尔排序
  4. 线性阶排序
    　　基数排序，此外还有桶、箱排序。

说明：

当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至；
而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为；
原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

稳定性：

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

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

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

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

示意图

shell排序

shellSort

堆排序

heapSort

冒泡排序

bubbleSort

鸡尾酒排序

cockTailSort

快速排序

quickSort