[[377307]]

 1.算法的評(píng)判標(biāo)準(zhǔn)

在講解排序算法之前,我們首先來(lái)了解一下評(píng)判一個(gè)算法一般都是從哪些角度來(lái)評(píng)判的。

這個(gè)只要是稍微懂一點(diǎn)算法的小伙伴一定知道?！高@兩個(gè)標(biāo)準(zhǔn)就是時(shí)間復(fù)雜度和空間復(fù)雜度」

• 時(shí)間復(fù)雜度時(shí)間復(fù)雜度,這個(gè)其實(shí)很好理解,這個(gè)從字面意思來(lái)看,我們就能夠很好的理解了,就是整個(gè)算法執(zhí)行需要多長(zhǎng)的時(shí)間,這個(gè)時(shí)間復(fù)雜度又有兩個(gè)評(píng)判標(biāo)準(zhǔn),其實(shí)嚴(yán)格來(lái)說(shuō)有三個(gè)即 「最好情況,平均情況,最壞情況」,但是一般我們并不討論最好的情況,因?yàn)檫@個(gè)沒(méi)有意義.所以我們一般討論平均情況以及最壞的情況.

并且一般情況下,時(shí)間復(fù)雜度是我們最注重的,畢竟類比到我們平常生活中我們一般在乎的都是這個(gè)軟件運(yùn)行速度怎么樣,是不是快,慢的離譜之后,用戶的體驗(yàn)就會(huì)特別的差.一般不會(huì)說(shuō)這東西怎么又吃了我多少內(nèi)存空間.

其次另外一點(diǎn)就是 「時(shí)間復(fù)雜度是體現(xiàn)一個(gè)算法的最核心的地方」,畢竟空間復(fù)雜度稍微大一點(diǎn)還是可以接受的,但是如果算法的時(shí)間復(fù)雜度降不下來(lái),就算再怎么加空間也是解決不了問(wèn)題的.

• 空間復(fù)雜度空間復(fù)雜度其實(shí)也是很好理解的,指的就是「在算法的執(zhí)行過(guò)程中到底占用了多少的內(nèi)存空間」.這個(gè)大家一般并不是特別的在意空間復(fù)雜度.但是在這里給大家舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子,大家就能立馬了解這個(gè)概念了.

這個(gè)數(shù)據(jù)結(jié)構(gòu)就是HashMap,HashMap就是一種采取犧牲空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu).「Map能夠直接獲取到你想要鍵的元素」.

知道HashMap這么強(qiáng)大之后,大家就能知道為啥大廠問(wèn)到數(shù)據(jù)結(jié)構(gòu)的源碼的時(shí)候一般都是會(huì)問(wèn)HashMap的源碼了,因?yàn)樗@樣設(shè)計(jì)是真的流弊.

2.排序算法的分類

了解完上述算法的評(píng)判標(biāo)準(zhǔn)之后,我們就需要來(lái)看看這些排序算法又是怎么進(jìn)行分類的了. 主要有這么兩種分類的方式.

排序類型

在這里插入圖片描述

這里的比較就和大家平常理解的比較是一個(gè)意思,就是主要是通過(guò)比較來(lái)進(jìn)行排序的.

• 是否穩(wěn)定

這里的穩(wěn)定就需要和大家稍微說(shuō)一說(shuō)了,這里的穩(wěn)定指的是相同的元素在排序之后的相對(duì)位置對(duì)比排序之前是否是一樣的,如果沒(méi)有發(fā)生變化的,那么就稱這個(gè)算法是穩(wěn)定的.這樣說(shuō)的話,大家可能不是很能理解,這里我們還是通過(guò)下面的圖來(lái)幫助大家加深印象.

了解完上面這些概念之后,接下來(lái)我們講解排序算法的時(shí)候提出的一些概念大家就能比較好的理解了.

3.十大經(jīng)典排序算法-冒泡排序,選擇排序,插入排序

3.1-冒泡排序

算法思想:

說(shuō)到冒泡,大家的第一反應(yīng)可能就是下圖里面金魚(yú)吐泡泡的畫(huà)面

[[377308]]

在畫(huà)面里面我們就能看出來(lái),泡泡是越往上泡泡越大.這個(gè)就是冒泡排序的核心思想:每次循環(huán)都找出剩余排序序列中的一個(gè)最大值或最小值,并且將它置換到序列的最末尾或者是最開(kāi)始的位置.舉下面這個(gè)簡(jiǎn)單的例子,大家就能理解了:

這就是冒泡排序的基本思想.并且我們能稍微總結(jié)一下冒泡排序的特點(diǎn):

• 每次排序都能「至少確定一個(gè)元素的最終位置」
• 冒泡冒泡排序是「穩(wěn)定的」,「只有當(dāng)元素的大小不一樣時(shí),元素之間才會(huì)交換位置」,這就使得相同元素的相對(duì)位置在排序之前以及排序之后都是不變的,所以冒泡排序是穩(wěn)定的.
• 冒泡排序有一個(gè)「極端情況」,假如「我們規(guī)定的排序方式是從大到小的」,「但是原序列的順序是從小到大的話」,那么小伙伴們這時(shí)候就會(huì)發(fā)現(xiàn),我們「每次比較元素之后都需要將這兩個(gè)元素進(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 i=0;i<num.length-1;i++) { 
  for(int j=0;j<num.length-1-i;j++) { 
   if(num[j]>num[j+1]) { 
    int temp=num[j+1]; 
    num[j+1]=num[j]; 
    num[j]=temp; 
   } 
  } 
  System.out.print("第"+(i+1)+"次排序結(jié)果:"); 
  for(int j=0;j<num.length;j++) 
   System.out.print(num[j]+" "); 
  System.out.println(); 
 } 
 long endTime=System.currentTimeMillis();  
 System.out.println("程序運(yùn)行時(shí)間： "+(endTime-startTime)+"ms");  
} 

在這里插入圖片描述

復(fù)雜度分析:

理解完冒泡排序的基本思想之后,我們就需要來(lái)分析一下他的時(shí)間復(fù)雜度,空間復(fù)雜度.

• 時(shí)間復(fù)雜度 時(shí)間復(fù)雜度我們從兩個(gè)方面來(lái)評(píng)判
  • 平均情況 平均情況下我們的算法復(fù)雜度主要就是在進(jìn)行元素的比較的過(guò)程.即進(jìn) if(num[j]>num[j+1])的過(guò)程,這個(gè)過(guò)程平均下來(lái)就是我們兩層for循環(huán)的次數(shù),這個(gè)我們計(jì)算一下就能得出是n*(n-1)/2,我們?nèi)プ畲蟮拇螖?shù),可以看到時(shí)間復(fù)雜度就是O(n*n)
  • 最壞情況 最壞情況就是我們上面說(shuō)的極端情況.但是極端情況只是比我們的平均情況多執(zhí)行了交換元素的操作,但是比較的次數(shù)是一直不變的,所以這樣算下來(lái)時(shí)間復(fù)雜度也是O(n*n)
• 空間復(fù)雜度

這個(gè)我們也可以看到我們整個(gè)排序的過(guò)程中值增加了一個(gè)空間,這個(gè)空間就是我們定義的temp,主要就是幫助我們進(jìn)行元素的交換的.所以冒泡排序的空間復(fù)雜度即為O(1)

3.2-選擇排序

算法思想: 選擇排序的重點(diǎn)就是選擇,選擇的方式就是每次循環(huán)選出最小的元素,然后將最小的元素與排序序列中的隊(duì)頭元素進(jìn)行置換.還是老樣子,通過(guò)下面的圖來(lái)讓大家更好的理解這一個(gè)選擇的過(guò)程:

這是我們基本就能理解選擇排序的基本概念.這里我們「需要和上面的冒泡排序區(qū)分一點(diǎn)」的就是,選擇排序「在比較結(jié)束之后并不會(huì)直接交換兩個(gè)元素的位置,只是記錄當(dāng)前序列中的最小元素」 ,當(dāng)找到最小的元素之后,在將該最小元素與隊(duì)頭的元素進(jìn)行置換. 了解完這些之后,我們也來(lái)稍微說(shuō)一下選擇排序的特點(diǎn):

• 「每次循環(huán)必定能夠確定一個(gè)元素的最終位置」,這一點(diǎn)和冒泡排序是一樣的
• 選擇排序也是不穩(wěn)定的,這里大家可能會(huì)不理解,還是老樣子我們還是通過(guò)下面的圖來(lái)掩飾一下大家就懂了:

算法圖解:

在這里插入圖片描述

示例代碼:

public static void main(String[] args) { 
  int []num ={7,4,9,3,2,1,8,6,5,10}; 
  long startTime=System.currentTimeMillis();   
  for(int i=0;i<num.length-1;i++) { 
   int min=i; 
   for(int j=i+1;j<num.length;j++) { 
    if(num[min]>num[j]) { 
     min=j; 
    } 
   } 
   if(i!=min) { 
    int temp=num[i]; 
    num[i]=num[min]; 
    num[min]=temp; 
   } 
   System.out.print("第"+(i+1)+"次排序結(jié)果:"); 
   for(int j=0;j<num.length;j++) 
    System.out.print(num[j]+" "); 
   System.out.println(); 
  } 
  long endTime=System.currentTimeMillis();  
  System.out.println("程序運(yùn)行時(shí)間： "+(endTime-startTime)+"ms");  
 } 

復(fù)雜度分析:

理解完選擇排序的基本思想之后,我們就需要來(lái)分析一下他的時(shí)間復(fù)雜度,空間復(fù)雜度.

• 時(shí)間復(fù)雜度 時(shí)間復(fù)雜度我們從兩個(gè)方面來(lái)評(píng)判
  • 平均情況 平均情況下我們的算法復(fù)雜度主要就是在進(jìn)行元素的比較的過(guò)程.即進(jìn) if(num[min]>num[j])的過(guò)程,這個(gè)過(guò)程平均下來(lái)就是我們兩層for循環(huán)的次數(shù),這個(gè)我們計(jì)算一下就能得出是n*(n-1)/2,我們?nèi)プ畲蟮拇螖?shù),可以看到時(shí)間復(fù)雜度就是O(n*n)
  • 最壞情況 最壞情況本質(zhì)上和我們的平均情況是一樣的,因?yàn)椴还苁瞧骄闆r還是最壞情況,都是只在最后置換最小元素與隊(duì)頭元素的位置,比較的次數(shù)也是一樣的,所以這樣算下來(lái)時(shí)間復(fù)雜度也是O(n*n)
• 空間復(fù)雜度

這個(gè)我們也可以看到我們整個(gè)排序的過(guò)程中值增加了兩個(gè)個(gè)空間,這個(gè)空間就是我們定義的temp和min,所以選擇排序的空間復(fù)雜度也是常量級(jí)別的即為O(1)

3.3-插入排序

算法思想: 插入排序的算法思想則是將整個(gè)序列劃分成兩段,一段時(shí)已經(jīng)排序完成的序列,另一端序列則是仍然無(wú)需的狀態(tài).就比方下圖所示:

分成這樣兩個(gè)序列之后,插入序列每次都是挑選待排序序列的隊(duì)頭元素插入到已有序的序列之中,從有序序列的隊(duì)尾開(kāi)始比較,如果比該元素大的話,將該元素后移,一旦出現(xiàn)小于該元素的元素,插入當(dāng)前的位置.這個(gè)就是插入排序名字的由來(lái).

說(shuō)了半天大家可能還是不太了解,還是通過(guò)下面的圖來(lái)詳細(xì)講解一下該算法的執(zhí)行過(guò)程吧:

理解完插入排序算法的基本思想之后我們?cè)賮?lái)看看該算法的特點(diǎn):

• 這個(gè)其實(shí)「不算特點(diǎn)」,只是和上述兩個(gè)算法對(duì)比之后,大家可以發(fā)現(xiàn)該算法不像上面的冒泡與選擇排序一樣,每次循環(huán)排序都能確定一個(gè)元素的最終位置.「插入排序每次循環(huán)排序之后是不能夠唯一確定一個(gè)元素的最終位置的.他只能是每次循環(huán)之后確定一些元素的相對(duì)位置.」
• 插入排序和冒泡排序一樣也有一個(gè)「極端的排序情況」,但是冒泡排序的極端情況是最慘的情況,但是插入排序的極端情況就是最爽的情況.就是在序列已經(jīng)基本有序的時(shí)候,插入排序是最快的,時(shí)間復(fù)雜度可以達(dá)到O(n)即線性級(jí)別.「因?yàn)橐坏┬蛄杏行蛑?for循環(huán)仍然需要執(zhí)行,但是在while循環(huán)里面就根本不用執(zhí)行了」,這就是插入排序能夠達(dá)到線性級(jí)別的關(guān)鍵.對(duì)比冒泡和選擇排序,「他們都是通過(guò)兩層for循環(huán)進(jìn)行的,但是插入排序的第二層循環(huán)是通過(guò)while并且有相應(yīng)的終止條件」,這就使得插入排序的性能比上面兩者會(huì)相對(duì)好一點(diǎn).當(dāng)然了,「這種情況只存在于序列已經(jīng)基本有序的情況」.

算法圖解:

在這里插入圖片描述

示例代碼:

public static void main(String[] args) { 
  int []num ={7,4,9,3,2,1,8,6,5,10}; 
  long startTime=System.currentTimeMillis();   
  for(int i=1;i<num.length;i++) { 
   int temp=num[i]; 
   int j=i; 
   while(j>0&&temp<num[j-1]) { 
    num[j]=num[j-1]; 
    j--; 
   } 
   if(j!=i) { 
    num[j]=temp; 
   } 
   System.out.print("第"+i+"次排序結(jié)果:"); 
   for(int k=0;k<num.length;k++) 
    System.out.print(num[k]+" "); 
   System.out.println(); 
  } 
  long endTime=System.currentTimeMillis();  
  System.out.println("程序運(yùn)行時(shí)間： "+(endTime-startTime)+"ms");  
 } 

在這里插入圖片描述

復(fù)雜度分析:

理解完插入排序的基本思想之后,我們就需要來(lái)分析一下他的時(shí)間復(fù)雜度,空間復(fù)雜度.

• 時(shí)間復(fù)雜度 時(shí)間復(fù)雜度我們從三個(gè)方面來(lái)評(píng)判,這里就必須要提一下我們上面所說(shuō)的極端情況了
  • 最佳情況 時(shí)間復(fù)雜度能夠達(dá)到線性級(jí)別O(n)
  • 平均情況 平均情況下我們的算法復(fù)雜度主要就是在進(jìn)行元素的比較的過(guò)程.即進(jìn) temp
  • 最壞情況 最壞情況本質(zhì)上和我們的平均情況是一樣的,因?yàn)椴还苁瞧骄闆r還是最壞情況,都是只比較的次數(shù)也是一樣的,所以這樣算下來(lái)時(shí)間復(fù)雜度也是O(n*n)
• 空間復(fù)雜度

這個(gè)我們也可以看到我們整個(gè)排序的過(guò)程中值增加了兩個(gè)個(gè)空間,這個(gè)空間就是我們定義的temp和j,所以選擇排序的空間復(fù)雜度也是常量級(jí)別的即為O(1)

本文轉(zhuǎn)載自微信公眾號(hào)「萌萌噠的瓤瓤」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系萌萌噠的瓤瓤公眾號(hào)。