简介
之前介绍的7种常见排序算法，它们都是比较排序，也就是有if(arr[i] > arr[j])的比较过程。
接下来要介绍3种非比较排序，其本质在于将数组元素映射到自带参考坐标系中，从某种意义上讲，是提前帮你比较好了。因此通常情况下，非比较排序效率比比较排序要高。
不一样的思路：计数排序
统计每种元素出现的次数，进而推算出每个元素在排序后数组中的索引位置，最终完成排序。
原理
计数排序的原理比较简单
- 找出待排序数组中的最大值max和最小值min
确定计数数组的长度范围，为后续统计元素出现次数做准备。 - 统计每个元素出现的次数
创建一个长度为max - min + 1的计数数组count，遍历待排序数组，以元素值与最小值的差值作为计数数组的索引，对应位置的值加 1，记录每个元素出现的次数。 - 对计数数组进行累加
从计数数组的第二个元素开始，将当前元素的值加上前一个元素的值。这样，计数数组中每个位置的值表示小于等于该位置对应元素的元素个数，为确定元素在排序后数组中的位置提供依据。 - 将元素放入排序后的数组
创建一个与待排序数组长度相同的结果数组result，从后往前遍历待排序数组，根据元素值与最小值的差值在计数数组中找到其位置，将元素放入结果数组的相应位置，同时将计数数组中对应位置的值减 1。
实现
void Sort(int[] nums) { //最大值和最小值 int max = int.MinValue, min = int.MaxValue; foreach (int element in nums) { max= Math.Max(max, element); min = Math.Min(min, element); } //根据max min 推断出需要创建多大的temp数组 int offset = -min; var temp = new int[max - min + 1]; //统计数组元素出现的个数 foreach (int element in nums) { temp[element+offset]++; } //对计数数组进行累加 for (int i = 1; i < temp.Length; i++) { temp[i] += temp[i - 1]; } var sort = new int[nums.Length]; for (int i = nums.Length - 1;i>= 0; i--) { sort[temp[nums[i] + offset] - 1] = nums[i]; temp[nums[i] + offset]--; } for(int i = 0; i < nums.Length; i++) { nums[i] = sort[i]; } } 复杂度分析
- 时间复杂度
O(n+k)，n是数组长度，k是元素的取值范围(max-min+1) - 空间复杂度
O(k)，这点比较伤，因为是利用数组的特性。所以取值范围多大，k就有多大。要万一是0，999。那就要创建int[1000]的空间。 - 排序稳定性
在将元素放入排序后的数组时，从后往前遍历待排序数组，保证了相等元素的相对顺序不变。 - 原地排序
很明显不是。它需要temp数组来辅助。
桶排序
桶排序的思路非常简单，但应用范围也非常广，它的底层逻辑实际上就是分而治之。把待排序的元素切割到若干个桶中分别排序，然后再合并起来。
有点类似归并排序，都是把大数组进行切割。因此桶排序不是一种限定逻辑的算法，它是一种思想。因此实现对每个桶可以自选算法。
原理
- 确定桶的数量和范围
根据待排序数组的最大值、最小值以及数据分布情况，确定桶的数量和每个桶所表示的数值范围，并提供一个映射函数 - 将元素分配到桶中
遍历待排序数组，根据元素的值将其放入对应的桶中。 - 对每个桶内的元素进行排序
可以使用其他排序算法（如插入排序、快速排序等）对每个桶内的元素进行排序。
一般来说会选择插入排序，因为插入排序属于比较简单的稳定排序算法。在几个O(n^2)的算法中，比较综合。 - 合并所有桶中的元素
按照桶的顺序，依次将每个桶中的元素取出，合并成一个有序的数组。
如何将桶合并？虽然有一个合并数组的通用算法,但需要用到二叉堆，且复杂度为O(n*log k)。不符合不超过O(N)的要求
实现
public static void Run() { int[] arr = new int[] { 1,30, 22, 94, 71, 47, 88, 25, -3, 73, 58, 4, 37,1, 16, 92, 61, -86, 77, 13, 27, 74, 64, -44, 9, 34, -53, -19, -81, 29, 57, 42, 67, 12, 83, 20, 51, 49, 6, 32, 79, 50, 70, 15, 85, 23, 56, 45, 8, 35, 76, 52, 69, 11, 84, 24, 55, 48, 7, 33, 78, 54, 68, 10, 82, 21, 59, 46, 1, 31, 75, 5, 66, 14, 87, 26, 60, 43, 0, 36, 72, -3, 40, 17, 90, 28, 62, 41, 2, 39, -3, 65, 18, 91, 38, 93, -3, 96, 97, 98, 99 }; new BucketSort().Sort(arr, 2); foreach (var item in arr) { Console.WriteLine(item); } } public void Sort(int[] nums,int bucketCount) { int min=int.MaxValue,max=int.MinValue; foreach(int i in nums) { min=Math.Min(min,i); max=Math.Max(max,i); } int offset = -min; //计算出每个桶的大小 int bucketSize = (max - min) / bucketCount + 1; //初始化桶 List<int>[] buckets = new List<int>[bucketCount]; for(int i = 0; i < bucketCount; i++) { buckets[i] = new List<int>(bucketSize); } //分配元素 foreach(int num in nums) { //用除法向下取整计算桶的索引 var bucketIndex = (num + offset) / bucketSize; buckets[bucketIndex].Add(num); } //对每个桶元素进行排序 //分而治之的魅力，就是可以利用多个线程。 Parallel.For(0, bucketCount, i => { InsertSort(buckets[i]); }); //合并有序桶 int idx = 0; for (int i = 0; i < buckets.Length; i++) { foreach (var item in buckets[i]) { nums[idx] = item; idx++; } } } public void InsertSort(List<int> arr) { for (int i = 0; i < arr.Count; i++) { for(int j = i; j > 0; j--) { if (arr[j] < arr[j - 1]) { //swap (arr[j], arr[j - 1]) = (arr[j - 1], arr[j]); } else { break; } } } } 复杂度分析
- 时间复杂度
桶排序的时间复杂度主要取决于算法的选择，不同算法复杂度不同。均摊下来O(n+k)，其中 n 是待排序数组的长度，k 是桶的数量，最坏情况下O(n^2)。 - 空间复杂度
同上，主要用于存储桶和桶内的元素。需要额外的 n 个空间来存储所有元素，以及 k 个桶的空间。 - 排序稳定性
同上，也取决于算法的选择。 - 原地排序
看代码，很明显不是。
计数的拓展：基数排序
其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。它通过多轮排序，从最低位到最高位，逐步确定元素的顺序。
原理
同计数排序
1. 一个无需的数组 468 004 766 222 2. 先按个数排序 222 004 766 468 3. 再按十位数排序 004 222 766 468 4. 再按百位数排序 004 222 766 468 实现
public static void Run() { var arr = new int[] { 468, 004, 766, 222 }; new RadixSort().Sort(arr); foreach (var item in arr) { Console.WriteLine(item); } } public void Sort(int[] arr) { int max = int.MinValue; foreach (int i in arr) { max = Math.Max(max, i); } for (int exp = 1; max / exp > 0; exp *= 10) { CountingSortByDigit(arr, exp); } } private static void CountingSortByDigit(int[] arr,int exp) { int n = arr.Length; //数字就0-9，所以桶是固定的 int[] buckets = new int[10]; //统计数组元素出现的个数 for (int i = 0; i < n; i++) { int index = arr[i] / exp; buckets[index % 10]++; } //对计数数组进行累加 for (int i = 1;i < 10; i++) { buckets[i] += buckets[i - 1]; } int[] sort = new int[n]; for (int i = arr.Length - 1; i >= 0; i--) { int index = arr[i] / exp; sort[buckets[index % 10] - 1] = arr[i]; buckets[index % 10]--; } // 将输出数组复制回原数组 for (int i = 0; i < n; i++) { arr[i] = sort[i]; } } 复杂度分析
- 时间复杂度
O(mn),m是最大元素的位数，n是待排序数组长度 - 空间复杂度
O(k)，同计数排序 - 排序稳定性
稳定，同计数排序 - 原地排序
不是，同计数排序
总结
| 排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 排序方式 | 适用场景 |
|---|---|---|---|---|---|---|---|
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | 比较排序 | 数据量小且对稳定性无要求 |
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 | 比较排序 | 数据量小且基本有序的情况 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 | 比较排序 | 数据量小且基本有序的情况 |
| 希尔排序 | O(n^{1.3}) | O(n) | O(n^2) | O(1) | 不稳定 | 比较排序 | 中等规模数据排序 |
| 快速排序 | O(n log n) | O(n log n) | O(n^2) | O(log n) | 不稳定 | 比较排序 | 数据量大且平均分布的情况 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 比较排序 | 数据量大且对稳定性有要求 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 比较排序 | 数据量大且对空间要求高、对稳定性无要求 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 | 非比较排序 | 数据范围小且为整数的情况 |
| 桶排序 | O(n + k) | O(n + k) | O(n^2) | O(n + k) | 稳定 | 非比较排序 | 数据均匀分布的情况 |
| 基数排序 | O(mn) | O(mn) | O(mn) | O(n) | 稳定 | 非比较排序 | 数据位数少且范围不大的整数排序 |
