数据结构排序——计数排序和排序总结
现在常见算法排序都已讲解完成,今天就再讲个计数排序。再总结一下
计数排序是一种非基于比较的排序算法,它通过统计数组中每个元素出现的次数,然后根据元素的值和出现次数重新构造数组,从而实现排序。计数排序适用于元素范围比较小且元素非负的情况 步骤:
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;
}
排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|
直接插入排序 | 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) | 稳定 |
不稳定的情况之一:
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;
}
这题有根据快排的痛点进行特地进行测试用例的编写 一开始大家肯定就直接放上去一个快排,结果发现:超时了(过不去的测试用例是有序的)
mid
是,现在是left+(rand()%(right-left))
好啦,排序的内容也到这里啦。下面就要开启c++的内容了