歸併排序演算法過程圖解
- IT科技
- 關注:1.21W次
排序演算法是《資料結構與演算法》中最基本的演算法之一。排序演算法可以分為內部排序和外部排序,內部排序是資料記錄在記憶體中進行排序,而外部排序是因排序的資料很大,一次不能容納全部的排序記錄,在排序過程中需要訪問外存。常見的內部排序演算法有:插入排序、希爾排序、選擇排序、氣泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是歸併排序演算法:
歸併排序(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) 的時間複雜度。代價是需要額外的記憶體空間。
2. 演算法步驟
申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合併後的序列;
設定兩個指標,最初位置分別為兩個已經排序序列的起始位置;
比較兩個指標所指向的元素,選擇相對小的元素放入到合併空間,並移動指標到下一位置;
重複步驟 3 直到某一指標達到序列尾;
將另一序列剩下的所有元素直接複製到合併序列尾。
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 result
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<typename T> // 整數或浮點數皆可使用,若要使用物件(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<int> &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<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
int idxLeft = 0, idxRight = 0;
LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::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 MergeSort(vector<int> &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<int> sort(List<int> lst) {if (lst.Count <= 1)
return lst;
int mid = lst.Count / 2;
List<int> left = new List<int>(); // 定義左側List
List<int> right = new List<int>(); // 定義右側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);
}
/// <summary>
/// 合併兩個已經排好序的List
/// </summary>
/// <param name="left">左側List</param>
/// <param name="right">右側List</param>
/// <returns></returns>
static List<int> merge(List<int> left, List<int> right) {
List<int> temp = new List<int>();
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 listreturn 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])
end
參考地址:
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/5.mergeSort.md
https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
以下是熱心網友對歸併排序演算法的補充,僅供參考:
熱心網友提供的補充1:
分而治之
可以看到這種結構很像一棵完全二元樹,本文的歸併排序我們採用遞迴去實現(也可採用迭代的方式去實現)。分階段可以理解為就是遞迴拆分子序列的過程,遞迴深度為log2n。
合併相鄰有序子序列
再來看看治階段,我們需要將兩個已經有序的子序列合併成一個有序序列,比如上圖中的最後一次合併,要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列,合併為最終序列[1,2,3,4,5,6,7,8],來看下實現步驟。
import java.util.Arrays;/** * Created by chengxiao on 2016/12/8. */public class MergeSort { public static void main(String []args){ int []arr = {9,8,7,6,5,4,3,2,1}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int []arr){ int []temp = new int[arr.length];//在排序前,先建好一個長度等於原陣列長度的臨時陣列,避免遞迴中頻繁開闢空間 sort(arr,0,arr.length-1,temp); } private static void sort(int[] arr,int left,int right,int []temp){ if(left<right){ int mid = (left+right)/2; sort(arr,left,mid,temp);//左邊歸併排序,使得左子序列有序 sort(arr,mid+1,right,temp);//右邊歸併排序,使得右子序列有序 merge(arr,left,mid,right,temp);//將兩個有序子數組合並操作 } } private static void merge(int[] arr,int left,int mid,int right,int[] temp){ int i = left;//左序列指標 int j = mid+1;//右序列指標 int t = 0;//臨時陣列指標 while (i<=mid && j<=right){ if(arr[i]<=arr[j]){ temp[t++] = arr[i++]; }else { temp[t++] = arr[j++]; } } while(i<=mid){//將左邊剩餘元素填充進temp中 temp[t++] = arr[i++]; } while(j<=right){//將右序列剩餘元素填充進temp中 temp[t++] = arr[j++]; } t = 0; //將temp中的元素全部拷貝到原陣列中 while(left <= right){ arr[left++] = temp[t++]; } }}以上為歸併排序演算法詳細介紹,插入排序、希爾排序、選擇排序、氣泡排序、歸併排序、快速排序、堆排序、基數排序等排序演算法各有優缺點,用一張圖概括:
關於時間複雜度
平方階 (O(n2)) 排序 各類簡單排序:直接插入、直接選擇和氣泡排序。
線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸併排序;
O(n1+§)) 排序,§ 是介於 0 和 1 之間的常數。 希爾排序
線性階 (O(n)) 排序 基數排序,此外還有桶、箱排序。
關於穩定性
穩定的排序演算法:氣泡排序、插入排序、歸併排序和基數排序。
不是穩定的排序演算法:選擇排序、快速排序、希爾排序、堆排序。
名詞解釋:
n:資料規模
k:"桶"的個數
In-place:佔用常數記憶體,不佔用額外記憶體
Out-place:佔用額外記憶體
穩定性:排序後 2 個相等鍵值的順序和排序之前它們的順序相同
- 文章版權屬於文章作者所有,轉載請註明 https://shqsg.com/dianzi/8yyyl6.html