重生之数据结构与算法----常见排序算法(三)
简介之前介绍的7种常见排序算法，它们都是比较排序，也就是有if(arr > arr)的比较过程。
接下来要介绍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;
//统计数组元素出现的个数
foreach (int element in nums)
{
temp++;
}
//对计数数组进行累加
for (int i = 1; i < temp.Length; i++)
{
temp += temp;
}
var sort = new int;
for (int i = nums.Length - 1;i>= 0; i--)
{
sort + offset] - 1] = nums;
temp + offset]--;
}
for(int i = 0; i < nums.Length; i++)
{
nums = sort;
}
}复杂度分析
[*]时间复杂度
O(n+k)，n是数组长度，k是元素的取值范围(max-min+1)
[*]空间复杂度
O(k)，这点比较伤，因为是利用数组的特性。所以取值范围多大，k就有多大。要万一是0，999。那就要创建int的空间。
[*]排序稳定性
在将元素放入排序后的数组时，从后往前遍历待排序数组，保证了相等元素的相对顺序不变。
[*]原地排序
很明显不是。它需要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>;
for(int i = 0; i < bucketCount; i++)
{
buckets = new List<int>(bucketSize);
}
//分配元素
foreach(int num in nums)
{
//用除法向下取整计算桶的索引
var bucketIndex = (num + offset) / bucketSize;
buckets.Add(num);
}
//对每个桶元素进行排序
//分而治之的魅力，就是可以利用多个线程。
Parallel.For(0, bucketCount, i =>
{
InsertSort(buckets);
});
//合并有序桶
int idx = 0;
for (int i = 0; i < buckets.Length; i++)
{
foreach (var item in buckets)
{
nums = 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 < arr)
{
//swap
(arr, arr) = (arr, arr);
}
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;
//统计数组元素出现的个数
for (int i = 0; i < n; i++)
{
int index = arr / exp;
buckets++;
}
//对计数数组进行累加
for (int i = 1;i < 10; i++)
{
buckets += buckets;
}
int[] sort = new int;
for (int i = arr.Length - 1; i >= 0; i--)
{
int index = arr / exp;
sort - 1] = arr;
buckets--;
}
// 将输出数组复制回原数组
for (int i = 0; i < n; i++)
{
arr = sort;
}
}复杂度分析
[*]时间复杂度
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)稳定非比较排序数据位数少且范围不大的整数排序
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]