良许Linux教程网 干货合集 详解归并排序

详解归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and 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

以上就是良许教程网为各位朋友分享的Linu系统相关内容。想要了解更多Linux相关知识记得关注公众号“良许Linux”,或扫描下方二维码进行关注,更多干货等着你 !

1ad5ad6eddc451da964a8888a6fd5266d0163210
本文由 良许Linux教程网 发布,可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。
良许

作者: 良许

良许,世界500强企业Linux开发工程师,公众号【良许Linux】的作者,全网拥有超30W粉丝。个人标签:创业者,CSDN学院讲师,副业达人,流量玩家,摄影爱好者。
上一篇
下一篇

发表评论

邮箱地址不会被公开。 必填项已用*标注

联系我们

联系我们

公众号:良许Linux

在线咨询: QQ交谈

邮箱: yychuyu@163.com

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部