详解归并排序

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

专注于为中小企业提供成都网站建设、网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业清河免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了近千家企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  1. 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
  2. 自下而上的迭代;

在《数据结构与算法 JavaScript 描述》中,作者给出了自下而上的迭代方法。但是对于递归法,作者却认为:

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。

说实话,我不太理解这句话。意思是 JavaScript 编译器内存太小,递归太深容易造成内存溢出吗?还望有大神能够指教。

和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

算法步骤

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
  4. 重复步骤 3 直到某一指针达到序列尾;
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

动图演示

代码实现

JavaScript

实例

function mergeSort(arr) {  // 采用自上而下的递归方法
   var len = arr.length;
   if(len return arr;
   }
   var middle = Math.floor(len / 2),
       left = arr.slice(0, middle),
       right = arr.slice(middle);
   return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
   var result = [];

   while (left.length && right.length) {
       if (left[0] else {
           result.push(right.shift());
       }
   }

   while (left.length)
       result.push(left.shift());

   while (right.length)
       result.push(right.shift());

   return result;
}

Python

实例

def mergeSort(arr):
   import math
   if(len(arr)return arr
   middle = math.floor(len(arr)/2)
   left, right = arr[0:middle], arr[middle:]
   return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
   result = []
   while left and right:
       if left[0] else:
           result.append(right.pop(0));
   while left:
       result.append(left.pop(0))
   while right:
       result.append(right.pop(0));
   return result

Go

实例

func mergeSort(arr []int) []int {
       length := len(arr)
       if length return arr
       }
       middle := length / 2
       left := arr[0:middle]
       right := arr[middle:]
       return merge(mergeSort(left), mergeSort(right))
}

func merge(left []int, right []int) []int {
       var result []int
       for len(left) != 0 && len(right) != 0 {
               if left[0] else {
                       result = append(result, right[0])
                       right = right[1:]
               }
       }

       for len(left) != 0 {
               result = append(result, left[0])
               left = left[1:]
       }

       for len(right) != 0 {
               result = append(result, right[0])
               right = right[1:]
       }

       return result
}

Java

实例

public class MergeSort implements IArraySort {

   @Override
   public int[] sort(int[] sourceArray) throws Exception {
       // 对 arr 进行拷贝,不改变参数内容
       int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

       if (arr.length return arr;
       }
       int middle = (int) Math.floor(arr.length / 2);

       int[] left = Arrays.copyOfRange(arr, 0, middle);
       int[] right = Arrays.copyOfRange(arr, middle, arr.length);

       return merge(sort(left), sort(right));
   }

   protected int[] merge(int[] left, int[] right) {
       int[] result = new int[left.length + right.length];
       int i = 0;
       while (left.length > 0 && right.length > 0) {
           if (left[0] else {
               result[i++] = right[0];
               right = Arrays.copyOfRange(right, 1, right.length);
           }
       }

       while (left.length > 0) {
           result[i++] = left[0];
           left = Arrays.copyOfRange(left, 1, left.length);
       }

       while (right.length > 0) {
           result[i++] = right[0];
           right = Arrays.copyOfRange(right, 1, right.length);
       }

       return result;
   }

}

PHP

实例

function mergeSort($arr)
{
   $len = count($arr);
   if ($len return $arr;
   }
   $middle = floor($len / 2);
   $left = array_slice($arr, 0, $middle);
   $right = array_slice($arr, $middle);
   return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right)
{
   $result = [];

   while (count($left) > 0 && count($right) > 0) {
       if ($left[0] $right[0]) {
           $result[] = array_shift($left);
       } else {
           $result[] = array_shift($right);
       }
   }

   while (count($left))
       $result[] = array_shift($left);

   while (count($right))
       $result[] = array_shift($right);

   return $result;
}

C

实例

int min(int x, int y) {
   return x for (seg = 1; seg for (start = 0; start while (start1 while (start1 while (start2 if (a != arr) {
       int i;
       for (i = 0; i 

递归版:

实例

void merge_sort_recursive(int arr[], int reg[], int start, int end) {
   if (start >= end)
       return;
   int len = end - start, mid = (len >> 1) + start;
   int start1 = start, end1 = mid;
   int start2 = mid + 1, end2 = end;
   merge_sort_recursive(arr, reg, start1, end1);
   merge_sort_recursive(arr, reg, start2, end2);
   int k = start;
   while (start1 while (start1 while (start2 for (k = start; k 

C++

迭代版:

实例

template // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(for (int seg = 1; seg for (int start = 0; start while (start1 while (start1 while (start2 if (a != arr) {       for (int i = 0; i 

递归版:

实例

void Merge(vector &Array, int front, int mid, int end) {   // preconditions:   // Array[front...mid] is sorted   // Array[mid+1 ... end] is sorted   // Copy Array[front ... mid] to LeftSubArray   // Copy Array[mid+1 ... end] to RightSubArray   vector LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);   vector RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);   int idxLeft = 0, idxRight = 0;   LeftSubArray.insert(LeftSubArray.end(), numeric_limits::max());   RightSubArray.insert(RightSubArray.end(), numeric_limits::max());   // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]   for (int i = front; i if (LeftSubArray[idxLeft] else {           Array[i] = RightSubArray[idxRight];           idxRight++;       }   }}void MergeSort(vector &Array, int front, int end) {   if (front >= end)       return;   int mid = (front + end) / 2;   MergeSort(Array, front, mid);   MergeSort(Array, mid + 1, end);   Merge(Array, front, mid, end);}

C#

实例

public static List sort(List lst) {
   if (lst.Count return lst;
   int mid = lst.Count / 2;
   List left = new List();  // 定义左侧List
   List right = new List(); // 定义右侧List
   // 以下兩個循環把 lst 分為左右兩個 List
   for (int i = 0; i for (int j = mid; j return merge(left, right);
}
///
/// 合併兩個已經排好序的List
///
/// 左側List
/// 右側List
///
static List merge(List left, List right) {
   List temp = new List();
   while (left.Count > 0 && right.Count > 0) {
       if (left[0] else {
           temp.Add(right[0]);
           right.RemoveAt(0);
       }
   }
   if (left.Count > 0) {
       for (int i = 0; i if (right.Count > 0) {
       for (int i = 0; i return temp;
}

Ruby

实例

def merge list
 return list if list.size # Merge
 lambda { |left, right|
   final = []
   until left.empty? or right.empty?
     final if left.first else right.shift end
   end
   final + left + right
 }.call merge(list[0...pivot]), merge(list[pivot..-1])
end

本文题目:详解归并排序
网站路径:http://www.shufengxianlan.com/qtweb/news4/531804.html

网站建设、网络推广公司-创新互联,是专注品牌与效果的网站制作,网络营销seo公司;服务项目有等

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联