什么是歸并排序

一、歸并排序的定義

上篇文章帶大家了解了,這篇文章帶大家了解下歸并排序,歸并排序有兩個過程:第一個過程是分組,分組是將數據進行逐層對半分組,第一次分成兩個大組,每組n/2個元素,第二次分成四個大組,每組n/4個元素,以此操作直到最后每組元素只有一個元素;第二個過程是合并,合并需要比較元素的大小進行排序,第一次有n/2個操作元素同時進行,第二次有n/4操作元素同時進行操作,以此類推,最后進行兩個大數組的比較排序就可得到結果。歸并這種思想有點像分布式這種思維,將雞蛋放在很多籃子里,讓很多人同時操作,選出更大的雞蛋,大大提升了效率。

圖像演示:

在這里插入圖片描述

二、代碼實現

 1static public void mergeSort(int[] array, int start, int end){ 2 3    if(start < end){ 4 5        //折半成兩個小集合,分別進行遞歸 6 7        int mid=start+(end-start)/2; 8 9        mergeSort(array, start, mid);1011        mergeSort(array, mid+1, end);1213        //把兩個有序小集合,歸并成一個大集合1415        merge(array, start, mid, end);1617        }1819}20212223static private void merge(int[] array, int start, int mid, int end){2425    //開辟額外大集合,設置指針2627    int[] tempArray = new int[end-start+1];2829    int p1=start, p2=mid+1, p=0;3031    //比較兩個小集合的元素,依次放入大集合3233    while(p1<=mid && p2<=end){3435        if(array[p1]<=array[p2])3637            tempArray[p++]=array[p1++];3839        else4041            tempArray[p++]=array[p2++];4243    }4445//左側小集合還有剩余,依次放入大集合尾部4647    while(p1<=mid)4849        tempArray[p++]=array[p1++];5051    //右側小集合還有剩余,依次放入大集合尾部5253    while(p2<=end)5455        tempArray[p++]=array[p2++];5657    //把大集合的元素復制回原數組5859    for (int i=0; i<tempArray.length; i++)6061        array[i+start]=tempArray[i];6263}

三、時間復雜度分析

歸并排序的時間復雜度為O(NlogN),主要花費時間在合并的操作中,合并又可以細分為3個步驟,第一步是聲明一個大數組用來存儲兩個小數組元素,第二步將兩個小數組的元素按順序比較,選取較大的元素放入大數組中,第三步是將剩余的元素放入大數組中,整個過程和鏈表的合并操作非常類似。

四、實際應用

合并排序的特點是穩定的,其他兩種快速排序和堆排序就不穩定,所以當需要對很大的數據量進行排序而且要求最后不能改變元素的相對位置,合并排序是首選的。下篇文章將講解另一個穩定的排序算法:基數排序。

五、表格總結

排序類型時間復雜度空間復雜度穩定性
歸并排序O(NlogN)O(NlogN)穩定

掃一掃,關注一波

免責聲明:本文僅代表文章作者的個人觀點,與本站無關。其原創性、真實性以及文中陳述文字和內容未經本站證實,對本文以及其中全部或者部分內容文字的真實性、完整性和原創性本站不作任何保證或承諾,請讀者僅作參考,并自行核實相關內容。

http://image99.pinlue.com/thumb/img_jpg/ickRudqAM3jk5k11n0E9dzDfACA38KbJLxqxiaPxuejtAA1084nsLGbGEibABgib4LZ3ZzuyiaQiccXFFicg3jibEVLxyA/0.jpeg
我要收藏
贊一個
踩一下
分享到
相關推薦
精選文章
?
分享
評論
首頁
河北十一选五有直播吗