基础算法 | 最终章-8 归并排序
我们已经在本系列文章中已经学习了7种算法，其中一种是查找算法，六种是排序算法。本篇文章是基础算法系列的最后一章，我们将学习最后一个排序算法——归并排序。让我们话不多说，开始学习吧~
归并排序
归并排序是一种效率较高的排序，它用到了我们算法设计方法里面的分治算法（在后面的新主题文章会讲述）,在处理大量排序数据时，归并排序的效率比我们之前所学的冒泡排序，直接插入排序等算法要快很多。归并排序，我们从这个名字中似乎就能看出其算法思想——归并嘛，那怎么个归并法呢？那让我们来详细看看其思想吧。
归并排序的算法思想
我们先想想这样一个问题，假设我们有两个有序的数列，我们怎么把这两个数列合并成一个有序的数列呢？我们可以这样做，我们分别从两个数列的第一个元素开始，相互比较，因为这两个数列都是有序的，所以比较之后，将小的元素临时插入到一个第三个数列的第一个元素，然后将这个小的元素从所属的数列中"去掉"，然后取这个数列的下一个元素和另外一个数列的那个较大（此处为第一个）元素进行比较，同样，我们将小的元素临时插入到第三个数列的第二个位置，以此类推。经过这样一轮比较之后，开始的两个数列肯定会有一个数列"剩余"元素，我们将剩余的元素依次插入到上述的第三个数列中，这样，这个第三个数列就是我们想要的那个合并以后的数列。解决了这个问题之后，我们就知道了归并排序的算法思想，即我们可以将待排序的数列中每一个单一的元素看成一个有序的数列，然后将它们两两按上述方式合并得到了n/2（假设有n个元素）个有序数列，再将其两两合并，重复此过程直到最后合并成一个数列，不就得到了我们所需要的有序数列嘛~
归并排序的实现过程
假设待排序数列a长度为n，第一个元素索引位置为start，最后一个为end。我们可以将数列"分割"为n个有序数列，然后再通过merge函数两两合并，得到我们需要的结果。那我们怎么"分割"呢？对了，我们通过递归来实现，我们每次取中间位置mid=（start+end）/2，然后对a[start~mid]与a[mid+1~end]两部分元素分别进行划分，这样通过不断递归，划分数组直到每个数列只有一个元素，然后在进行不断地两两合并，得到结果。此外，我们还需考虑一个问题，就是每次两两合并时我们都需要一个第三个临时数列用来储存结果，如果每次合并时都新产生一个数列，这样会十分影响算法的效率。所以我们可以在算法中预先定义一个temp数组，让每次合并的时候都共享这个数组。
代码实现
public static void mergeSort(int[]a ,int start,int end){ //对下面的mergeSort方法进行封装
int[] temp = new int[a.length]; //定义中间变量temp数组
mergeSort(a, temp, start, end); //调用未进行封装的mergeSort方法
}
public static void mergeSort(int[]a,int[] temp,int start,int end){
if(start < end){ //当待排序元素的长度大于1时
int mid = (start+end)/2;
mergeSort(a, temp, start, mid); //对 待排序的元素左边进行排序
mergeSort(a, temp, mid+1, end); //对 待排序的元素右边进行排序
merge(a,temp,start,mid,end); //合并左右两边元素，即a[start~mid]与a[mid+1~end]两部分元素进行合并
}
}
//对a[start~mid]与a[mid+1~end]两部分元素进行合并
public static void merge(int[]a,int[] temp,int start,int mid,int end){
//对两部分元素start位置进行标记，即从第一个（最小的）元素开始（此处也可以标记末端,从最大的元素开始，并修改下面的比较）
int i =start,j=mid+1;
int k = 0; //标记中间值temp数组的位置
while(i <= mid && j <= end){ //当两部分元素都未到达末端时
if(a[i]<a[j]){ //若a[i]<a[j],将a[i]插入到temp中，之后标记i,k向后移动一个位置
temp[k] = a[i];
i++;
k++;
}
else{ //若a[i]>=a[j],将a[j]插入到temp中，之后标记j,k向后移动一个位置
temp[k] = a[j];
j++;
k++;
}
}
if(i == mid+1){ //当i等于length1时，则将后半部分剩余的元素全部依次插入到temp的后面
while(j<=end){
temp[k] = a[j];
j++;
k++;
}
}
if(j == end+1){ //当j等于length2时，则将前半部分剩余的元素全部依次插入到temp的后面
while(i<=mid){
temp[k] = a[i];
i++;
k++;
}
}
//将temp中排好序的元素依次赋值给数组a对应位置元素
for(int x =0;x<k;x++){
//注意此处应为a[start+x]，因为a[start~mid]与a[mid+1~end]两部分元素中start不一定是从索引0开始的
a[start+x] = temp[x];
}
}让我们运行下面代码，来测试下我们的算法吧
public static void main(String[] args) {
int[] a = new int[]{4,16,79,20,30,16,52,2,1};
mergeSort(a,0, a.length-1);
System.out.println(Arrays.toString(a));//打印出数组a
}结果为：
又到了我们最熟悉的环节了，上题咯~
HDU 2561 第二小整数
Problem Description 求n个整数中倒数第二小的数。 每一个整数都独立看成一个数,比如,有三个数分别是1,1,3,那么,第二小的数就是1。
Input 输入包含多组测试数据。 输入的第一行是一个整数C,表示有C测试数据; 每组测试数据的第一行是一个整数n,表示本组测试数据有n个整数(2<=n<=10),接着一行是 n个整数 (每个数均小于100);
Output 请为每组测试数据输出第二小的整数,每组输出占一行。
Sample Input 2 2 1 2 3 1 1 3
Sample Output 2 1
分析：是不是感觉有上面我们测试例子的影子呢，只要对每组数进行排序，找出按升序排序的第二个数即可。刚刚我们学的归并排序就可以派上用场了。
代码实现：
public static void main(String[] args) {
int n,m; //n组测试数据，m为每一组数据的个数
Scanner input = new Scanner(System.in);
System.out.println("请输入数据的组数：");
n = input.nextInt();
int[] result = new int[n]; //记录每一组的结果
for(int i=0;i<n;i++){
System.out.println("请输入本组测试数据的个数：");
m=input.nextInt();
int[] a = new int[m];//保存本组数据
System.out.println("请输入本组测试数据：");
for(int j=0;j<m;j++){
a[j] =input.nextInt();
}
mergeSort(a, 0, m-1); //对本组数据进行排序
result[i] = a[1]; //获取第二小的整数
}
for(int i :result){
System.out.println(i+" ");
}
}
public static void mergeSort(int[]a ,int start,int end){ //对下面的mergeSort方法进行封装
int[] temp = new int[a.length]; //定义中间变量temp数组
mergeSort(a, temp, start, end); //调用未进行封装的mergeSort方法
}
public static void mergeSort(int[]a,int[] temp,int start,int end){
if(start < end){ //当待排序元素的长度大于1时
int mid = (start+end)/2;
mergeSort(a, temp, start, mid); //对 待排序的元素左边进行排序
mergeSort(a, temp, mid+1, end); //对 待排序的元素右边进行排序
merge(a,temp,start,mid,end); //合并左右两边元素，即a[start~mid]与a[mid+1~end]两部分元素进行合并
}
}
/**
* 对a[start~mid]与a[mid+1~end]两部分元素进行合并
*/
public static void merge(int[]a,int[] temp,int start,int mid,int end){
//对两部分元素start位置进行标记，即从第一个（最小的）元素开始（此处也可以标记末端,从最大的元素开始，并修改下面的比较）
int i =start,j=mid+1;
int k = 0; //标记中间值temp数组的位置
while(i <= mid && j <= end){ //当两部分元素都未到达末端时
if(a[i]<a[j]){ //若a[i]<a[j],将a[i]插入到temp中，之后标记i,k向后移动一个位置
temp[k] = a[i];
i++;
k++;
}
else{ //若a[i]>=a[j],将a[j]插入到temp中，之后标记j,k向后移动一个位置
temp[k] = a[j];
j++;
k++;
}
}
if(i == mid+1){ //当i等于length1时，则将后半部分剩余的元素全部依次插入到temp的后面
while(j<=end){
temp[k] = a[j];
j++;
k++;
}
}
if(j == end+1){ //当j等于length2时，则将前半部分剩余的元素全部依次插入到temp的后面
while(i<=mid){
temp[k] = a[i];
i++;
k++;
}
}
//将temp中排好序的元素依次赋值给数组a对应位置元素
for(int x =0;x<k;x++){
//注意此处应为a[start+x]，因为a[start~mid]与a[mid+1~end]两部分元素中start不一定是从索引0开始的
a[start+x] = temp[x];
}
}总述
归并排序是一种效率较高的排序算法，尤其在处理大量数据排序时有较大的优势。它用到了我们算法设计方法里面的分治算法（将在新主题文章中讲述，敬请期待~）。你是否get到了呢~ヾ(◍°∇°◍)ﾉﾞ