【排序篇2】选择排序、计数排序

一、选择排序

整体思想：
从数组中选出最小值和最大值放在起始位置，直到排序完成

具体步骤：

1. 定义两个变量begin和end为下标，指向数组始末
2. 定义要找的最大值的下标为maxi，最小值的下标为mini，刚开始初始化为begin，因为begin和end会缩小，也就是说找最大和最小的范围为当前begin和end之间的范围
3. 找到最大值的下标和最小值的下标，然后把最小值与begin位置的值交换，这里要考虑特殊情况，最后再交换最大值和end位置的值
4. begin++，end–，缩小范围再重复前面的步骤

图示：

代码：

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，然后待排序的数组只要是出现的元素就在临时空间对应的位置计数，最后从小到大恢复原来的元素重新放入数组，完成排序。
思路：

1. 在数组中找到最大值max和最小值min
2. 算出最大与最小之间有多少个数，范围range：max-min+1
3. 开临时空间大小为range，每个元素初始化为0
4. 待排序数组的元素减去最小值min即对应临时空间的下标，原数组出现的元素会在临时空间对应的位置计数
5. 从小到大遍历临时空间数组，只要不为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(N+range)
• 空间复杂度：O(range)
• 稳定