导读 | 归并排序(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) 的时间复杂度。代价是需要额外的内存空间。
算法步骤
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
- 重复步骤 3 直到某一指针达到序列尾;
- 将另一序列剩下的所有元素直接复制到合并序列尾。
动图演示
代码实现
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="">=>
Go
实例
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=""> &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 Listsort(List lst) { if (lst.Count <= 1)="" return="" lst;="" int="" mid="lst.Count" 2;="">=> 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])="">