归并排序 归并排序（，或-- ），是建立在归并操作上的一种有效的排序算法，效率为formula_1（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。 概述. 采用分治法: 归并操作. 归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。 迭代法（Bottom-up）. 原理如下（假设序列共有formula_2个元素）： 实作范例. C语言. 迭代版： int min(int x, int y) { return x // 整数或浮点数皆可使用,若要使用物件(class)时必须设定"小于"( &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 &Array, int front, int end) { if (front >= end) return; int mid = front + (end - front) / 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 left = new List(); // 定义左侧List List right = new List(); // 定义右侧List // 以下两个循环把 lst 分为左右两个 List for (int i = 0; i /// 合并两个已经排好序的List /// /// /// /// static List merge(List left, List right) { List temp = new List(); while (left.Count > 0 && right.Count > 0) { if (left[0] 0) { for (int i = 0; i 0) { for (int i = 0; i = 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, result, start1, end1); merge_sort_recursive(arr, result, start2, end2); int k = start; while (start1 = arr.length ? (arr.length - 1) : (left + i / 2); int right = i * (j + 1) - 1 >= arr.length ? (arr.length - 1) : (i * (j + 1) - 1); int start = left, l = left, m = mid; while (l g_sort([T]) -> [T]; g_sort(L) -> g_sort(L, length(L)). g_sort([_, _ | _] = L, Length) -> SplitNum = trunc(Length / 2), {L1, L2} = lists:split(SplitNum, L), g_merge(g_sort(L1, SplitNum), g_sort(L2, Length - SplitNum)); g_sort(L, _Length) -> L. %% 已经排好序的两个list合并 g_merge([], L2) -> L2; g_merge(L1, []) -> L1; g_merge([T1 | Rest1] = L1, [T2 | Rest2] = L2) -> if T1 = [T1 | g_merge(Rest1, L2)]; true -> [T2 | g_merge(L1, Rest2)] end. Javascript. 递归法 function merge(left, right){ var result = []; while(left.length > 0 && right.length > 0){ if(left[0] = 2 { left = merge(left) right := data[sum/2:] rSize := len(right) if rSize >= 2 { right = merge(right) j := 0 t := 0 arr := make([]int, sum) fmt.Println(left, right, data) for i := 0; i = lSize{ arr[i] = right[t] t++ } else if t >= rSize{ arr[i] = left[j] j++ return arr func main() { var bb = merge(aa) fmt.Println(bb) 算法复杂度. 比较操作的次数介于formula_5和formula_6。 赋值操作的次数是formula_7。归并算法的空间复杂度为：formula_8