【数据结构初阶】八大排序(三)——归并排序&&计数排序

大家好我是沐曦希💕

往期博客：【数据结构初阶】八大排序(一)——希尔排序&&堆排序&&直接插入排序&&直接选择排序
【数据结构初阶】八大排序(二)——快速排序&&冒泡排序

文章目录

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));}voidMergeSort(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 特性总结

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

排序性能对比

voidtestOp(){srand((unsignedint)time(0));constint 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>voidMergeSortNOR(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;}intmain(){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");return0;}

3.非比较排序——计数排序

3.1 基本思想

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

优化：可以采用相对映射，即遍历一遍数组，找最小和最大的，开辟最大-最小+1个int空间。(由此可见计数排序不适合浮点数)，然后每次元素计数时候，用该元素-最小的所得的数即为该元素的下标，该下标进行++。排序时候，用下标加上最小值。
负数也可以采用计数排序。

计数排序的动图：

代码

voidCountSort(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]--;}}}}

特性总结

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定

排序性能对比

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.写在最后

其实排序不止这八种，还有基数排序，桶排序等等。因为效率低得问题，就不过多描述了。那么八大排序就到这里结束了。