一奶赔、概述
????歸并排序是建立在歸并操作上的一種有效的排序算法惋嚎,該算法是采用分治法(Divide and Conquer)的一個(gè)典型應(yīng)用。
????將已有序的子序列合并纺阔,得到完全有序的序列瘸彤;即先使每個(gè)子序列有序,再使子序列段之間有序笛钝。將兩個(gè)有序表合并成一個(gè)有序表质况,稱為二路歸并愕宋。
二、歸并排序的基本思想
????將待排序序列R[0...n-1]看成是n個(gè)長度為1的有序序列结榄,將相鄰的有序表成對歸并中贝,得到n/2個(gè)長度為2的有序表;將這些有序序列再次歸并臼朗,得到n/4個(gè)長度為4的有序序列邻寿;如此反復(fù),最后得到一個(gè)長度為n的有序序列视哑。
歸并排序需要做兩件事:
1)分解:將序列每次折半劃分
2)合并:將劃分后的序列段兩兩合并后排序
如何合并绣否?
????在每次合并過程中,都是對兩個(gè)有序的序列段進(jìn)行合并挡毅,然后再排序蒜撮。這兩個(gè)有序的序列段分別為R[low, mid]和R[mid+1, high],先將它們合并到一個(gè)局部的暫存數(shù)組R2中跪呈,待合并完成后再將R2復(fù)制回R中段磨。
????每次從兩個(gè)段中取出一個(gè)記錄進(jìn)行關(guān)鍵字的比較,將較小者放入R2中耗绿,最后將各段中余下的部分直接復(fù)制到R2中苹支。經(jīng)過這樣的過程,R2已經(jīng)是一個(gè)有序的序列误阻,再將其復(fù)制回R中债蜜,一次合并排序就完成了。
在某趟歸并中究反,設(shè)各子表的長度為gap策幼,則歸并前R[0...n-1]中共有n/gap個(gè)有序的子表:R[0...gap-1], R[gap...2*gap-1], ... , R[(n/gap)*gap ... n-1]。
在將相鄰的子表歸并時(shí)奴紧,需要對表的特殊情況進(jìn)行處理:
1)若子表個(gè)數(shù)為奇數(shù),最后一個(gè)子表無須和其他子表歸并(即本趟處理輪空)晶丘;
2)若子表個(gè)數(shù)為偶數(shù)黍氮,到最后一對子表中后一個(gè)子表區(qū)間的上限為n-1;
三浅浮、排序性能
時(shí)間復(fù)雜度:歸并排序的形式就是一棵二叉樹沫浆,需要遍歷的次數(shù)就是二叉樹的深度,時(shí)間復(fù)雜度是O(nlogn)滚秩。
空間復(fù)雜度:算法處理過程中专执,需要一個(gè)大小為n的臨時(shí)存儲空間用來保存合并序列。
算法穩(wěn)定性:在歸并排序中郁油,相等元素的順序不會改變本股,所以它是穩(wěn)定的算法攀痊。
總結(jié):
1)時(shí)間復(fù)雜度:O(nlogn)
2)空間復(fù)雜度:O(n)
3)穩(wěn)定性:穩(wěn)定
4)復(fù)雜性:較復(fù)雜
四、選擇對比
1)空間復(fù)雜度考慮:選擇優(yōu)先級為[堆排序>快速排序>歸并排序]拄显。
2)穩(wěn)定性考慮:應(yīng)選歸并排序苟径,堆排序和快速排序都是不穩(wěn)定的。
3)平均排序速度考慮:應(yīng)選快速排序躬审。
五棘街、代碼實(shí)現(xiàn)
import java.util.Arrays;
/**
* 歸并排序
* 效率O(nlogn),歸并的最佳承边、平均和最糟用例效率之間沒有差異遭殉,適用于排序大列表,基于分治法博助。
*/
public class MergeSort {
????public static void main(String[] args) {
????????int[] array = {9, 1, 5, 3, 4, 2, 6, 8, 7};
????????MergeSort merge = new MergeSort();
????????System.out.println("排序前:"+Arrays.toString(array));
????????merge.sort(array);
????????System.out.println("排序后:"+Arrays.toString(array));
????}
????private static int[] sort(int[] list){
????????for(int gap = 1;gap <list.length; gap = 2*gap){
????????????MergePass(list,gap,list.length);
????????????System.out.println("gap="+gap+":"+Arrays.toString(list));
????????}
????????return list;
????}
????private static void MergePass(int[] arr,int gap,int length){
????????int i=0;
????????// 歸并gap長度的兩個(gè)相鄰子表
????????for(i=0;i+2*gap-1 < length;i = i+2*gap){
????????????Merge(arr, i, i + gap - 1, i + 2 * gap - 1);
????????}
????????// 余下兩個(gè)子表险污,后者長度小于gap
????????if (i + gap - 1 < length) {
????????????Merge(arr, i, i + gap - 1, length - 1);
????????}
????}
????private static void Merge(int[] arr,int low,int mid,int high){
????????int i=low;// i是第一段序列的下標(biāo)
????????int j = mid +1;// j是第二段序列的下標(biāo)
????????int k = 0;// k是臨時(shí)存放合并序列的下標(biāo)
????????int[] array2 = new int[high - low + 1]; // array2是臨時(shí)合并序列
????????// 掃描第一段和第二段序列,直到有一個(gè)掃描結(jié)束
????????while (i <= mid && j <= high) {
????????????// 判斷第一段和第二段取出的數(shù)哪個(gè)更小翔始,將其存入合并序列罗心,并繼續(xù)向下掃描
????????????if (arr[i] <= arr[j]) {
????????????????array2[k] = arr[i];
????????????????i++;
????????????????k++;
????????????} else {
????????????????array2[k] = arr[j];
????????????????j++;
????????????????k++;
????????????}
????????}
????????// 若第一段序列還沒掃描完,將其全部復(fù)制到合并序列
????????while(i <= mid){
????????????array2[k] = arr[i];
????????????i++;
????????????k++;
????????}
????????// 若第二段序列還沒掃描完城瞎,將其全部復(fù)制到合并序列
????????while(j <= high){
????????????array2[k] = arr[j];
????????????j++;
????????????k++;
????????}
????????// 將合并序列復(fù)制到原始序列中
????????for (k = 0, i = low; i <= high; i++, k++) {
????????????arr[i] = array2[k];
????????}
????}
}
運(yùn)行結(jié)果:
排序前: ? ? 9???1???5???3???4???2???6???8???7??
gap?=?1:???1???9???3???5???2???4???6???8???7??
gap?=?2:???1???3???5???9???2???4???6???8???7??
gap?=?4:???1???2???3???4???5???6???8???9???7??
gap?=?8:???1???2???3???4???5???6???7???8???9??
排序后: ? ? 1???2???3???4???5???6???7???8???9 ?