共计 2935 个字符,预计需要花费 8 分钟才能阅读完成。
导读 | 归并排序(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
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]
Go
实例
func mergeSort(arr []int) []int {length := len(arr)
if length
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 0 && right.length > 0) {if (left[0] 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 0 && count($right) > 0) {if ($left[0]
C
实例
int min(int x, int y) {
return x
递归版:
实例
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
C++
迭代版:
实例
template // 整數或浮點數皆可使用, 若要使用物件 (class) 時必須設定 "小於"(
递归版:
实例
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 &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 left = new List (); // 定义左侧 List
List right = new List (); // 定义右侧 List
// 以下兩個循環把 lst 分為左右兩個 List
for (int i = 0; i
/// 合併兩個已經排好序的 List
///
/// 左側 List
/// 右側 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
Ruby
实例
def merge list
return list if list.size
正文完
星哥说事-微信公众号
![post-qrcode](https://www.xgss.net/wp-content/uploads/2023/07/二维码-微信公众号256x256.jpg)