莆田网站建设电话,当涂网站建设,物流信息平台,上海制作网站公司目录 一、选择排序二、计数排序 一、选择排序
整体思想#xff1a; 从数组中选出最小值和最大值放在起始位置#xff0c;直到排序完成
具体步骤#xff1a;
定义两个变量begin和end为下标#xff0c;指向数组始末定义要找的最大值的下标为maxi#xff0c;最小值的下标为… 目录 一、选择排序二、计数排序 一、选择排序
整体思想 从数组中选出最小值和最大值放在起始位置直到排序完成
具体步骤
定义两个变量begin和end为下标指向数组始末定义要找的最大值的下标为maxi最小值的下标为mini刚开始初始化为begin因为begin和end会缩小也就是说找最大和最小的范围为当前begin和end之间的范围找到最大值的下标和最小值的下标然后把最小值与begin位置的值交换这里要考虑特殊情况最后再交换最大值和end位置的值beginend–缩小范围再重复前面的步骤
图示 代码
void SelectSort(int* a, int n)
{//数组的范围int begin 0, end n - 1;while (begin end)//控制范围{// maxi和mini是下标从begin开始因为begin会变化int maxi begin, mini begin;//找最大元素的下标和最小元素的下标for (int i begin; i end; i)//注意找的范围{if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}//最小值与begin的位置交换Swap(a[begin], a[mini]);//特殊情况如果maxi与begin重叠此时最大值的下标在miniif (begin maxi){maxi mini;}//最大值与end的位置交换Swap(a[end], a[maxi]);//缩小范围begin;--end;}
}特性总结
时间复杂度O(N ^ 2)空间复杂度O(1)不稳定
二、计数排序
计数排序采用相对映射的思想开辟一块空间该空间的范围为待排序的数组的最大值和最小值之差加1并且每个元素初始化为0然后待排序的数组只要是出现的元素就在临时空间对应的位置计数最后从小到大恢复原来的元素重新放入数组完成排序。 思路
在数组中找到最大值max和最小值min算出最大与最小之间有多少个数范围rangemax-min1开临时空间大小为range每个元素初始化为0待排序数组的元素减去最小值min即对应临时空间的下标原数组出现的元素会在临时空间对应的位置计数从小到大遍历临时空间数组只要不为0说明该位置是对应原数组有出现的元素然后依次重新放入原数组临时空间的下标加上最小值恢复到原数组的元素的值。
图示
代码
void CountSort(int* a, int n)
{//找最大值和最小值int max a[0], min a[0];for (int i 0; i n; i){if (a[i] max){max a[i];}if (a[i] min){min a[i];}}//最大值与最小值的差int range max - min 1;//开空间每个元素为0后面要计数int* count (int*)calloc(range, sizeof(int));if (count nullptr){perror(calloc fail);exit(-1);}//给出现的元素计数for (int i 0; i n; i){count[a[i] - min];}//从小到大重新放入数组完成排序int j 0;for (int i 0; i range; i){while (count[i]--)//该位置有元素{a[j] i min;//恢复原来的元素依次放入数组}}free(count);
}特性总结
计数排序适用于数据较集中的场景时间复杂度O(Nrange)空间复杂度O(range)稳定
