图解JavaScript合并排序.docx

合并排序是一个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语言实现代码如下：01#include 02 /合并过程03 void merge(int data,int start,int mid,int end)04 05 int *tmpLeft,*tmpRight;06 int leftSize,rightSize;07 int l,r,j;08 printArray(data,8);09 printf(n);10 l = 0;11 r = 0;12 j = 0;13 leftSize = mid - start + 1;14 rightSize = end - mid;15 tmpLeft = (int *)malloc(leftSize * sizeof(int);16 tmpRight = (int *)malloc(rightSize * sizeof(int);17 while(j leftSize)18 19 tmpLeftj = datastart + j;20 j+;21 22 j = 0;23 while(j rightSize)24 25 tmpRightj = datamid + 1 + j;26 j+;27 28 j = 0;29 while(l leftSize & r rightSize)30 31 if(tmpLeftl tmpRightr)32 33 datastart + j+ = tmpLeftl+;34 35 else36 37 datastart + j+ = tmpRightr+;38 39 40 while(l leftSize)41 42 datastart + j+ = tmpLeftl+;43 44 while(r rightSize)45 46 datastart + j+ = tmpRightr+;47 48 free(tmpLeft);49 free(tmpRight);50 51void merge_sort(int data,int start,int end)5253 int mid;54 if(start 0 & right.length 0)05 06 if (left0 right0)07 08 result.push(left.shift();/把最小的最先取出，放到结果集中09 10 else11 12 result.push(right.shift();13 14 15 return result.concat(left).concat(right);/剩下的就是合并，这样就排好序了1617function mergeSort(array)1819 if (array.length = 1) 20 21 return array;22 23 var middle = Math.floor(array.length / 2),/求出中点24 left = array.slice(0, middle),/分割数组25 right = array.slice(middle);26 return merge(mergeSort(left), mergeSort(right);/递归合并与排序27ruby版本：01def merge(left, right)02final = 03until left.empty? or right.empty?04final ( left.first right.first ? left.shift : right.shift )05end06final + left + right07end08def mergeSort(array)09return array if array.size 210left = array.first(array.size/2)11right = array.last(array.size - array.size/2)12merge(mergeSort(left), mergeSort(right)13end可运行版本：0102function merge(left, right)03 04 var result = ; 05 while (left.length 0 & right.length 0)06 07 if (left0 right0)08 09 result.push(left.shift();/把最小的最先取出，放到结果集中 10 11 else12 13 result.push(right.shift(); 14 15 16 return result.concat(left).concat(right);/剩下的就是合并，这样就排好序了 17 18function mergeSort(array)19 20 if (array.length = 1) 21 22 return array; 23 24 var middle = Math.floor(array.length / 2),/求出中点 25 left = array.slice(0, middle),/分割数组 26 right = array.slice(middle); 27 return merge(mergeSo