【数据结构与算法】第12课—数据结构之归并排序
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，直接全部放入tmp
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
//此时若第二个序列还有元素未放入tmp，直接全部放入tmp
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//最后将新建的数组tmp赋给arr
for (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申请内存会自动将所有元素默认设置为0
int* 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);
}
原文地址：https://blog.csdn.net/weixin_70620792/article/details/143659670
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！