.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}
排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是归并排序算法:
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 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) 的时间复杂度。代价是需要额外的内存空间。
2. 算法步骤
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
设定两个指针,最初位置分别为两个已经排序序列的起始位置;
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
重复步骤 3 直到某一指针达到序列尾;
将另一序列剩下的所有元素直接复制到合并序列尾。
3. 动图演示
![](https://www.runoob.com/wp-content/uploads/2019/03/mergeSort.gif)
代码实现JavaScript实例 function mergeSort(arr) { // 采用自上而下的递归方法 var len = arr.length; if(len < 2) { 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] <= right[0]) { result.push(left.shift()); } 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)<2): 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] <= right[0]: result.append(left.pop(0)) else: result.append(right.pop(0)); while left: result.append(left.pop(0)) while right: result.append(right.pop(0)); return resultGo 实例 func mergeSort(arr []int) []int { length := len(arr) if length < 2 { 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] <= right[0] { result = append(result, left[0]) left = left[1:] } 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 < 2) { 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] <= right[0]) { result[i++] = left[0]; left = Arrays.copyOfRange(left, 1, left.length); } 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 < 2) { 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 < y ? x : y;}void merge_sort(int arr[], int len) { int *a = arr; int *b = (int *) malloc(len * sizeof(int)); int seg, start; for (seg = 1; seg < len; seg += seg) { for (start = 0; start < len; start += seg * 2) { int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len); int k = low; int start1 = low, end1 = mid; int start2 = mid, end2 = high; while (start1 < end1 && start2 < end2) b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++]; while (start1 < end1) b[k++] = a[start1++]; while (start2 < end2) b[k++] = a[start2++]; } int *temp = a; a = b; b = temp; } if (a != arr) { int i; for (i = 0; i < len; i++) b[i] = a[i]; b = a; } free(b);}
递归版:
实例 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 <= end1 && start2 <= end2) reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; while (start1 <= end1) reg[k++] = arr[start1++]; while (start2 <= end2) reg[k++] = arr[start2++]; for (k = start; k <= end; k++) arr[k] = reg[k];}void merge_sort(int arr[], const int len) { int reg[len]; merge_sort_recursive(arr, reg, 0, len - 1);}C++
迭代版:
实例 template
// 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能void merge_sort(T arr[], int len) { T *a = arr; T *b = new T[len]; for (int seg = 1; seg < len; seg += seg) { for (int start = 0; start < len; start += seg + seg) { int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len); int k = low; int start1 = low, end1 = mid; int start2 = mid, end2 = high; while (start1 < end1 && start2 < end2) b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++]; while (start1 < end1) b[k++] = a[start1++]; while (start2 < end2) b[k++] = a[start2++]; } T *temp = a; a = b; b = temp; } if (a != arr) { for (int i = 0; i < len; i++) b[i] = a[i]; b = a; } delete[] b;}递归版:
实例 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 <= end; i++) { if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) { Array[i] = LeftSubArray[idxLeft]; 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 <= 1) return lst; int mid = lst.Count / 2; List left = new List(); // 定义左侧List List right = new List(); // 定义右侧List // 以下兩個循環把 lst 分為左右兩個 List for (int i = 0; i < mid; i++) left.Add(lst[i]); for (int j = mid; j < lst.Count; j++) right.Add(lst[j]); left = sort(left); right = sort(right); 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] <= right[0]) { temp.Add(left[0]); left.RemoveAt(0); } else { temp.Add(right[0]); right.RemoveAt(0); } } if (left.Count > 0) { for (int i = 0; i < left.Count; i++) temp.Add(left[i]); } if (right.Count > 0) { for (int i = 0; i < right.Count; i++) temp.Add(right[i]); } return temp;}Ruby实例 def merge list return list if list.size < 2 pivot = list.size / 2 # Merge lambda { |left, right| final = [] until left.empty? or right.empty? final << if left.first < right.first; left.shift else right.shift end end final + left + right }.call merge(list[0...pivot]), merge(list[pivot..-1])end参考地址:
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/5.mergeSort.md
https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
以下是热心网友对归并排序算法的补充,仅供参考:
热心网友提供的补充1:
分而治之
![](https://www.runoob.com/wp-content/uploads/2019/05/1557906108-5066-20161218163120151-452283750.png)
可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。
合并相邻有序子序列
再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。
![](https://www.runoob.com/wp-content/uploads/2019/05/1557906108-2034-20161218194508761-468169540.png)
![](https://www.runoob.com/wp-content/uploads/2019/05/1557906108-7614-20161218194621308-588010220.png)
import java.util.Arrays;
/**
* Created by chengxiao on 2016/12/8.
*/
public class MergeSort {
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left以上为归并排序算法详细介绍,插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点,用一张图概括: ![](https://img.how234.com/itpx/sort.png)
![](https://img.how234.com/itpx/sort2.png)
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;
O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。
关于稳定性
稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。
名词解释:
n:数据规模
k:"桶"的个数
In-place:占用常数内存,不占用额外内存
Out-place:占用额外内存
稳定性:排序后 2 个相等键值的顺序和排序之前它们的顺序相同