資訊專欄INFORMATION COLUMN
摘要：排序之歸并排序簡介歸并排序的算法是將多個有序數據表合并成一個有序數據表。如果參與合并的只有兩個有序表，則成為二路合并。對于一個原始的待排序數列，往往可以通過分割的方法來歸結為多路合并排序。
Java排序之歸并排序 1. 簡介
歸并排序的算法是將多個有序數據表合并成一個有序數據表。如果參與合并的只有兩個有序表，則成為二路合并。對于一個原始的待排序數列，往往可以通過分割的方法來歸結為多路合并排序。
2. 歸并排序思路將長度為n的待排序數組看做是由n個有序長度為1的數組組成
將其兩兩合并，得到長度為2的有序數組
然后再對這些子表進行合并，得到長度為4的有序數組
重復上述過程，一直到最后的子表長度為n也就完成了排序
3. 代碼實例歸并排序有兩種實現方式：遞歸和非遞歸。在看歸并排序的代碼之前先來看一下怎么和合并兩個有序數組：
// 基礎，合并兩個有序數組
public static int[] merge2Arr(int[] arr1, int[] arr2) {
int len1 = arr1.length;
int len2 = arr2.length;
int[] res = new int[len1 + len2]; // 使用一個數組用來存儲排好序的數組
int i = 0, j = 0, k = 0;
while(i < len1 && j < len2) {
res[k++] = arr1[i] < arr2[j]? arr1[i++] : arr2[j++];
}
while(i < len1) {
res[k++] = arr1[i++];
}
while(j < len2) {
res[k++] = arr2[j++];
}
return res;
}
歸并排序的遞歸實現：
// 歸并排序，遞歸實現
public void sortMergeRecursion(int[] nums) {
sortMergeRecursionHelper(nums, 0, nums.length - 1);
}
public void sortMergeRecursionHelper(int[] nums,int left, int right) {
if(left == right) return; // 當待排序的序列長度為1時，遞歸開始回溯，進行merge
int middle = left + (right - left) / 2;
sortMergeRecursionHelper(nums, left, middle);
sortMergeRecursionHelper(nums, middle + 1, right);
mergeArr(nums, left, middle, right);
}
public void mergeArr(int[] nums, int left, int middle, int right) {
int[] tem = new int[right - left + 1];
int i = left, j = middle + 1, k = 0;
while(i <= middle && j <= right) {
tem[k++] = nums[i] < nums[j]? nums[i++] : nums[j++];
}
while(i <= middle) {
tem[k++] = nums[i++];
}
while(j <= right) {
tem[k++] = nums[j++];
}
// 將輔助數組數據寫入原數組
int index = 0;
while(left <= right) {
nums[left++] = tem[index++];
}
}
歸并排序的非遞歸實現（迭代）：
// 歸并排序，非遞歸實現(迭代)
public void sortMergeIteration(int[] nums) {
int len = 1; // 初始排序數組的長度
while(len < nums.length) {
for(int i = 0; i < nums.length; i += len * 2) {
sortMergeIterationHelper(nums, i, len);
}
len *= 2; // 每次將排序數組的長度*2
}
}
/**
* 輔助函數
* @param nums 原數組
* @param start 從start位置開始
* @param len 本次合并的數組長度
*/
public void sortMergeIterationHelper(int[] nums, int start, int len) {
int[] tem = new int[len * 2];
int i = start;
int j = start + len;
int k = 0;
while(i < start + len && (j < start + len + len && j < nums.length)) {
tem[k++] = nums[i] < nums[j]? nums[i++] : nums[j++];
}
while(i < start + len && i < nums.length) { // 注意：這里i也可能超出長度
tem[k++] = nums[i++];
}
while(j < start + len + len && j < nums.length) {
tem[k++] = nums[j++];
}
int right = start + len + len;
int index = 0;
while(start < nums.length && start < right) {
nums[start++] = tem[index++];
}
}
歸并排序的時間復雜度為O(n*log2n),空間復雜度為O(n)
歸并排序是一種穩定的排序方法。
參考：https://blog.csdn.net/y999666...
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/69663.html
摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。 常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...
摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。 常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...
摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。 常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...
摘要：兩個單元素數組的合并實際就是對這兩個數進行了排序，即變為，同樣再對后一組的兩個數歸并排序，即變為，再將兩單元數組歸并成四單元數組即和歸并為。 前言 本周講解兩個50多年前發明，但今天仍然很重要的經典算法 (歸并排序和快速排序) 之一 -- 歸并排序，幾乎每個軟件系統中都可以找到其中一個或兩個的實現，并研究這些經典方法的新變革。我們的涉及范圍從數學模型中解釋為什么這些方法有效到使這些算法...
摘要：歸并排序是一種十分優秀的排序方法，在一開始學習的時候可能會對它的實現思路有點難以理解，不過當你想通了之后就會發現這種方法的絕妙之處。 歸并排序是一種十分優秀的排序方法，在一開始學習的時候可能會對它的實現思路有點難以理解，不過當你想通了之后就會發現這種方法的絕妙之處。 showImg(https://segmentfault.com/img/bVbctoS?w=941&h=560);sh...
閱讀 3467·2023-04-25 23:25
閱讀 2111·2021-11-12 10:36
閱讀 2826·2019-08-30 12:47
閱讀 2049·2019-08-29 18:45
閱讀 447·2019-08-29 17:28
閱讀 1793·2019-08-29 17:15
閱讀 1718·2019-08-29 16:05
閱讀 1421·2019-08-29 14:17
