电脑商业网站怎的做,广州深圳做网站,网站建设的优势是什么意思,以下可以制作二维码的网站为数据结构排序——计数排序和排序总结
现在常见算法排序都已讲解完成#xff0c;今天就再讲个计数排序。再总结一下 文章目录 1.计数排序2.排序总结3.排序oj#xff08;排序数组#xff09;题目详情代码思路 1.计数排序 计数排序是一种非基于比较的排序算法#xff0c;它通…数据结构排序——计数排序和排序总结
现在常见算法排序都已讲解完成今天就再讲个计数排序。再总结一下 文章目录 1.计数排序2.排序总结3.排序oj排序数组题目详情代码思路 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排序数组
题目详情
912. 排序数组 - 力扣LeetCode 代码
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);*returnSizenumsSize;return nums;
}Swap函数 这是一个用于交换两个整数值的简单函数。GetMid函数 用于在数组中找到三个位置左、中、右的元素从而选取合适的中间值。它通过比较这三个位置的元素找到其中介于最小和最大之间的值。QuickSort函数实现了快速排序的核心逻辑 选择中间值并将其与数组的第一个元素交换作为基准值。遍历数组将小于基准值的元素移到基准值左侧大于基准值的元素移到右侧相等的元素留在中间。对基准值左右两侧的子数组递归地进行快速排序直到左右两侧都排好序 思路 这题有根据快排的痛点进行特地进行测试用例的编写 一开始大家肯定就直接放上去一个快排结果发现超时了过不去的测试用例是有序的 所以第一次我们要加上三选一发现还不行过不去的是数字全部一样现在就考虑换上三路划分最后发现测试用例可以但是时间过长就改一下Getmid函数之前mid是 ( l e f t r i g h t ) / 2 (leftright)/2 (leftright)/2,现在是left(rand()%(right-left)) 好啦排序的内容也到这里啦。下面就要开启c的内容了
