溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
