第十九章 合并排序法
::: hljs-center
目录
第十九章 合并排序法
●前言
●认识排序
●一、合并排序法是什么？
1.简要介绍
2.具体情况
3.算法分析
●二、案例实现
1.案例一
●总结
:::
前言
排序算法是我们在程序设计中经常见到和使用的一种算法，它主要是将一堆不规则的数据按照递增或递减的方式重新进行排序。在如今的互联网信息时代，随着大数据和人工智能的发展，大型企业的数据库中有亿级的用户数据量。因此对其进行处理，排序算法也就成为了其中必不可缺的步骤之一。
认识排序
排序功能对计算机领域而言，是一项非常重要而且普遍的工作。排序中数据的移动方式可分为直接移动和逻辑移动两种方式，直接移动是直接交换存储数据的位置，而逻辑移动并不会移动数据存储的位置，仅改变指向这些数据辅助指针的值。排序通常按照数据量的多少和所使用的内存，可分为内部排序和外部排序，数据量小可以全部加载到内存来进行排序的，就称为内部排序，大部分排序属于此类。数据量大而无法一次性加载到内存中，必须借助磁带，磁盘等辅助存储器进行排序的，则称为外部排序。随着数据结构科学的进步，如今，陆续被提出的冒泡排序法，选择排序法，插入排序法，合并排序法，快速排序法，堆积排序法，希尔排序法，基数排序法，直接合并排序法等等，它们各有其特色和其应用场合。并且在算法中，我们非常关注算法程序代码的时间复杂度和空间复杂度，因为它会直接体现出我们程序代码的执行效率以及编程人员的逻辑思维等等的综合能力。当数据量相当庞大时，排序算法所花费的时间就显得相当重要，排序算法的时间复杂度可分为最好情况、最坏情况以及平均情况。另外，对于任何的排序算法都会有数据交换的操作，数据互换位置会暂时用到一个额外的空间，这也是排序算法中空间复杂度要考虑到的问题，而在排序算法中所使用的额外空间越小，它的空间复杂度就越好。
一、合并排序法是什么？
1.简要介绍
合并排序法是针对已经排序好的两个或两个以上的数列，通过合并的方式将其组合成一个大的且已经排好序的数列。即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列，该排序法也用到了分治法分而治之的思想。
2.具体情况
合并排序法的具体步骤如下：
（1）将N个长度为1的键值成对地合并为N/2个长度为2地键值组。
（2）将N/2个长度为2地键值成对地合并为N/4个长度为4地键值组。
（3）将键值组不断地去合并，直到合并成一组长度为N的键值组为止。
下面用合并排序法对40、10、42、75、51、99、66、24这十个数据元素进行从小到大的排序，具体情况如下图所示：
上面的图片中展示的是简单的一种合并排序法，其又被称为2-way合并排序（适用于偶数个数据）。我们可以将它的排序步骤进行整理：把初始时的8个长度为1的数列合并成4个已经排序完成且长度为2的数列；再将4个长度为2的数列合并成2个已经排序完成且长度为4的数列；最后将2个长度为4的数列合并成1个已经排序完成且长度为8的数列。
3.算法分析
①合并排序法的n个数据一般需要处理约log2^n次， 每次处理的时间复杂度为O(n)。所以该排序法的最好情况，最坏情况以及平均情况的时间复杂度为O(nlog2^n)。 ②合并排序法在排序过程中需要一个与数据文件大小同样的额外空间，所以空间复杂度O(n)。 ③合并排序法是稳定排序法。
二、案例实现
1.案例一
①范例情况：用合并排序法，对在快速排序法下已经排序好的数列一16，25，39，27，30，42和数列二12，8，45，63，20，99这两组数据的12个数据进行从小到大的排序。 ②代码展示：
#include<iostream>
using namespace std;
//事先声明排序数据的个数
#define size_1 6
#define size_2 6
class sort{
public:
int data_1[size_1];
int data_2[size_2];
int data_3[size_1 + size_2];
void showresult(int len,int data[]) {
for (int i = 0; i < len; i++)
cout << data[i] << " ";
cout << endl;
}
};
class quick :public sort {
public:
void quick_start(int left, int right,int data[]) {
int left_idx, right_idx;
int temp;
if (left < right)
{
left_idx = left + 1;
right_idx = right;
while (1)
{
//从左向右扫描，找出一个键值大于data[left]的数据元素
for (int i = left + 1; i <= right; i++)
{
if (data[i] > data[left])
{
left_idx = i;
break;
}
left_idx++;
}
//从右向左扫描，找出一个键值小于data[left]的数据元素
for (int j = right; j >= left + 1; j--)
{
if (data[j] < data[left])
{
right_idx = j;
break;
}
right_idx--;
}
//如果left_idx<right_idx，将二者交换位置
if (left_idx < right_idx) {
temp = data[left_idx];
data[left_idx] = data[right_idx];
data[right_idx] = temp;
}
else {
break;
}
}
//如果left_idx>=right_idx
if (left_idx >= right_idx)
{
//将data[left]与data[right_idx]交换位置
temp = data[left];
data[left] = data[right_idx];
data[right_idx] = temp;
//以递归的方式继续进行左半的快速排序
quick_start(left, right_idx - 1,data);
//以递归的方式继续进行右半的快速排序
quick_start(right_idx + 1, right,data);
}
}
}
};
class merge :public sort {
public:
void merge_start(int data_1[],int data_2[],int data_3[]) {
int i = 0, j = 0, k = 0;
//进行数据的合并排序
while (i<size_1&&j<size_2)
{
if (data_1[i] <= data_2[j])
data_3[k++] = data_1[i++];
else
data_3[k++] = data_2[j++];
}
//再次检查判断,是否合并完成
while (i < size_1)
data_3[k++] = data_1[i++];
while (j < size_2)
data_3[k++] = data_2[j++];
}
};
void text()
{
sort s;
quick q;
merge g;
cout << "请输入数列1中的" << size_1 << "个数据：";
for (int i = 0; i < size_1; i++)
cin >> s.data_1[i];
cout << "请输入数列2中的" << size_2 << "个数据：";
for (int i = 0; i < size_2; i++)
cin >> s.data_2[i];
//先利用最佳的快速排序法对两组数据进行分别排序
q.quick_start(0,size_1-1,s.data_1);
q.quick_start(0,size_2-1,s.data_2);
cout << "排序后的数列1:"; s.showresult(size_1, s.data_1);
cout << "排序后的数列2:"; s.showresult(size_2, s.data_2);
//再利用合并排序法去将1，2两个数据列合并到数据列3中
g.merge_start(s.data_1,s.data_2,s.data_3);
cout << "合并后的数列："; s.showresult(size_1 + size_2,s.data_3);
}
int main()
{
text();
}
③代码展示：
总结
以上就是合并排序法的讲解，合并排序法其实更广泛的用于多个已经经过排序法排序好的数列，然后将多个数列进行合并的问题。我也在上面的案例实现中，刻意的去举了这样的一个案例，让大家去更好的去理解多个排序算法的综合应用，从而提高我们对算法的综合使用能力。
<您的三连和关注是我最大的动力> ???? 文章作者：Keanu Zhang 分类专栏：算法之美（C++系列文章）