[数据结构]归并排序

2019独角兽企业重金招聘Python工程师标准>>>

归并排序

简述

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
其对数组进行排序时的基本操作在于两个有序序列进行合并操作。其代码部分在后面给出。
而进行整体数组排序时，可先将n个元素看作n个有序序列，对其两两进行合并，于是结果成为floor(n/2)个有序序列，再将其进行两两合并。直到最终合并成为一个整体有序序列。

后面给出的算法包含两个版本。一个是递归方法，另一个是非递归方法。其中递归方法是分治法的典型应用。

代码实例

#include<iostream>
using namespace std;
void dispList(int raw[], int n){
	//打印数组
	//from 1 to n not 0 to n
	for (int i = 1; i <= n; i++) cout << raw[i] << ' ';
}

void mergeSort(int raw[], int n){
	//merge with no recursion非递归方法
	int *temp = new int[n + 1]; //由于合并操作的辅助空间需要对等的长度
	for (int i = 1; i < n; i = i * 2){//两两归并，直到归并的长度大于序列长度跳出
		int right_a, right_b, left_a, left_b;	//每次比较[left_a...left_b-1]; [right_a...right_b-1]
		int cursor = 1;//记录相对位置，每进行一趟归并将其重新置为1
		for (left_a = 1; left_a <= n - i; left_a = right_b){
			left_b = right_a = left_a + i;
			right_b = right_a + i;
			if (right_b>n + 1) right_b = n + 1;//如果甩下一个尾巴不够i长度，那么直接将right_b置n+1;
			//如下格式是经典的合并三段while语句
			while (left_a < left_b && right_a<right_b)
				temp[cursor++] = (raw[left_a]<raw[right_a]) ? (raw[left_a++]) : (raw[right_a++]);
			while (left_a < left_b)
				temp[cursor++] = raw[left_a++];
			while (right_a < right_b)
				temp[cursor++] = raw[right_a++];
		}
		//将辅助空间写入原始序列.
		while ((--cursor) != 0)
			raw[cursor] = temp[cursor];
	}
	delete [] temp;
}
//以下给出递归方法，注意体会分治思想。
void merge_joint(int raw[], int temp[], int start, int middle, int end){
    //每次meger raw[start...middle-1] and raw[middle...end]
    int cursor_l = start, cursor_r = middle;
    int cursor = start;
    //同样，三段经典while合并语句
    while (cursor_l < middle && cursor_r <= end)
        temp[cursor++] = (raw[cursor_l] < raw[cursor_r]) ? raw[cursor_l++] : raw[cursor_r++];
    while (cursor_l < middle)
        temp[cursor++] = raw[cursor_l++];
    while (cursor_r <= end)
        temp[cursor++] = raw[cursor_r++];
    while ((--cursor) >= start) 
        raw[cursor] = temp[cursor];//合并好后写入原始序列
}
void merge_R(int raw[], int temp[], int n, int start, int end){
    if (start == end) return;
    else{
        int mid = (start + end) / 2;
        //先合并左面，再合并右边，最后合并整体
        merge_R(raw, temp, n, start, mid);    
        merge_R(raw, temp, n, mid + 1, end);
        merge_joint(raw, temp, start, mid + 1, end);
    }
}
void mergeSortRe(int raw[], int n){
    //最后调用归并排序
    int *temp = new int[n + 1];
    merge_R(raw, temp, n, 1, n);//需要传入辅助空间
    delete [] temp;
}

void main(){
    int a[9] = { 0, 3, 4, 8, 6, 7, 23, 21, 18 };
    mergeSortRe(a, 8);
    dispList(a, 8);

}