0


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

大家好我是沐曦希💕

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

文章目录

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

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

在这里插入图片描述


本文转载自: https://blog.csdn.net/m0_68931081/article/details/126784275
版权归原作者 沐曦希 所有, 如有侵权,请联系我们删除。

“【数据结构初阶】八大排序(三)&mdash;&mdash;归并排序&amp;&amp;计数排序”的评论:

还没有评论