合并排序是一个O(nlogn)的算法,其基本思想就是一个分治的策略,先进行划分,然后再进行合并,下面举个例子。
有这样一组数据,{5,4,1,22,12,32,45,21},如果对它进行合并排序的话,首先将它从中间分开,这样,它就被分成了两个数组{5,4,1,22} {12,32,45,21}。
对这两个数组,也分别进行这样的操作,逐步的划分,直到不能再划分为止(每个子数组只剩下一个元素),这样,划分的过程就结束了。
划分的过程如下图所示:
接下来,我们进行合并操作,依照上图,划分过程是从上到下进行的,而合并的过程是从下往上进行的,例如上图中,最下层{5},{4}这两个数组,如果按升序排列,将他们合并后的数组就是{4,5}。{1},{22}这两个子数组合并后是{1,22}。而{4,5}与{1,22},这两个数组同属一个分支,他们也需要进行合并,由于这两个子数组本身就是有序的,所以合并的过程就是,每次从待合并的两个子数组中选取一个最小的元素,然后把这个元素放到合并后的数组中,前面两个数组合并后就是{1,4,5,22}。依次类推,直到合并到最上层结束,这是数据的排序已经完成了。
合并的过程如下图所示。这个过程是从下往上的。
C语言实现代码如下:
#include <stdlib.h> //合并过程 void merge(int data[],int start,int mid,int end) { int *tmpLeft,*tmpRight; int leftSize,rightSize; int l,r,j; printArray(data,8); printf("\n"); l = 0; r = 0; j = 0; leftSize = mid - start + 1; rightSize = end - mid; tmpLeft = (int *)malloc(leftSize * sizeof(int)); tmpRight = (int *)malloc(rightSize * sizeof(int)); while(j < leftSize) { tmpLeft[j] = data[start + j]; j++; } j = 0; while(j < rightSize) { tmpRight[j] = data[mid + 1 + j]; j++; } j = 0; while(l < leftSize && r < rightSize) { if(tmpLeft[l] < tmpRight[r]) { data[start + j++] = tmpLeft[l++]; } else { data[start + j++] = tmpRight[r++]; } } while(l < leftSize) { data[start + j++] = tmpLeft[l++]; } while(r < rightSize) { data[start + j++] = tmpRight[r++]; } free(tmpLeft); free(tmpRight); } void merge_sort(int data[],int start,int end) { int mid; if(start < end) { //将数组划分 mid = (start + end) / 2; merge_sort(data,start,mid); merge_sort(data,mid + 1,end); //合并划分后的两个数组 merge(data,start,mid,end); } }
javascript版本:
function merge(left, right) { var result = []; while (left.length > 0 && right.length > 0) { if (left[0] < right[0]) { result.push(left.shift());//把最小的最先取出,放到结果集中 } else { result.push(right.shift()); } } return result.concat(left).concat(right);//剩下的就是合并,这样就排好序了 } function mergeSort(array) { if (array.length == 1) { return array; } var middle = Math.floor(array.length / 2),//求出中点 left = array.slice(0, middle),//分割数组 right = array.slice(middle); return merge(mergeSort(left), mergeSort(right));//递归合并与排序 }
ruby版本:
def merge(left, right) final = [] until left.empty? or right.empty? final << ( left.first < right.first ? left.shift : right.shift ) end final + left + right end def mergeSort(array) return array if array.size < 2 left = array.first(array.size/2) right = array.last(array.size - array.size/2) merge(mergeSort(left), mergeSort(right)) end
可运行版本:
<script language="javascript"> function merge(left, right) { var result = []; while (left.length > 0 && right.length > 0) { if (left[0] < right[0]) { result.push(left.shift());//把最小的最先取出,放到结果集中 } else { result.push(right.shift()); } } return result.concat(left).concat(right);//剩下的就是合并,这样就排好序了 } function mergeSort(array) { if (array.length == 1) { return array; } var middle = Math.floor(array.length / 2),//求出中点 left = array.slice(0, middle),//分割数组 right = array.slice(middle); return merge(mergeSort(left), mergeSort(right));//递归合并与排序 } var a = [49, 38 ,65 ,97 ,76, 13, 27] document.write(mergeSort(a)); </script>
运行结果:
13,27,38,49,65,76,97