这篇文章主要介绍了web如何实现归并排序，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而**治(conquer)**的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
在《数据结构与算法 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) 的时间复杂度。代价是需要额外的内存空间。
代码实现
实例
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;
}实例
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
实例
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
}实例
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;
}
}实例
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迭代版：
实例
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);}实例
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;
}实例
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感谢你能够认真阅读完这篇文章，希望小编分享的“web如何实现归并排序”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
