排序3——C语言

排序

1. 归并排序
2. 计数排序
3. 各排序的稳定性及复杂度

1. 归并排序

归并排序是建立在归并操作上的一种有效的算法>排序算法,该算法是采用分治法的一个非常典型的应用。

思路：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
下图为归并的全过程
在这里插入图片描述
将序列分割，若子区间无序，对子区间再分割，直至子区间有序（只有一个数时）再进行合并（相当于合并两个有序数组）。合并数据时，不能直接覆盖再原数组，会造成数据丢失，因此需要开辟一个辅助数组。

//归并排序
//复杂度O(N*logN)
void _MergeSort(int* array, int* tmp, int begin, int end)//左右闭区间
{//只有一个值，不用归并if (begin == end)return;//分成两组分别递归，归并int mid = (begin + end) / 2;_MergeSort(array, tmp, begin, mid);_MergeSort(array, tmp, mid + 1, end);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;//归并过程while (begin1 <= end1 && begin2 <= end2){if (array[begin1] <= array[begin2]){tmp[i++] = array[begin1++];}else{tmp[i++] = array[begin2++];}}while (begin1 <= end1){tmp[i++] = array[begin1++];}while (begin2 <= end2){tmp[i++] = array[begin2++];}//拷贝回原数组memcpy(array + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* array, int numsArr)
{//开辟辅助数组int* tmp = (int*)malloc(sizeof(int) * numsArr);if (tmp == NULL){return;}_MergeSort(array, tmp, 0, numsArr - 1);free(tmp);tmp = NULL;
}

归并排序的缺点，空间复杂度为O（N），即额外需要一块辅助空间。

2. 计数排序

计数排序的思路：

统计相同元素出现次数（遍历一遍数据即可）
根据统计的结果将序列回收到原来的序列中

举例如下图
在这里插入图片描述
这里会面临两个问题

数据过大，数据范围分散
数据有负数，下标没有负数
问题一会导致一个问题，开的辅助空间很大，比如数据为{ 1 ，19 ，33，50，69}，五个数需要开辟70个空间，太浪费。事实上，计数排序不适用于数据范围分散的情况，如果当数据范围很大很分数时，就不要采用计数排序了。

问题二可以采用相对映射的方法来解决。让每一个数都减去最小值，那么如果有负数，减去最小值（也是负数，可能是本身）之后的值肯定大于等于0，就可以满足数组的下标了。还原回去时，数据再加上最小值即可。

//计数排序
//时间复杂度O(N+range)，空间复杂度O(range)
//适合于数据范围小的情况
void CountSort(int* array, int numsArr)
{//最大最小值int max = array[0], min = array[0];for (int i = 1; i < numsArr; i++){if (array[i] < min)min = array[i];if (array[i] > max)max = array[i];}//开空间int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL)return;//统计每个数出现的次数(相对映射)for (int i = 0; i < numsArr; i++){count[array[i] - min]++;}//修改数组int j = 0;for (int i = 0; i < range; i++){while (count[i]--){array[j++] = i + min;}}
}