排序算法——归并排序

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

分而治之

排序算法——归并排序

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

合并相邻有序子序列

再来看看阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

排序算法——归并排序

代码实现

JAVA版:

  1. package algorithm;
  2. public class Sort_merge {
  3.     //打印数组
  4.     public static void printArr(int[] arr) {
  5.         for (int i:arr)
  6.             System.out.print(i+" ");
  7.         System.out.println();
  8.     }
  9.     private static void merge(int[] arr,int left,int mid,int right,int[] temp){
  10.         int i = left;//左序列指针
  11.         int j = mid+1;//右序列指针
  12.         int t = 0;//临时数组指针
  13.         while (i<=mid && j<=right){
  14.             if(arr[i]<=arr[j]){
  15.                 temp[t++] = arr[i++];
  16.             }else {
  17.                 temp[t++] = arr[j++];
  18.             }
  19.         }
  20.         while(i<=mid){//将左边剩余元素填充进temp中
  21.             temp[t++] = arr[i++];
  22.         }
  23.         while(j<=right){//将右序列剩余元素填充进temp中
  24.             temp[t++] = arr[j++];
  25.         }
  26.         t = 0;
  27.         //将temp中的元素全部拷贝到原数组中
  28.         while(left <= right){
  29.             arr[left++] = temp[t++];
  30.         }
  31.         //打印每一轮排序的结果
  32.         printArr(arr);
  33.     }
  34.     private static void mergeSort(int[] arr,int left,int right,int []temp){
  35.         if(left<right){
  36.             int mid = (left+right)/2;
  37.             mergeSort(arr,left,mid,temp);//左边归并排序,使得左子序列有序
  38.             mergeSort(arr,mid+1,right,temp);//右边归并排序,使得右子序列有序
  39.             merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
  40.         }
  41.     }
  42.     public static void main(String args[]) {
  43.         int[] arr = {6,1,2,7,9,3,4,5,10,8};
  44.         int []temp = new int[arr.length];//在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
  45.         mergeSort(arr,0,arr.length-1,temp);
  46.     }
  47. }

这是在网上看到的一个帖子,主要是图文部分让大家一看就能明白“归并算法”的要义,适合小白们学习,所以也扒来放到“菠菜园”上。下面我为大家再补充一个PHP版的。

  1. <?php
  2. class SortTest {
  3.     //归并主函数
  4.     public function merge_sort(array &$arr){
  5.         $start = 0;
  6.         $end = count($arr) - 1;
  7.         $this->mSort($arr,$start,$end);
  8.     }
  9.     private function msort(array &$arr,$start,$end){
  10.         if($start < $end){
  11.             //当子序列长度为1时,$start == $end,不用再分组
  12.             $mid = floor(($start + $end) / 2);  //将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]
  13.             $this->msort($arr,$start,$mid);         //将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]
  14.             $this->msort($arr,$mid + 1,$end);       //将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]
  15.             $this->merge($arr,$start,$mid,$end);       //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
  16.         }
  17.     }
  18.     //归并操作
  19.     private function merge(array &$arr,$start,$mid,$end){
  20.         $i = $start;
  21.         $j=$mid + 1;
  22.         $k = $start;
  23.         $temparr = array();
  24.         while($i!=$mid+1 && $j!=$end+1){
  25.            if($arr[$i] >= $arr[$j]){
  26.                $temparr[$k++] = $arr[$j++];
  27.            }else{
  28.                $temparr[$k++] = $arr[$i++];
  29.            }
  30.         }
  31.         //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  32.         while($i != $mid+1){
  33.             $temparr[$k++] = $arr[$i++];
  34.         }
  35.         //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  36.         while($j != $end+1){
  37.             $temparr[$k++] = $arr[$j++];
  38.         }
  39.         for($i=$start$i<=$end$i++){
  40.             $arr[$i] = $temparr[$i];
  41.         }
  42.     }
  43. }
  44. ?>

算法原理都是一样的,至于JS、python等其实都差不多。所以程序员一个很重要的品质就是学编程要会悟,会触类旁通。

再比如前端JS一样可以实现,参考代码如下:

  1. function merge(left, right) {
  2.   var tmp = [];
  3.   while (left.length && right.length) {
  4.     if (left[0] < right[0])
  5.       tmp.push(left.shift());
  6.     else
  7.       tmp.push(right.shift());
  8.   }
  9.   return tmp.concat(left, right);
  10. }
  11. function mergeSort(a) {
  12.   if (a.length === 1)
  13.     return a;
  14.   var mid = ~~(a.length / 2)
  15.     , left = a.slice(0, mid)
  16.     , right = a.slice(mid);
  17.   return merge(mergeSort(left), mergeSort(right));
  18. }

 

波波
你想把广告放到这里吗?

发表评论

您必须 登录 才能发表留言!