排序算法是《数据结构与算法》中最基本的算法之一。
十种常见排序算法可以分为两大类：
- 比较类排序：通过比较来决定元素间的相对次序，时间复杂度为 O(nlogn)～O(n²)。
- 非比较类排序：不通过比较来决定元素间的相对次序，其时间复杂度可以突破 O(nlogn)，以线性时间运行。
【十大经典排序算法分类】
【十大经典排序算法的复杂度分析】
名词解释：
时间/空间复杂度：描述一个算法执行时间/占用空间与数据规模的增长关系。
n：待排序列的个数。
k：“桶”的个数（上面的三种非比较类排序都是基于“桶”的思想实现的）。
In-place：原地算法，指的是占用常量内存，不占用额外内存。即空间复杂度为 O(1) 。
Out-place：非原地算法，占用额外内存。
稳定性：假设待排序列中两元素相等，排序前后这两个相等元素的相对位置不变，则认为是稳定的。
一、桶排序（Bucket-Sort）
桶排序 （Bucket sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
1.1、算法描述
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来。
1.2、动图演示
桶排序动图演示
1.3、C++编码
/**
* @version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved
* @file BucketSort.hpp
* @brief 桶排序
* @autor 写代码的小恐龙er
* @date 2024/03/07
*/
// 【分治法】
// 时间复杂度O(n + k)
// 空间复杂度O(n + k)
void BucketSort(int arr[], int n, int r) {
if (arr == NULL || r < 1) return;
// 根据最大/最小元素和桶数量，计算出每个桶对应的元素范围
int max = arr[0], min = arr[0];
int i, j;
for (i = 1; i < n; i++) {
if (max < arr[i]) max = arr[i];
if (min > arr[i]) min = arr[i];
}
// 防止数据溢出 将桶个数加1[如： max - min + 1 = 10; r = 3; 则需要四个桶]
int range = (max - min + 1) / r++;
// 建立桶对应的二维数组，一个桶里最多可能出现 n 个元素
vector<vector<int>> buckets(r, vector<int>(n, 0));
vector<int> counts(n, 0);
for (i = 0; i < n; i++) {
int k = (arr[i] - min) / range;
buckets[k][counts[k]++] = arr[i];
}
int index = 0;
for (i = 0; i < r; i++) {
// 分别对每个非空桶内数据进行排序，比如计数排序
if (counts[i] == 0) continue;
sort(buckets[i].begin(), buckets[i].begin() + counts[i]);
//counting_sort(buckets[i], counts[i]);
// 拼接非空的桶内数据，得到最终的结果
for (j = 0; j < counts[i]; j++) {
arr[index++] = buckets[i][j];
}
}
}
1.4 、算法分析
桶排序是稳定排序，但仅限于桶排序本身，假如桶内排序采用了快速排序之类的非稳定排序，那么就是不稳定的。
二、基数排序（Radix Sort）
基数排序（Radix Sort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
2.1 、算法描述
- 取得数组中的最大数，并取得位数；
- arr 为原始数组，从最低位开始取每个位组成 radix 数组；
- 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）。
2.2 、动图演示
基数排序动图演示
2.3、C++编码
/**
* @version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved
* @file RadixSort.hpp
* @brief 基数排序
* @autor 写代码的小恐龙er
* @date 2024/03/07
*/
// 【分治法】
// 时间复杂度O(n * k)
// 空间复杂度O(n + k)
// 基数，范围0~9
#define RADIX 10
void RadixSort(int arr[], int n) {
// 获取最大值和最小值
int max = arr[0], min = arr[0];
int i, j, l;
for (i = 1; i < n; i++) {
if (max < arr[i]) max = arr[i];
if (min > arr[i]) min = arr[i];
}
// 假如序列中有负数，所有数加上一个常数，使序列中所有值变成正数
if (min < 0) {
for (i = 0; i < n; i++) arr[i] -= min;
max -= min;
}
// 获取最大值位数
int d = 0;
while (max > 0) {
max /= RADIX;
d ++;
}
vector<vector<int>> queue(RADIX, vector<int>(n, 0);
int count[RADIX] = {0};
for (i = 0; i < d; i++) {
// 分配数据
for (j = 0; j < n; j++) {
// 依次从个位到最高位取出数值
int key = arr[j] % (int)pow(RADIX, i + 1) / (int)pow(RADIX, i);
// 放置到对应位数的数组中， 同时 count[key]++ 是为了 记录 位数相同的值 的个数
queue[key][count[key]++] = arr[j];
}
// 收集数据
int c = 0;
// 依次将各个基数数组中的值排列起来
for (j = 0; j < RADIX; j++) {
for (l = 0; l < count[j]; l++) {
arr[c++] = queue[j][l];
queue[j][l] = 0;
}
count[j] = 0;
}
}
// 假如序列中有负数，收集排序结果时再减去前面加上的常数
if (min < 0) {
for (i = 0; i < n; i++) arr[i] += min;
}
}2.4 、算法分析
基数排序是稳定排序，适用于关键字取值范围固定的排序。
