常见的五类排序算法图解和实现(归并类:二路归并排序)

简介:

归并类的排序算法

归并:将两个或两个以上的有序表组合成一个新的有序表。

内部排序中,通常采用的是 2-路归并排序。即:将两个位置相邻的记录有序子序列归并为一个记录有序的序列。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

图解如下

看成是 n 个有序的子序列(长度为 1),然后两两归并。

得到 n/2 个长度为2 或 1 的有序子序列。继续亮亮归并

最后一趟

代码如下:

复制代码
 1 //二路一次归并过程的算法
 2 //low为本次二路归并排序的第1有序区的第1个元素,i指向第1个元素, mid为第1有序区的最后1个元素
 3 void merge(int List[], int low, int mid, int high)
 4 {
 5     //mid+1为第2有序区第1个元素,mid为第1有序区的最后1个元素
 6     //i 指向第 1 有序区的第 1 个元素
 7     int i = low;
 8     //j 指向第 2 有序区的第 1 个元素,high 为第 2 有序区的最后一个元素
 9     int j = mid + 1;
10     //temp数组暂存合并的有序序列
11     int *temp = new int[high - low + 1];
12     //设置临时数组的指示标志 k
13     int k = 0;
14     //内存分配失败
15     if(!temp){
16         cout<<"数组分配失败!";
17         exit(0);
18     }
19     //顺序选取两个有序区的较小元素,存储到t数组中,因为是递增排序
20     while(i <= mid && j <= high){
21         //较小的元素,存入temp临时数组中
22         if(List[i] <= List[j]){
23             temp[k++] = List[i++];
24         }else{
25             temp[k++] = List[j++];
26         }
27     }// end of while
28     //比完之后,假如第1个有序区仍有剩余,则直接全部复制到 temp 数组
29     while(i <= mid){
30         temp[k++] = List[i++];
31     }
32     //比完之后,假如第2个有序区还有剩余,则直接全部复制到 temp 数组
33     while(j <= high){
34         temp[k++] = List[j++];
35     }
36     //将排好序的序列,重存回到 list 中 low 到 high 区间
37     for(i = low, k = 0; i <= high; i++, k++){
38         List[i] = temp[k];
39     }
40     //delete [] 删除动态数组的内存
41     delete []temp;
42 }
43 
44 //递归实现二路归并排序(也就是分治法的思想)
45 void mergeSort(int List[], int low, int high)
46 {
47     //二路归并排序,分为二路
48     int mid = (low + high) / 2;
49     //终止条件,low >= high, 不是while,且不含等号,否则死循环
50     if(low < high)
51     {
52         //递归过程,二路归并排序递归过程
53         mergeSort(List, low, mid);
54         mergeSort(List, mid + 1, high);
55         //归并
56         merge(List, low, mid, high);
57     }
58 }
59 
60 int main(void)
61 {
62     int source[7] = {49, 38, 65, 97, 76, 13, 27};
63     
64     mergeSort(source, 0, 6);
65     
66     for (int i = 0; i < 7; i++) {
67         printf(" %d  ", source[i]);
68     }
69     
70     return 0;
71 }
复制代码

上述代码使用的是递归的方式,递归函数里,递归语句之前的语句和各级被调的递归函数执行顺序一致,而递归语句之后的语句和被调的递归函数执行顺序相反。这就是为什么 merge 函数要放在递归语句(两条递归语句)之后,因为是逆向执行的。联系二路归并排序的过程!!

还可以使用非递归的方式,代码如下:

复制代码
 1 //非递归算法实现二路归并排序,length代表数组长度,即数组最大下标是 legth - 1
 2 void mergeSort(int List[],int length)
 3 {
 4     //回忆图解的过程,二路归并算法的流程,不同于递归,递归是先递归语句,然后归并函数,这样归并函数是倒序执行(和递归函数执行顺序相反)
 5     int size = 1;
 6     int low;
 7     int mid;
 8     int high;
 9     //size 是标记当前各个归并序列的high-low,从1,2,4,8,……,2*size
10     while(size <= length - 1)
11     {
12         //从第一个元素开始扫描,low代表第一个分割的序列的第一个元素
13         low = 0;
14         //当前的归并算法结束的条件
15         while(low + size <= length - 1)
16         {
17             //mid代表第一个分割的序列的最后一个元素
18             mid = low + size - 1;
19             //high 代表第二个分割的序列的最后一个元素
20             high = mid + size;
21             //判断一下:如果第二个序列个数不足size个
22             if(high > length - 1){
23                 //调整 high 为最后一个元素的下标即可
24                 high = length - 1;
25             }
26             //调用归并函数,进行分割的序列的分段排序
27             merge(List, low, mid, high);
28             //打印出每次归并的区间
29             cout << "low:" << low << " mid:" << mid << " high:" << high << endl;
30             //下一次归并时第一序列的第一个元素位置
31             low = high + 1;
32         }// end of while
33         //范围扩大一倍,二路归并的过程
34         size *= 2;
35     }// end of while
36 }
复制代码

二路归并排序算法分析

每趟归并的时间复杂度为O(n),共需进行 log2 n 趟。

二路归并排序的时间复杂度:等于归并趟数与每一趟时间复杂度的乘积。时间复杂度为O(nlog2n)。

利用二路归并排序时,需要利用与待排序数组相同的辅助数组作临时单元,故该排序方法的空间复杂度为O(n)比前面介绍的其它排序方法占用的空间大。

由于二路归并排序中,每两个有序表合并成一个有序表时,若分别在两个有序表中出现有相同排序码,则会使前一个有序表中相同排序码先复制,后一有序表中相同排序码后复制,从而保持它们的相对次序不会改变。所以,二路归并排序是一种稳定的排序方法。

归并的思想主要用于外部排序:

外部排序可分两步
①待排序记录分批读入内存,用某种方法在内存排序,组成有序的子文件,再按某种策略存入外存。
②子文件多路归并,成为较长有序子文件,再记入外存,如此反复,直到整个待排序文件有序。
外部排序可使用外存、磁带、磁盘,最初形成有序子文件长取决于内存所能提供排序区大小和最初排序策略,归并路数取决于所能提供排序的外部设备数。

 

辛苦的劳动,转载请注明出处,谢谢……
http://www.cnblogs.com/kubixuesheng/p/4355865.html
相关文章
|
1月前
|
机器学习/深度学习 算法 搜索推荐
【初阶算法4】——归并排序的详解,及其归并排序的扩展
【初阶算法4】——归并排序的详解,及其归并排序的扩展
【初阶算法4】——归并排序的详解,及其归并排序的扩展
|
2月前
|
算法 前端开发 搜索推荐
前端算法之归并排序
前端算法之归并排序
20 0
|
1天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
11 4
|
11天前
|
算法 搜索推荐 C#
|
14天前
|
数据采集 算法 安全
CVPR 2024:给NeRF开透视眼!稀疏视角下用X光进行三维重建,9类算法工具包全开源
【6月更文挑战第28天】CVPR 2024亮点:SAX-NeRF框架开源!融合X光与NeRF,提升3D重建效果。X3D数据集验证,Lineformer+MLG策略揭示物体内部结构,增强几何理解。虽有计算成本及泛化挑战,但为计算机视觉和医学影像开辟新路径。[论文链接](https://arxiv.org/abs/2311.10959)**
33 5
|
22天前
|
搜索推荐 算法 Java
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治,以基准元素划分数组并递归排序;归并排序同样分治,先分割再合并有序子数组;堆排序通过构建堆来排序,保持堆性质并交换堆顶元素。每种算法各有优劣:快排平均高效,最坏O(n²);归并稳定O(n log n)但需额外空间;堆排序O(n log n)且原地排序,但不稳定。
22 3
|
1月前
|
算法
数据结构与算法-归并排序
数据结构与算法-归并排序
15 2
|
2月前
|
存储 搜索推荐 算法
归并排序算法深入解析
归并排序算法深入解析
|
19天前
|
搜索推荐 C语言
【C/排序算法】:快速排序和归并排序的非递归实现
【C/排序算法】:快速排序和归并排序的非递归实现
12 0
|
19天前
|
搜索推荐 算法
【C/排序算法】:归并排序和计数排序
【C/排序算法】:归并排序和计数排序
12 0