【数据结构与算法】第12课—数据结构之归并排序

文章目录

1. 归并排序
2. 计数排序
3. 排序算法复杂度及稳定性分析
- 在这里插入图片描述

1. 归并排序

分治法（Divide and Conquer）是一种重要的算法设计策略，其核心思想是将一个复杂的大问题分解为若干个小规模的子问题，递归地解决这些子问题，并将它们的解合并起来以得到原始问题的解。
而归并排序正是分治法的一个典型应用
归并排序的思想：首先将一个序列分为两个子序列，再将两个子序列分为4个子序列，直到每个元素都各为一个序列，则不再继续分，然后合并子序列，将子序列开始有序合并，最终合并成一个有序的序列,它本质还是递归

接下来我将用图示的方法来帮助大家理解

在这里插入图片描述

代码

//归并排序子函数
void _MergeSort(int* arr, int left, int right, int* tmp)
{//如果首元素下标大于等于尾元素下标if (left >= right){return;}//根据中间值二分int mid = left + (right - left) / 2;//左边序列[left,mid]  右边序列[mid+1,right]_MergeSort(arr, left, mid, tmp);//分解左子序列_MergeSort(arr, mid + 1, right, tmp);//分解右子序列//合并两个有序序列int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;while (begin1 <= end1 && begin2 <= end2){//如果第一个序列的首元素小于第二个序列的首元素if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];//赋完值都往后走}//如果第一个序列的首元素大于第二个序列的首元素else{tmp[index++] = arr[begin2++];//赋完值都往后走}}//此时若第一个序列还有元素未放入tmp，直接全部放入tmpwhile (begin1 <= end1){tmp[index++] = arr[begin1++];}//此时若第二个序列还有元素未放入tmp，直接全部放入tmpwhile (begin2 <= end2){tmp[index++] = arr[begin2++];}//最后将新建的数组tmp赋给arrfor (int i = left; i <= right; i++){arr[i] = tmp[i];}
}//归并排序
void MergeSort(int* arr, int sz)
{//创建tmp函数用来接收合并的有序数组int* tmp = (int*)malloc(sizeof(int) * sz);if (tmp == NULL){perror("malloc fail!\n");exit(1);}_MergeSort(arr, 0, sz - 1, tmp);free(tmp);tmp = NULL;
}

2. 计数排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：
1）统计相同元素出现次数
2）根据统计的结果将序列回收到原来的序列中

在这里插入图片描述

代码

//计数排序
void CountSort(int* arr, int sz)
{int max = arr[0], min = arr[0];//默认为首元素//找最大、最小数for (int i = 0; i < sz; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}//计数int range = max - min + 1;//count数组大小//calloc申请内存会自动将所有元素默认设置为0int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror("malloc fail!\n");exit(1);}for (int i = 0; i < sz; i++){count[arr[i]-min]++;//对应的count数组元素++}//排序int index = 0;//arr数组下标//遍历count数组，找对应元素出现的次数for (int i = 0; i < range; i++){//将count数组对应元素放入arr数组while (count[i]--){arr[index++] = i + min;}}//释放内存free(count);count = NULL;
}

计数排序的时间复杂度是O(n+range)
计数排序的空间复杂度是O(range)
计数排序有一定的局限性，当数组中的数据差值较大时，会造成空间的极大浪费，此时计数排序便不再适用，因此它只适用于元素之间差值较小的序列

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

稳定性：对于含有相同数据的序列，排序前后不改变他们的相对位置，则代表该算法稳定，否则表示该排序算法不稳定

在这里插入图片描述

各种排序算法的时间复杂度

各种排序性能测试

在这里插入图片描述

//测试排序的性能对⽐
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}