十大經(jīng)典排序算法詳解之二希爾排序,歸并排序,快速排序
十大經(jīng)典排序算法-希爾排序,歸并排序,快速排序前言這是十大經(jīng)典排序算法詳解的第二篇,這是之前第一篇文章的鏈接:十大經(jīng)典排序算法詳解(一)冒泡排序,選擇排序,插入排序,沒(méi)有看過(guò)的小伙伴可以看一下.
每次講解都是「先采用文字」的方式幫助大家先熟悉一下算法的基本思想,之后我會(huì)在通過(guò)「圖片的方式」來(lái)幫助大家分析排序算法的動(dòng)態(tài)執(zhí)行過(guò)程,這樣就能夠幫助大家更好的理解算法.
每次的圖畫起來(lái)都比較的繁瑣,真的很耗費(fèi)時(shí)間.所以如果你覺(jué)得文章寫得還可以或者說(shuō)對(duì)你有幫助的話,你可以選擇一鍵三連,或者選擇關(guān)注我的公眾號(hào):「萌萌噠的瓤瓤」 ,這對(duì)我真的很重要.UP在此謝謝各位了.
廢話不多說(shuō)了,下面開(kāi)始我們的正文部分吧!!!
1-希爾排序
算法思想:
其實(shí)希爾排序的思想很簡(jiǎn)單,因?yàn)橄柵判虻幕舅枷刖褪堑谝黄虚g講解的關(guān)于插入排序的基本思想,「只是希爾排序相比較與插入排序多加了一步就是確定步長(zhǎng)」.之前在插入排序的過(guò)程中,我們的步長(zhǎng)是固定的即為1,在希爾排序中我們的步長(zhǎng)是不固定的,「一開(kāi)始數(shù)組長(zhǎng)度的一半,之后每次分組排序之后步長(zhǎng)就再減半,直到步長(zhǎng)到1為止」.這時(shí)候我們的排序就已經(jīng)完成了.
說(shuō)完了,那我們接下來(lái)還是通過(guò)圖解的方式來(lái)幫助大家更好的理解希爾排序吧:
看完上面的圖之后相信大家就基本了解希爾排序算法的思想了,那么接下來(lái)我們還是來(lái)分析一下希爾排序算法的特點(diǎn)吧:
- 希爾排序算法是不穩(wěn)定的,這里大家可能會(huì)產(chǎn)生這樣的疑問(wèn),本身希爾排序算法的本質(zhì)就是插入排序,只不過(guò)是多了一步確定步長(zhǎng)的過(guò)程,為什么插入排序就是穩(wěn)定的,但是希爾排序缺失不穩(wěn)定的呢?其實(shí)重點(diǎn)就是在分組之后,大家都知道在一個(gè)分組里面進(jìn)行一次插入排序肯定是穩(wěn)定的,關(guān)鍵就在于希爾排序的過(guò)程中會(huì)出現(xiàn)多次分組,那么就會(huì)出現(xiàn)在之前的分組里面是穩(wěn)定的,但是到下一次分組的時(shí)候就會(huì)出現(xiàn)不穩(wěn)定的情況.
說(shuō)這么多還不如直接來(lái)個(gè)例子給大家看一下,大家就知道了:
- 希爾排序是 「第一個(gè)」 在時(shí)間復(fù)雜度上突破O(N*N)的算法,這一點(diǎn)是非常有意義的.時(shí)間復(fù)雜度僅為O(N*log N)
算法圖解:
在這里插入圖片描述
示例代碼:
「按照算法思想不改動(dòng)的版本」:
- public static void main(String[] args) {
- int []num ={7,4,9,3,2,1,8,6,5,10};
- long startTime=System.currentTimeMillis();
- //規(guī)定步長(zhǎng)
- for(int step=num.length/2;step>0;step/=2) {
- System.out.println("步長(zhǎng)為"+step+"的分組排序:");
- //步長(zhǎng)確定之后就需要分批次的對(duì)分組進(jìn)行插入排序
- for(int l=0;l<step;l++) {
- //插入排序的代碼
- for(int i=l+step;i<num.length;i+=step) {
- int temp=num[i];
- int j=i;
- while(j>0&&temp<num[j-step]) {
- num[j]=num[j-step];
- j-=step;
- //這里需要注意一點(diǎn)就是j-step可能會(huì)越界,所以我們需要繼續(xù)進(jìn)行判斷
- //之前在插入排序中,步長(zhǎng)始終是1,所以在while循環(huán)那里就會(huì)阻斷,但是現(xiàn)在步長(zhǎng)會(huì)發(fā)生變化
- //所以我們需要在這里提前進(jìn)行判斷,否則金輝發(fā)生數(shù)組越界的情況
- if(j-step<0)
- break;
- }
- if(j!=i) {
- num[j]=temp;
- }
- }
- System.out.println(" "+l+"號(hào)分組排序:");
- for(int k=0;k<num.length;k++)
- System.out.print(num[k]+" ");
- System.out.println();
- }
- System.out.println();
- }
- long endTime=System.currentTimeMillis();
- System.out.println("程序運(yùn)行時(shí)間： "+(endTime-startTime)+"ms");
- }
但是大家會(huì)發(fā)現(xiàn)如果真的按照希爾排序的思想這樣做得的話,我們會(huì)發(fā)現(xiàn)用了三層for循環(huán),那么很顯然時(shí)間復(fù)雜度就會(huì)達(dá)到我們目前遇到的最壞的情況即O(N*N*N),所以我們需要進(jìn)行改進(jìn),主要就是改進(jìn)分組排序的過(guò)程,之前我們是確定完步長(zhǎng)之后,就通過(guò)for循環(huán)進(jìn)行循環(huán)分組的排序,這里我們修改成直接和下一個(gè)for循環(huán)一起,直接進(jìn)行循環(huán)分組
「改進(jìn)后的代碼」:
- public static void main(String[] args) {
- int []num ={7,4,9,3,2,1,8,6,5,10};
- long startTime=System.currentTimeMillis();
- for(int step=num.length/2;step>0;step/=2) {
- System.out.println("步長(zhǎng)為"+step+"的分組排序:");
- System.out.println("循環(huán)分組排序:");
- for(int j=step;j<num.length;j++) {
- int temp=num[j];
- int k=j;
- while(k-step>=0&&temp<num[k-step]) {
- num[k]=num[k-step];
- k-=step;
- }
- num[k]=temp;
- for(int l=0;l<num.length;l++)
- System.out.print(num[l]+" ");
- System.out.println();
- }
- }
- long endTime=System.currentTimeMillis();
- System.out.println("程序運(yùn)行時(shí)間： "+(endTime-startTime)+"ms");
- }
改進(jìn)之后的算法之使用了兩層for循環(huán),真的讓時(shí)間復(fù)雜度達(dá)到了O(N*log N)
復(fù)雜度分析: 理解完希爾排序的基本思想之后,我們就需要來(lái)分析一下他的時(shí)間復(fù)雜度,空間復(fù)雜度.
- 時(shí)間復(fù)雜度
希爾排序的時(shí)間復(fù)雜度在各情況下,主要就取決于元素的個(gè)數(shù)以及分組的次數(shù),我們分析得到分組的次數(shù)剛好就是log N,所以我們可以得到希爾排序的時(shí)間復(fù)雜度僅為O(N*log N)
- 空間復(fù)雜度
這個(gè)我們可以看到我們整個(gè)排序的過(guò)程中只增加一個(gè)存儲(chǔ)Key的位置,所以希爾排序的空間復(fù)雜是常量級(jí)別的僅為O(1).
2-歸并排序
算法思想: 歸并排序的思想本質(zhì)就是進(jìn)行分冶.把 「整個(gè)序列拆分成多個(gè)序列」,先將每個(gè)序列排好序,這個(gè)就是「分冶思想中分」,同樣也是「歸并排序中歸」 的思想.
之后再將各個(gè)序列整合到一起這就是「分冶中的冶同樣也是歸并排序的并」.思想說(shuō)完了,但是呢說(shuō)不能解決問(wèn)題,我們還是通過(guò)下面的圖來(lái)幫助大家理解:
看到圖之后,我們就會(huì)發(fā)現(xiàn)上面分和合并的過(guò)程都特別像遞歸對(duì)不對(duì),都是按照一定的終止條件一直執(zhí)行下去.所以呢這就暗示了我們的歸并排序是可以通過(guò)「遞歸」的思想來(lái)編寫的.
現(xiàn)在我們基本上已經(jīng)基本了解歸并排序的基本思想了,現(xiàn)在我們?cè)賮?lái)看看歸并排序由那些特點(diǎn)吧
歸并排序是穩(wěn)定的,這個(gè)大家看過(guò)我上面的演示過(guò)程就能看出來(lái)了.
歸并排序需要消耗大量的內(nèi)存空間.這個(gè)內(nèi)存空間是對(duì)比冒泡排序之類的排序算法而言的,因?yàn)樗麄兊膬?nèi)存空間都是只存在于常量級(jí)別的,但是歸并排序卻是需要消耗線性級(jí)別的內(nèi)存空間,所以才會(huì)使用大量這個(gè)形容詞.消耗的內(nèi)存空間就是等同于待排序序列的長(zhǎng)度.即O(n)的復(fù)雜度.
算法圖解:
在這里插入圖片描述
示例代碼:
重要代碼我已經(jīng)添加了注釋能夠更加方便讀者們理解.
- public static int[] sort(int []num) {
- //分裂之后的數(shù)組如果只有1個(gè)元素的話,
- //那么就說(shuō)明可以開(kāi)始合并的過(guò)程了,所以直接返回.
- if(num.length<2)
- return num;
- int middle=num.length/2;
- //截取左右兩個(gè)序列
- int []left=Arrays.copyOfRange(num, 0, middle);
- int []right=Arrays.copyOfRange(num, middle, num.length);
- return merge(sort(left), sort(right));
- }
- public static int[] merge(int []left,int []right) {
- int []num=new int [left.length+right.length];
- int i=0,j=0,k=0;
- //注意終止條件是&&,只要有一個(gè)不滿足,循環(huán)就結(jié)束
- while(i<left.length&&j<right.length) {
- if(left[i]<right[j])
- num[k++]=left[i++];
- else
- num[k++]=right[j++];
- }
- //上面的循環(huán)跳出之后,就說(shuō)明有且僅會(huì)有一個(gè)序列還有值了
- //所以需要再次檢查各個(gè)序列,并且下面的兩個(gè)循環(huán)是互斥的,只會(huì)執(zhí)行其中的一個(gè)
- //或者都不執(zhí)行
- while(i<left.length) {
- num[k++]=left[i++];
- }
- while(j<right.length) {
- num[k++]=right[j++];
- }
- for(int l=0;l<num.length;l++)
- System.out.print(num[l]+" ");
- System.out.println();
- return num;
- }
- public static void main(String[] args) {
- int []num ={7,4,9,3,2,1,8,6,5,10};
- long startTime=System.currentTimeMillis();
- num=sort(num);
- // for(int i=0;i<num.length;i++) {
- // System.out.print(num[i]+" ");
- // }
- // System.out.println();
- long endTime=System.currentTimeMillis();
- System.out.println("程序運(yùn)行時(shí)間： "+(endTime-startTime)+"ms");
- }
這里呢就不演示全部的元素了,這里就簡(jiǎn)單和大家演示一下左半邊區(qū)間元素排序的過(guò)程,右半邊大家可以自行腦補(bǔ),這個(gè)應(yīng)該不難.
這樣大家應(yīng)該就能理解了,主要就是如果「序列長(zhǎng)度不是2的次方」的話,后續(xù)劃分序列的時(shí)候就會(huì)出現(xiàn)上述與我們類似的情況.畢竟我們劃分區(qū)間的 整個(gè)過(guò)程就類似于「將區(qū)間中心劃分成一個(gè)二叉樹(shù)」.
復(fù)雜度分析:
理解完歸并排序的基本思想之后,我們就需要來(lái)分析一下他的時(shí)間復(fù)雜度,空間復(fù)雜度.
- 時(shí)間復(fù)雜度
其實(shí)我們從上面的算法中能明顯看出來(lái)我們沒(méi)有使用for循環(huán),而是通過(guò)遞歸的方式來(lái)解決我們的循環(huán)問(wèn)題的.所以更加的高效. 就像我們上面的演示過(guò)程里面寫的一樣,這個(gè)執(zhí)行的層數(shù)為2 * log N,并且每層操作的元素是N個(gè),所以我們的時(shí)間復(fù)雜度即為2 * N * log N,但是常數(shù)可以忽略不計(jì),所以我們的時(shí)間復(fù)雜度就控制在了O(N*log N),對(duì)比我們之前算法的時(shí)間復(fù)雜度O(N*N),可以看到「時(shí)間復(fù)雜度明顯降低很多」,并且這個(gè)時(shí)間復(fù)雜度「不僅僅只是適用于平均情況,針對(duì)最壞的情況,同樣也能適用」.
- 空間復(fù)雜度
這個(gè)我們也可以看到我們整個(gè)排序的過(guò)程中需要增加一個(gè)等同于排序序列的長(zhǎng)度的空間來(lái)存儲(chǔ)我們?yōu)槎闻判蛑蟮男蛄?所以我們需要的空間復(fù)雜度就是線性級(jí)別的O(n),這個(gè)復(fù)雜度對(duì)比我們之前的幾種排序算法,可以看得出來(lái)的確是較為大了一點(diǎn).但是也可以明顯看出來(lái)整個(gè)的時(shí)間復(fù)雜度明顯降低了很多,這就是一種跟明顯通過(guò)犧牲空間換取時(shí)間的方法.對(duì)比我們第一篇講的HashMap.
3-快速排序
算法思想:
快速排序的算法思想也比較好理解.但是呢用文字講述出來(lái)可能會(huì)有點(diǎn)難以理解,這里我盡可能的講的簡(jiǎn)單些.就算還是看不懂的話也沒(méi)事,我們還是會(huì)通過(guò)圖片演示的形式來(lái)加深大家的理解的.
快速排序的思想就是每次排序都「選定一個(gè)基準(zhǔn)值」 ,當(dāng)我們?cè)谶x定完這個(gè)基準(zhǔn)值之后,我們就另外在需要兩個(gè)""指針"",這個(gè)指針并不是我們C++中的指針,但是作用也差不多,主要就是幫助我們標(biāo)記位置的.「這兩個(gè)指針?lè)謩e指向待排序序列的隊(duì)頭元素和隊(duì)尾元素」.
我們首先先「從隊(duì)尾元素開(kāi)始從右往左查找出第一個(gè)不大于該基準(zhǔn)值的元素」,找到之后首先將之前指向隊(duì)尾元素的指針指向該元素位置,之后再將基準(zhǔn)值與我們剛才查找到的元素交換位置.
在這個(gè)步驟結(jié)束之后,我們就需要「從隊(duì)頭元素開(kāi)始從左往右查找第一個(gè)不小于基準(zhǔn)值的元素」,查找到該元素之后還是按照我們上面的步驟.先將之前指向隊(duì)頭元素的指針指向該元素,之后再將基準(zhǔn)值與該元素交換位置.
重復(fù)上面這個(gè)步驟,「直到隊(duì)頭指針與隊(duì)尾指針相遇,相遇之后就代表我們的第一次排序就已經(jīng)完成了」,并且在第一次排序完成之后我們就會(huì)發(fā)現(xiàn)序列是這樣的狀態(tài),「基準(zhǔn)值左邊的元素全部小于等于該基準(zhǔn)值,基準(zhǔn)值右邊的元素全部大于等于該基準(zhǔn)值.」
之后的排序就只需要對(duì)基準(zhǔn)值左右兩邊的序列在進(jìn)行上述的操作即可.
好了關(guān)于算法的文字講解已經(jīng)完成了,當(dāng)然了,這時(shí)候很多小伙伴肯定會(huì)想 「"你這都說(shuō)的啥啊"」 ,沒(méi)關(guān)系老樣子還是用圖來(lái)說(shuō)話:
這里我只演示了第一次排序的過(guò)程,后續(xù)的相信大家可以自行腦補(bǔ)的. 理解完快速排序的基本算法思想之后,我們就需要來(lái)稍微聊聊快速排序的特點(diǎn)了.
快速排序本身是不穩(wěn)定的,我們首先先來(lái)了解一下不穩(wěn)定的快排是什么樣的演示過(guò)程.
通過(guò)上面的圖大家就能知道快排為啥是不穩(wěn)定的了.
「快速排序也有一個(gè)極端情況」,就是快排在對(duì) 「已經(jīng)有序的序列進(jìn)行排序」的時(shí)候,時(shí)間復(fù)雜度會(huì)直接飆到O(n*n),也就是最壞的時(shí)間復(fù)雜度,這個(gè)情況大家其實(shí)自己模擬以下就能知道了. 這里我們就不在過(guò)多講解了.算法圖解:
在這里插入圖片描述
示例代碼:
重要代碼我已經(jīng)添加了注釋能夠更加方便讀者們理解.
- public static void sort(int []num,int left,int right) {
- if(left<right) {
- int key=num[left];
- int i=left;
- int j=right;
- //這部分便是算法的核心思想
- while(i<j) {
- //從右向左找到第一個(gè)不大于基準(zhǔn)值的元素
- while(i<j&&num[j]>=key) {
- j--;
- }
- if(i<j) {
- num[i]=num[j];
- }
- //從左往右找到第一個(gè)不小于基準(zhǔn)值的元素
- while (i<j&&num[i]<=key) {
- i++;
- }
- if(i<j) {
- num[j]=num[i];
- }
- }
- num[i]=key;
- for(int k=0;k<num.length;k++) {
- System.out.print(num[k]+" ");
- }
- System.out.println();
- //遞歸繼續(xù)對(duì)剩余的序列排序
- sort(num, left, i-1);
- sort(num, i+1, right);
- }
- }
- public static void main(String[] args) {
- int []num ={7,4,9,3,2,1,8,6,5,10};
- long startTime=System.currentTimeMillis();
- sort(num, 0, num.length-1);
- long endTime=System.currentTimeMillis();
- System.out.println("程序運(yùn)行時(shí)間： "+(endTime-startTime)+"ms");
- }
因?yàn)樯厦娴膭?dòng)態(tài)演示圖已經(jīng)演示的很清楚了,所以就不在畫圖演示了.
復(fù)雜度分析:
理解完快速排序的基本思想之后,我們就需要來(lái)分析一下他的時(shí)間復(fù)雜度,空間復(fù)雜度.
- 時(shí)間復(fù)雜度
其實(shí)我們從上面的算法中能明顯看出來(lái)我們沒(méi)有使用for循環(huán),而是通過(guò)遞歸的方式來(lái)解決我們的循環(huán)問(wèn)題的.所以更加的高效.
就像我們上面所演示的一樣,平均情況下的時(shí)間復(fù)雜度即為O(N * log N),但是也想我們所說(shuō)的那樣,快速排序存在著一個(gè)極端情況就是 「已經(jīng)有序的序列進(jìn)行快排」 的話很剛好形成是類似于冒泡排序一樣的時(shí)間復(fù)雜度即為O(N * N),這是我們需要注意的,但是在大多數(shù)情況下,快排還是我們效率最高的排序算法.
- 空間復(fù)雜度
這個(gè)我們也可以看到我們整個(gè)排序的過(guò)程中每次排序的一個(gè)循環(huán)里面就需要添加一個(gè)空間來(lái)存儲(chǔ)我們的key,并且快排其實(shí)和我們上面的歸并排序也是有異曲同工之妙的,也有點(diǎn)類似于使用了二叉樹(shù)的概念,所以他的空間復(fù)雜度就是O(log N)
到這里十大經(jīng)典排序算法詳解的第二期內(nèi)容就已經(jīng)結(jié)束了.如果覺(jué)得UP的文章寫得還可以或者對(duì)你有幫助的話,可以關(guān)注UP的公眾號(hào),新人UP需要你的支持!!!
