数据结构_第十三关（3）：归并排序、计数排序

目录

归并排序

1.基本思想：

2.原理图：

1）分解合并

2）数组比较和归并方法：

3.代码实现（递归方式）：

4.归并排序的非递归方式

原理：

情况1：

情况2：

情况3：

非递归代码实现

归并排序的特性总结：

计数排序

基本思想：

算法原理：

算法升级

计算排序的特点：

代码实现

排序算法复杂度及稳定性分析

什么时稳定性？

各种常见排序算法的总结

---

归并排序

1.基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,

该算法是采用分治法（Divide andConquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；

即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。

2.原理图：

1）分解合并

第一层将一个数组分两个大组，

第二层再继续分，直到分成每组都只有一个为止

分解完了之后就是进行合并，每两个小数组，按顺序合并成一个大的数组

最终，合并称为一个有序的集合

动图效果：

归并排序是在原数组上进行的，用一个临时数组来做归并，把归并好的元素复制回原数组

2）数组比较和归并方法：

用上述长度为4的集合举例：

第一步：比较p1和p2位置元素的大小，谁的小，将谁的值放到p位置，并将指向小的元素的那个指针++，并且将p++

1比2小，放1到p位置，p1++，p++

 ......

第二步：按第一步的步骤，逐一比较，直到有一个指针走到了集合之外如下：

此时p2已经走到了集合外，就可以退出循环了

 第三步：放一个循环，将没走完的那个集合的剩余元素按顺序放到大集合种即可

当p走到大集合外面时结束循环

3.代码实现（递归方式）：

//归并排序（递归实现）//归并子函数
//（在遇到需要malloc扩容的函数时，将malloc代码放入主函数，另写一个子函数用来完成递归）
void _MergeSort(int* a, int begin ,int end, int* temp)
{//最后只剩下一个数的时候就说明begin=end，返回if (begin >= end){return;}int mid = (begin + end) / 2;//[begin, mid] [mid+1, end] 递归让子区间都有序_MergeSort(a, begin, mid, temp);    //递归左半区_MergeSort(a, mid+1, end, temp);    //递归右半区//归并int begin1 = begin, end1 = mid;     //左区间[begin1, end1]int begin2 = mid + 1, end2 = end;   //右区间[begin2, end2]int i = begin;//如果左右两个区间都没有结束就继续，只要有一个区间结束就终止while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){temp[i++] = a[begin1++]; }else{temp[i++] = a[begin2++];}}//将没走到头的区间按顺序放到后面while (begin1 <= end1){temp[i++] = a[begin1++];}while (begin2 <= end2){temp[i++] = a[begin2++];}//将临时区间的数据拷贝回原数组memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}//归并主函数
void MergeSort(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, 0, n-1, temp);free(temp);temp = NULL;
}

4.归并排序的非递归方式

原理：

控制每次参与归并的元素即可，可以先定义一个变量rangeN，让其来划分区域

 开始时rangeN=1，区域为1则是有序，

i = i + 2*rangeN     定义 i 来区分每块区域

左区域：[begin1,end1]                右区域：[begin2,end2]

上图情况是一个特殊情况，如果遇到不能被完全划分左右区域对称的情况分为以下三种：

情况1：

当最后一个区域进行归并时，最后一组的左区间越界，所以需要对左区间的end1进行控制

情况2：

当最后一个区域进行归并时，最后一组的右区间全部越界，所以需要对右区间的begin2进行控制

情况3：

 当最后一个小组进行归并时，由于右区间越界，所以我们需要对右区间end2进行控制

非递归代码实现

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");exit(-1);}// 归并每组数据个数，从1开始，因为1个认为是有序的，可以直接归并int rangeN = 1;while (rangeN < n) {for (int i = 0; i < n; i += 2 * rangeN){// [begin1,end1][begin2,end2] 归并int begin1 = i, end1 = i + rangeN - 1;int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;int j = i;// end1 begin2 end2 越界的三种情况//一定需要按顺序进行判断，不然会出错//end1越界，情况1，//解决：直接退出本次循环，可以不让后面的进行归并，再下一次循环时再排序if (end1 >= n){break;}//begin2出界，情况2，//解决：直接退出本次循环，可以不让后面的进行归并，再下一次循环时再排序else if (begin2 >= n){break;}//end2越界，情况3//解决：让end2等于数组最后的下标else if (end2 >= n){end2 = n - 1;}//开始按顺序归并while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}// 归并一部分，拷贝一部分memcpy(a + i, tmp + i, sizeof(int)*(end2 - i + 1));}rangeN *= 2;}free(tmp);tmp = NULL;
}

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，
   归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

计数排序

基本思想：

之前学习的排序，无论是希尔排序，还是堆排序，都用的是比较两个数大小的方式进行的排序

而计数排序不是用比较的方法来进行排序的，它利用的是数组下标的计数来进行的排序

具体实现方法如下：

算法原理：

现假设有一组0~4的数据需要排序：{ 2，3，3，4，0，3，2，4，3 }

创建一个临时数组temp来依次记录每个数的出现次数

原数组中，

        0出现了1次，就在temp下标为0的位置记录1

        1没有出现，  就在temp下标为1的位置记录0

        2出现了2次，就在temp下标为0的位置记录2

        3出现了4次，就在temp下标为0的位置记录3

        4出现了2次，就在temp下标为0的位置记录2

数组每一个下标位置的值，代表了数列中对应整数出现的次数。

有了这个 “统计结果”，排序就很简单了。
直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：

这样就能得到一个有序序列了

这就是计数排序的过程，因为他没有进行数与数之间的比较，
所以他的性能甚至快过那些O( log N) 的排序

可以看到上面的排序是一种特殊情况，那如果我们要排序的数组是  9000~9009，那么是不是得浪费前九千多个空间？

又或者是在原数组里面有负数的情况下是不是九不能进行计数排序了？

这就要对现有的算法进行一些小小的升级了

算法升级

例如我们有一组这样的数：9004，9001，9002，9005，9004，9001

这个数组，最大是9005，但最小的数是9001，如果用长度为9005的数组，那么按照上面的方法排序，肯定会太过浪费

事实上我们只需要开辟大小为5的数组即可（最大数 - 最小数 + 1）9005 - 9001 +1 = 5

用下标为0的记录9001，用下标为4的记录9005

当然，对于负数也一样可以使用，这里就不一一展示了

计算排序的特点：

1. 稳定性：稳定
2. 时间复杂度：O（n+k）
3. 空间复杂度：O（n+k）

对于数据率不是很大，并且数据比较集中时，计数排序是一个很有效的排序算法

计数排序的局限性：

不能对小数进行排序，只适用于整数

代码实现

分4步实现

1. 找到数组中的最大最小值
2. 计算范围，开辟临时数组空间
3. 统计相同元素出现次数
4. 根据计数结果将序列依次放回原来的数组中

//计数排序
void CountSort(int* a, int n)
{//确定数组里面的最大最小值int max = a[0], min = a[0];for (int i = 1;i < n;i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}//范围 = 最大值 - 最小值 + 1//比如从 0 到 9 有10个数int range = max - min + 1;//用calloc开辟range个大小为int的空间，并给每个元素赋值为0int* countA = (int*)calloc(range, sizeof(int));if (countA == NULL){perror("calloc fail");exit(-1);}//统计相同元素出现的次数for (int i = 0;i < n;i++){//a[i] - min 是a[i]下标在countA里面对应的相对位置countA[a[i] - min]++;}//排序，根据计数结果将序列依次放回原来的数组中int k = 0;for (int j = 0;j < range;j++){while (countA[j]--){//j + min 就是数组元素的大小a[k++] = j + min;}}free(countA);
}

排序算法复杂度及稳定性分析

什么时稳定性？

稳定性的价值：

比如再考试排名的时候，第三名种有三个人的成绩相同，那么如果先交卷的人是第三名的话，就要去再成绩排序的时候保证其稳定性

各种常见排序算法的总结