数据结构排序——计数排序和排序总结
现在常见算法排序都已讲解完成，今天就再讲个计数排序。再总结一下
1.计数排序
计数排序是一种非基于比较的排序算法，它通过统计数组中每个元素出现的次数，然后根据元素的值和出现次数重新构造数组，从而实现排序。计数排序适用于元素范围比较小且元素非负的情况
步骤：
找出待排序的数组中最大和最小的元素：min和max
统计数组中每个值为 i 的元素出现的次数，存入新建数组 C 的第 i-min 项(c初始化时都是0)，每遇到一次，对应下标上的数就++
反向填充目标数组：利用新建的数组把数据覆盖回去
时间复杂度：O(n + range)
void CountSort(int* a, int n) { //先找最大最小，确定范围 int max = a[0], min = a[0]; for (int i = 1; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } int range = max - min + 1; int* count= (int*)calloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); return; } //开始想count中累加了 for (int i = 0; i < n; i++) { count[a[i] - min]++; } //赋值覆盖 int a_index = 0; for (int i = 0; i < range; i++) { for (int j = 0; j < count[i]; j++) { a[a_index] = i + min; a_index++; } } } int main() { int a[] = { 2,4,1,7,9 }; CountSort(a, 5); for (int i = 0; i < 5; i++) { printf("%d ", a[i]); } return 0; }
2.排序总结
| 排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
| 直接插入排序 | O(N^2) | O(1) | 稳定 |
| 希尔排序 | O(N^1.3) | O(logN) | 不稳定 |
| 选择排序 | O(N^2) | O(N) | 不稳定 |
| 堆排序 | O(N*logN) | O(N) | 不稳定 |
| 冒泡排序 | O(N^2) | O(1) | 稳定 |
| 快速排序 | O(N*logN) | O(logN) | 不稳定 |
| 归并排序 | O(N*logN) | O(N) | 稳定 |
不稳定的情况之一：
- 希尔：根据gap分组不在一个组
- 选择：3 3 1 1…
- 堆排序：向下调整过程
- 快排：相同的数字其中一个在keyi的位置
3.排序oj（排序数组）
题目详情
代码
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } int GetMid(int* a,int left, int right)//找中间的 { // a[left] a[mid] a[right] int mid = left+(rand()%(right-left)); if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) // mid是最大值 { return left; } else { return right; } } else // a[left] > a[mid] { if (a[left] < a[right]) { return left; } else if (a[mid] < a[right]) { return right; } else { return mid; } } } void QuickSort(int* a, int left, int right) { if (left >= right) { return; } int begin = left; int end = right; int mid = GetMid(a, left, right); Swap(&a[mid], &a[left]); int cur = left + 1; int key = a[left];//储存一下，后面比较来用，用a[left]会被替代 while (cur <= right) { if (a[cur] < key) { Swap(&a[cur], &a[left]); cur++; left++; } else if (a[cur] == key) { cur++; } else { Swap(&a[cur], &a[right]); right--; } } QuickSort(a, begin, left - 1); QuickSort(a, right + 1, end); } int* sortArray(int* nums, int numsSize, int* returnSize) { srand(time(0)); QuickSort(nums,0,numsSize-1); *returnSize=numsSize; return nums; }
Swap函数： 这是一个用于交换两个整数值的简单函数。
GetMid函数： 用于在数组中找到三个位置（左、中、右）的元素，从而选取合适的中间值。它通过比较这三个位置的元素，找到其中介于最小和最大之间的值。
QuickSort函数：实现了快速排序的核心逻辑
选择中间值，并将其与数组的第一个元素交换，作为基准值。
遍历数组，将小于基准值的元素移到基准值左侧，大于基准值的元素移到右侧，相等的元素留在中间。
对基准值左右两侧的子数组递归地进行快速排序，直到左右两侧都排好序
思路
这题有根据快排的痛点进行特地进行测试用例的编写
一开始大家肯定就直接放上去一个快排，结果发现：超时了（过不去的测试用例是有序的）
所以第一次我们要加上三选一
发现还不行（过不去的是数字全部一样），现在就考虑换上三路划分
最后发现测试用例可以，但是时间过长，就改一下Getmid函数，之前mid是( l e f t + r i g h t ) / 2 (left+right)/2(left+right)/2,现在是left+(rand()%(right-left))
好啦，排序的内容也到这里啦。下面就要开启c++的内容了
