今天把三种排序放到一起写，因为原理都差不多。
桶排序
桶排序的代码我没有写，讲下思想就可以了。
图片.png
时间复杂度
O(n)
空间复杂度
O(n * m) n是多少个桶 m每个桶多少个元素
稳定排序
取决于每个桶中的元素使用什么排序算法
算法核心思想
将待排序元素按顺序拆分为N个桶，再对每个桶中的元素进行排序。之后按顺序输出每个桶中的元素。
计数排序
废话不多说先上代码
void countingSort(int arr[], int length) {
int max = arr[0];
for (int i = 1; i < length; ++i)
{
if (max < arr[i])
{
max = arr[i];
}
}
int counting[max + 1];
memset(&counting, 0, sizeof(int) * (max + 1));
for (int i = 0; i < length; ++i)
{
counting[arr[i]]++;
}
for (int i = 1; i < max + 1; ++i)
{
counting[i] += counting[i - 1];
}
int temp[length];
for (int i = length - 1; i >= 0; --i)
{
temp[--counting[arr[i]]] = arr[i];
}
for (int i = 0; i < length; ++i)
{
arr[i] = temp[i];
}
return;
}
时间复杂度
O(n)
空间复杂度
额外需要数组中最大元素大小的空间
稳定排序
稳定排序
算法核心思想
根据数组中最大元素创建一个临时数组。
扫描一遍数组，将临时数组中下标与当前元素对应的值加1。
将临时数组中值不为1的元素的下标输出，值为1就输出下标1次，值为2就输出下标两次，值为几就输出下标几次。
思想就这么简单，实现的逻辑有些绕。
一步步实现计数排序
根据数组中最大元素申请额外空间。
void countingSort(int arr[], int length) {
int max = arr[0];
for(int i = 1; i < length; ++i)
{
if(max < arr[i])
{
max = arr[i];
}
}
//申请一个大小为最大数加1的数组
int counting[max + 1];
memset(&counting, 0, sizeof(int) * (max + 1));
}
计算每个元素出现的次数
void countingSort(int arr[], int length) {
int max = arr[0];
for(int i = 1; i < length; ++i)
{
if(max < arr[i])
{
max = arr[i];
}
}
//申请一个大小为最大数加1的数组
int counting[max + 1];
memset(&counting, 0, sizeof(int) * (max + 1));
//计算每个元素出现的次数，将对应下标的值加1
for(int i = 0; i < length; ++i)
{
counting[arr[i]]++;
}
}
将元素按顺序填装回数组
这里的填装顺序决定了计数排序是否为稳定算法
void countingSort(int arr[], int length) {
int max = arr[0];
for(int i = 1; i < length; ++i)
{
if(max < arr[i])
{
max = arr[i];
}
}
//申请一个大小为最大数加1的数组
int counting[max + 1];
memset(&counting, 0, sizeof(int) * (max + 1));
//计算每个元素出现的次数，将对应下标的值加1
for(int i = 0; i < length; ++i)
{
counting[arr[i]]++;
}
//这一步计算出下标对应的元素应该在原数组中的位置
//这个位置是从后往前计算的
//假如有两个2 这里存储的是第二个 2 应该在原数组中的下标
for(int i = 1; i < max + 1; ++i)
{
counting[i] += counting[i - 1];
}
//申请一个和原数组一样大的临时数组
int temp[length];
//将arr数组元素按照counting的对应关系赋值给temp
for(int i = 0; i < length; ++i)
{
//counting[arr[i]] 就是 arr应该在的位置 下标从0开始要先减1
temp[--counting[arr[i]]] = arr[i];
}
//将temp 赋值给 arr
for(int i = 0; i < length; ++i)
{
arr[i] = temp[i];
}
}
计数排序就已经完成了，难点就在计算原数组对应关系这，可以自己写写理解一下。
基数排序
基数排序就是计数排序的另一个版本，我们要对284，385，235这样的少量且值大的数组排序，如果用计数排序就太占用空间了，这是我们就可以使用基数排序。
先看代码
int lastNum(int num, int place) {
int base = 1;
while(place > 1) {
place--;
base *= 10;
}
printf("返回值 %d\n", (num / base) % 10);
return (num / base) % 10;
}
void radixSort(int arr[], int length) {
int max = arr[0];
for (int i = 1; i < length; ++i)
{
if (max < arr[i])
{
max = arr[i];
}
}
int max_size = 0;
while(max > 0) {
++max_size;
max /= 10;
}
for (int j = 1; j <= max_size; ++j)
{
int counting[10];
memset(&counting, 0, sizeof(int) * 10);
for (int i = 0; i < length; ++i)
{
counting[lastNum(arr[i], j)]++;
}
for (int i = 1; i < 10; ++i)
{
counting[i] += counting[i - 1];
}
int temp[length];
for (int i = length - 1; i >= 0; --i)
{
temp[--counting[lastNum(arr[i], j)]] = arr[i];
}
for (int i = 0; i < length; ++i)
{
arr[i] = temp[i];
}
}
}
时间复杂度
O(n)
空间复杂度
每一位的范围不同而变化
稳定排序
稳定排序
算法核心思想
先对低位进行计数排序，然后在对高位进行计数排序，因为计数排序是稳定排序，将所有位都进行排序后整个数组就有序了。
因为基数排序就是基于计数排序实现的，我这里只讲一些不同的地方。
取数组中的某一位
int lastNum(int num, int place) {
int base = 1;
while(place > 1) {
place--;
base *= 10;
}
printf("返回值 %d\n", (num / base) % 10);
return (num / base) % 10;
}
计算数组中最大元素的位数
void radixSort(int arr[], int length) {
int max = arr[0];
for (int i = 1; i < length; ++i)
{
if (max < arr[i])
{
max = arr[i];
}
}
int max_size = 0;
while(max > 0) {
++max_size;
max /= 10;
}
}
对每一位进行计数排序
void radixSort(int arr[], int length) {
int max = arr[0];
for (int i = 1; i < length; ++i)
{
if (max < arr[i])
{
max = arr[i];
}
}
int max_size = 0;
while(max > 0) {
++max_size;
max /= 10;
}
//最大数的位数，有几位进行几次计数排序
for (int j = 1; j <= max_size; ++j)
{
int counting[10];
memset(&counting, 0, sizeof(int) * 10);
for (int i = 0; i < length; ++i)
{
//通过lastNum函数获取对应位
counting[lastNum(arr[i], j)]++;
}
for (int i = 1; i < 10; ++i)
{
counting[i] += counting[i - 1];
}
int temp[length];
for (int i = length - 1; i >= 0; --i)
{
temp[--counting[lastNum(arr[i], j)]] = arr[i];
}
for (int i = 0; i < length; ++i)
{
arr[i] = temp[i];
}
}
}
如果你会计数排序的话基数排序已然不在话下了
看到这了，点个赞再走~
网友评论