建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
詳解歸并排序
歸并排序（MERGE-SORT）是利用歸并的思想實現(xiàn)的排序方法，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而**治(conquer)**的階段則將分的階段得到的各答案”修補”在一起，即分而治之)，下面為大家詳細(xì)講解一下歸并排序。
專注于為中小企業(yè)提供成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)清河免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了近千家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。
作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實現(xiàn)由兩種方法：
-
自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
-
自下而上的迭代；
在《數(shù)據(jù)結(jié)構(gòu)與算法 JavaScript 描述》中，作者給出了自下而上的迭代方法。但是對于遞歸法，作者卻認(rèn)為：
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而，在 JavaScript 中這種方式不太可行，因為這個算法的遞歸深度對它來講太深了。
說實話，我不太理解這句話。意思是 JavaScript 編譯器內(nèi)存太小，遞歸太深容易造成內(nèi)存溢出嗎？還望有大神能夠指教。
和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因為始終都是 O(nlogn) 的時間復(fù)雜度。代價是需要額外的內(nèi)存空間。
算法步驟
-
申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列；
-
設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置；
-
比較兩個指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動指針到下一位置；
-
重復(fù)步驟 3 直到某一指針達(dá)到序列尾；
-
將另一序列剩下的所有元素直接復(fù)制到合并序列尾。
動圖演示
代碼實現(xiàn)
JavaScript
實例
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;
}
Python
實例
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
Go
實例
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
}
Java
實例
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進(jìn)行拷貝，不改變參數(shù)內(nèi)容
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;
}
}
PHP
實例
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 C++
迭代版：
實例
template // 整數(shù)或浮點數(shù)皆可使用,若要使用物件(class)時必須設(shè)定"小於"(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);}
C#
實例
public static List sort(List lst) {
if (lst.Count return lst;
int mid = lst.Count / 2;
List left = new List(); // 定義左側(cè)List
List right = new List(); // 定義右側(cè)List
// 以下兩個循環(huán)把 lst 分為左右兩個 List
for (int i = 0; i for (int j = mid; j return merge(left, right);
}
///
/// 合併兩個已經(jīng)排好序的List
///
/// 左側(cè)List
/// 右側(cè)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;
}
Ruby
實例
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
文章標(biāo)題：詳解歸并排序
分享路徑：http://www.dlmjj.cn/article/cdgcpph.html
