C++ 数据结构与算法 （十一）（排序算法）

排序算法

排序简介 - OI Wiki
排序–全栈潇晨

排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。

（一）稳定性：

稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。
稳定的排序算法会让原本有相等键值的纪录维持相对次序。

1. 稳定排序：基数排序、计数排序、插入排序、冒泡排序、归并排序。

2. 不稳定排序：选择排序、堆排序、快速排序。

（二）复杂度：

基于比较的排序算法的时间复杂度下限是 O ( n l o g n ) O(n logn) O(nlogn) 的。
当然也有不是 O ( n l o g n ) O(n logn) O(nlogn) 的。例如，计数排序 的时间复杂度是 O ( n + w ) O(n+w) O(n+w) ，其中 w w w 代表输入数据的值域大小。

（三）存储器：

1. 内部排序： 待排序记录存放在计算机随机存储器中进行的排序过程；
2. 外部排序： 待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
   
   

1. 选择排序（Selection sort）

• 工作原理：每次找出第 i i i 小的元素（也就是 A A A_i…n 中最小的元素），然后将这个元素与数组第 i i i 个位置上的元素交换。
  
• 不稳定性：由于 swap（交换两个元素） *** 作的存在，选择排序是一种不稳定的排序算法。
• 时间复杂度：最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O ( n 2 ) O(n^2) O(n2)

#include 
using namespace std;

void sort(int* nums, int n){    // 数组指针  数组大小
    for(int i = 0; i < n; ++i){
        int min_index = i;
        for(int j = i+1; j < n; ++j){
            if(nums[j] < nums[min_index]) min_index = j;
        }
        swap(nums[i], nums[min_index]);
    }
}

int main(){
    int nums[] = {0,2,6,1,5,4,3,7};
    sort(nums, 8);  
    for(int num : nums){
        cout << num << endl;
    }
    return 0;
}

2. 冒泡排序（Bubble sort）

在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。

• 工作原理：
  每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。
  
  经过 i i i 次扫描后，数列的末尾 i i i 项必然是最大的 i i i 项，因此冒泡排序最多需要扫描 n − 1 n-1 n−1遍数组就能完成排序。
• 稳定性：
  冒泡排序是稳定排序算法。
• 时间复杂度：
  在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换 *** 作，时间复杂度为 O ( n ) O(n) O(n)。
  在最坏情况下，冒泡排序要执行 ( n − 1 ) n / 2 (n-1)n/2 (n−1)n/2 次交换 *** 作，时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
  冒泡排序的平均时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

#include 
using namespace std;

void sort(int* nums, int n){                // 数组指针  数组大小
    for(int j = 0; j < n; ++j){             // 大循环遍历（最多n-1次）
        bool flag = true;   
        for(int i = 1; i < n; ++i){
            if(nums[i] < nums[i-1]){        // 相邻两个元素逐一比较
                swap(nums[i], nums[i-1]);
                flag = false;
            }
        }
        if(flag == true) break;             // true 为当前遍历未发生交换
    }    
}

int main(){
    int nums[] = {0,2,6,1,5,4,3,7};
    sort(nums, 8);  
    for(int num : nums){
        cout << num << endl;
    }
    return 0;
}

3. 插入排序（Insertion sort）

• 工作原理：
  将待排列元素划分为“已排序”和“未排序”两部分，每次从“未排序的”元素中选择一个插入到“已排序的”元素中的正确位置。
  
• 稳定性：
  插入排序是稳定的排序算法。
• 时间复杂度：
  插入排序的最优时间复杂度为 O ( n ) O(n) O(n)，在数列几乎有序时效率很高。
  插入排序的最坏时间复杂度和平均时间复杂度都为 O ( n 2 ) O(n^2) O(n2)。

// insertion sort

#include 
using namespace std;

void sort(int* nums, int n){                // 数组指针  数组大小
    for(int i = 1; i < n; ++i){ 
        int curr = nums[i];                 // 当前需要插入的元素
        for(int j = i-1; j >= 0; --j){      // 从后往前遍历已排序部分
            if(nums[j] > curr){             
                nums[j+1] = nums[j];        // 更大元素后移
            }else{
                nums[j+1] = curr;           // 插入正确位置
                break;
            }  
        }
    }
}

int main(){
    int nums[] = {0,2,6,1,5,4,3,7};
    int ans[] = {0,1,2,3,4,5,6,7};
    int n = 8;
    sort(nums, n);      // 排序
    bool result = true;
    for(int i = 0; i < n; ++i){
        if(nums[i] != ans[i]) result = false;
        cout << nums[i] << endl;
    }
    cout << "result is: " << result << endl;
    return 0;
}

4. 希尔排序（Shell sort）

也称为缩小增量排序法，是 插入排序 的一种改进版本。

• 工作原理：对不相邻的记录进行比较和移动
  （1）将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
  （2）对这些子序列进行插入排序；
  （3）减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。
• 不稳定性：
  希尔排序是不稳定的排序算法。
• 复杂度：
  （1）时间复杂度：最优时间复杂度为 O ( n ) O(n) O(n)；
  平均时间复杂度和最坏时间复杂度与间距序列的选取（就是间距如何减小到 1）有关，比如「间距每次除以 3」的希尔排序的时间复杂度是 O ( n 3 / 2 ) O(n^{3/2}) O(n3/2)。已知最好的最坏时间复杂度为 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n) 。
  （2）空间复杂度为 O ( 1 ) O(1) O(1)。
  https://www.runoob.com/w3cnote/shell-sort.html
  https://baijiahao.baidu.com/s?id=1707870928646769729&wfr=spider&for=pc
  https://www.runoob.com/data-structures/shell-sort.html

5. 归并排序 6. 快速排序 7. 堆排序 8. 计数排序（Counting sort）

• 工作原理：
  使用一个额外的数组 C C C，其中第 i i i 个元素是待排序数组 A A A 中值等于 i i i 的元素的个数，然后根据数组 C C C 来将 A A A 中的元素排到正确的位置。
  
• 工作步骤：
  1.计算每个数出现的次数；
  2.求出每个数出现次数的 前缀和；
  3.利用出现次数的前缀和，从右至左计算每个数的排名。
• 稳定性：
  计数排序是一种稳定的排序算法。
• 复杂度：
  时间复杂度为 O ( n + w ) O(n+w) O(n+w)，
  空间复杂度为 O ( w ) O(w) O(w)，其中 w w w 代表待排序数据的值域大小。
• 局限性：
  （1）当数列最大最小值差距**（值域）过大时，会造成空间浪费**，并不适用于计数排序；
  （2）当数列元素不是整数时，无法创建对应的统计数组，并不适用于计数排序。

// Counting sort

#include 
using namespace std;

void sort(int* nums, int n){     // 数组指针  数组大小
    int min = nums[0];
    int max = nums[0];
    for(int i = 1; i < n; ++i){ // 确定数值最大最小值，确定值域大小
        if(nums[i] > max) max = nums[i];
        if(nums[i] < min) min = nums[i];
    }
    int w = max - min +1;       // 值域大小
    int cnt[w] = {0};           // 统计数组
    for(int i = 0; i < n; ++i) ++cnt[nums[i]-min];  // cnt数组统计每个数值出现的次数
    int index = 0;
    for(int i = 0; i < w; ++i){ // 根据数值个数进行排序
        while(cnt[i] > 0){
            nums[index] = i + min;  // 偏置
            --cnt[i];
            ++index;
        }
    }
}

int main(){
    int nums[] = {0,2,6,1,5,7,4,3,7};
    int ans[] = {0,1,2,3,4,5,6,7,7};
    int n = 9;
    sort(nums, n);      // 排序
    bool result = true;
    for(int i = 0; i < n; ++i){
        if(nums[i] != ans[i]) result = false;
        cout << nums[i] << endl;
    }
    cout << "result is: " << result << endl;
    return 0;
}

9. 桶排序 10. 基数排序（Radix sort）

一种非比较型的排序算法，最早用于解决卡片排序的问题。

• 工作原理：
  将待排序的元素拆分为 k k k 个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第 k k k 关键字进行稳定排序，再对第 k − 1 k-1 k−1 关键字进行稳定排序，再对第 k − 2 k-2 k−2 关键字进行稳定排序……最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。
  基数排序需要借助一种 稳定算法 完成内层对关键字的排序。
• 稳定性：
  基数排序是一种稳定排序算法。
• 复杂度：
  （1）时间复杂度
  （2）空间复杂度
• 说明：
  通常而言，基数排序比基于比较的排序算法（比如快速排序）要快。但由于需要额外的内存空间，因此当内存空间稀缺时，原地置换算法（比如快速排序）或许是个更好的选择。

https://blog.csdn.net/sinat_31275315/article/details/107866337
https://blog.csdn.net/qq_35423154/article/details/109125235
https://www.runoob.com/w3cnote/radix-sort.html

11. 锦标赛排序 12. 排序相关 STL 13. 排序应用