【数据结构初阶】八大排序(三)——归并排序计数排序
大家好我是沐曦希💕
往期博客：【数据结构初阶】八大排序(一)——希尔排序&&堆排序&&直接插入排序&&直接选择排序
【数据结构初阶】八大排序(二)——快速排序&&冒泡排序
文章目录
- 1.归并排序(递归)
- 1.1 基本思想
- 1.2 具体思路
- 1.2 代码
- 1.3 特性总结
- 排序性能对比
- 2.归并排序(非递归)
- 2.1 具体思路
- 2.3 代码
- 3.非比较排序——计数排序
- 3.1 基本思想
- 代码
- 特性总结
- 排序性能对比
- 4.排序算法复杂度及稳定性分析
- 5.选择题练习
- 5.1 选择题一
- 5.2 选择题二
- 5.3 选择题三
- 5.4 选择题四
- 5.5 选择题五
- 5.6 选择题六
- 5.7 选择题七
- 4.写在最后
1.归并排序(递归)
1.1 基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
1.2 具体思路
第一步：递归分解数组。通过递归将数组a分解成n个数组，其中每个数组只有一个元素，类似与二叉树。那么此时每个数组都是有序的，那么就可以进行归并。例如:
第二步：将上述的n个数组，进行相邻两两数组的全部元素进行比较，创建一个新的数组tmp，数组tmp大小和数组a的大小相同。取小的尾插进数组tmp,将两个数组中剩余元素尾插进入数组tmp。
(当数组元素不为奇数)进行一次归并后，每个数组的元素为两个，那么继续相邻的两个数组进行元素比较，取小的尾插到tmp，最后将两个数组中剩余元素尾插进入数组tmp。
(当数组元素个数为2^n)此时每个数组的元素个数为四个，继续按照上面步骤直到数组有序。
第三步，最后将数组tmp的元素拷贝回原数组a–归并哪了部分就拷贝哪部分回原数组a。
memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));
归并排序的动图
因为需要分解和比较元素大小，那么可以创建三个变量left,mid,right。将数组分解成[left,mid] [mid+1,right]继续进行递归直到每个数组元素只有一个。
此时要解决边界的问题：即数组一的left1是left,right1是mid。
数组二的left2是mid+1,right2是right。
比较大小
while (left1 <= right1 && left2 <= right2)
{
if (a[left1] <= a[left2])
tmp[i++] = a[left1++];
else
tmp[i++] = a[left2++];
}
while (left1 <= right1)
tmp[i++] = a[left1++];
while (left2 <= right2)
tmp[i++] = a[left2++];
1.2 代码
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
return;
int mid = (right - left) / 2 + left;
//[left,mid] [mid+1,right]
//递归将数组分成n个数组--类似二叉树
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
//归并一趟
int left1 = left, right1 = mid;
int left2 = mid + 1, right2 = right;
int i = left;
while (left1 <= right1 && left2 <= right2)
{
if (a[left1] <= a[left2])
tmp[i++] = a[left1++];
else
tmp[i++] = a[left2++];
}
while (left1 <= right1)
tmp[i++] = a[left1++];
while (left2 <= right2)
tmp[i++] = a[left2++];
//拷贝回原数组--归并哪部分就拷贝哪部分回原数组
memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(n * sizeof(int));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, 0, n - 1, tmp);
}
1.3 特性总结
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
排序性能对比
void testOp()
{
srand((unsigned int)time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
assert(a1);
int* a2 = (int*)malloc(sizeof(int) * N);
assert(a2);
int* a3 = (int*)malloc(sizeof(int) * N);
assert(a3);
int* a4 = (int*)malloc(sizeof(int) * N);
assert(a4);
int* a5 = (int*)malloc(sizeof(int) * N);
assert(a5);
int* a6 = (int*)malloc(sizeof(int) * N);
assert(a6);
int* a7 = (int*)malloc(sizeof(int) * N);
assert(a7);
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();
//BubbleSort(a5, N);
int end5 = clock();
int begin6 = clock();
QuickSort(a6, 0, N - 1);
int end6 = clock();
int begin7 = clock();
MergeSort(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("BubbleSort:%d\n", end5 - begin5);
printf("QuickSort:%d\n", end6 - begin6);
printf("MergeSort:%d\n", end7 - begin7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
free(a8);
a1 = NULL;
a2 = NULL;
a3 = NULL;
a4 = NULL;
a5 = NULL;
a6 = NULL;
a7 = NULL;
}
当N为1000000时
2.归并排序(非递归)
2.1 具体思路
非递归的基本思路和递归类似，不同的是非递归通过创建一个新变量gap来进行分解数组。
gap可以从1或者2开始分解数组，当每个数组元素都为1或者2时，进行归并。此时数组元素个数变成2或者4，gap就增大一倍，继续归并。
重复以上步骤直到数组有序。
要注意的是：
1.数组个数不一定是整数倍，上面计算时候直接按照整数倍算的，存在数组越界的情况，需要我们修正一下数组边界。
//第一组部分越界
if (end1 >= n)
break;
//第一组不越界，第二组全部越界
if (begin2 >= n)
break;
//第二组部分越界
if (end2 >= n)
end2 = n - 1;
2.因为有奇数情况，所以要归并完哪部分数组就拷贝回哪部分数组回原数组。
2.3 代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void MergeSortNOR(int* a, int n)
{
int* tmp = (int*)malloc(n * sizeof(int));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
int j = 0;
while (gap < n)
{
for (j = 0; j < n; j += 2 * gap)
{
int begin1 = j, end1 = j + gap - 1;
int begin2 = j + gap, end2 = j + 2 * gap - 1;
//需要调整边界
//第一组部分越界
if (end1 >= n)
break;
//第一组不越界，第二组全部越界
if (begin2 >= n)
break;
//第二组部分越界
if (end2 >= n)
end2 = n - 1;
int i = j;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
tmp[i++] = a[begin1++];
else
tmp[i++] = a[begin2++];
}
while (begin1 <= end1)
tmp[i++] = a[begin1++];
while (begin2 <= end2)
tmp[i++] = a[begin2++];
memcpy(a + j, tmp + j, (end2 - j + 1) * sizeof(int));
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
int main()
{
int a[] = { 10,6,7,1,3,9,4,2,8 };
int sz = sizeof(a) / sizeof(a[0]);
MergeSortNOR(a, sz);
for (int i = 0; i < sz; i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
3.非比较排序——计数排序
3.1 基本思想
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
优化：可以采用相对映射，即遍历一遍数组，找最小和最大的，开辟最大-最小+1个int空间。(由此可见计数排序不适合浮点数)，然后每次元素计数时候，用该元素-最小的所得的数即为该元素的下标，该下标进行++。排序时候，用下标加上最小值。
负数也可以采用计数排序。
计数排序的动图：
代码
void CountSort(int* a, int n)
{
int i = 0;
int min = a[0];
int max = a[0];
for (i = 0; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int* count = (int*)calloc(max - min + 1, sizeof(int));
if (count == NULL)
{
perror("malloc fail");
return;
}
for (i = 0; i < n; i++)
{
int tmp = a[i] - min;
count[tmp]++;
}
int flag = 0;
for (i = 0; i < max - min + 1; i++)
{
if (flag < n)
{
while (count[i] > 0)
{
a[flag++] = i + min;
count[i]--;
}
}
}
}
特性总结
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
- 稳定性：稳定
排序性能对比
4.排序算法复杂度及稳定性分析
5.选择题练习
5.1 选择题一
1. 快速排序算法是基于（ ）的一个排序算法。
A分治法
B贪心法
C递归法
D动态规划法
答案:A
5.2 选择题二
2.对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，
当把第8个记录45插入到有序表时，为找到插入位置需比较（ ）次？
（采用从后往前比较）
A 3
B 4
C 5
D 6
答案:C
5.3 选择题三
3.以下排序方式中占用O（n）辅助存储空间的是（ ）
A 简单排序
B 快速排序
C 堆排序
D 归并排序
答案：D
5.4 选择题四
4.下列排序算法中稳定且时间复杂度为O(n^2)的是（ ）
A 快速排序
B 冒泡排序
C 直接选择排序
D 归并排序
答案：B
5.5 选择题五
5.关于排序，下面说法不正确的是（ ）
A 快排时间复杂度为O(N*logN)，空间复杂度为O(logN)
B 归并排序是一种稳定的排序,堆排序和快排均不稳定
C 序列基本有序时，快排退化成冒泡排序，直接插入排序最快
D 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)
答案：D
5.6 选择题六
6.下列排序法中，最坏情况下时间复杂度最小的是（ ）
A 堆排序
B 快速排序
C 希尔排序
D 冒泡排序
答案:A
5.7 选择题七
7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，
则以第一个关键字65为基准而得到的一趟快速排序结果是（）
A 34，56，25，65，86，99，72，66
B 25，34，56，65，99，86，72，66
C 34，56，25，65，66，99，86，72
D 34，56，25，65，99，86，72，66
答案:A
4.写在最后
其实排序不止这八种，还有基数排序，桶排序等等。因为效率低得问题，就不过多描述了。那么八大排序就到这里结束了。
