[[377307]]

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

在講解排序算法之前,我們首先來了解一下評判一個算法一般都是從哪些角度來評判的。

這個只要是稍微懂一點算法的小伙伴一定知道。「這兩個標(biāo)準(zhǔn)就是時間復(fù)雜度和空間復(fù)雜度」

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

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

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

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

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

知道HashMap這么強大之后,大家就能知道為啥大廠問到數(shù)據(jù)結(jié)構(gòu)的源碼的時候一般都是會問HashMap的源碼了,因為它這樣設(shè)計是真的流弊.

2.排序算法的分類

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

排序類型

在這里插入圖片描述

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

• 是否穩(wěn)定

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

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

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

3.1-冒泡排序

算法思想:

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

[[377308]]

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

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

• 每次排序都能「至少確定一個元素的最終位置」
• 冒泡冒泡排序是「穩(wěn)定的」,「只有當(dāng)元素的大小不一樣時,元素之間才會交換位置」,這就使得相同元素的相對位置在排序之前以及排序之后都是不變的,所以冒泡排序是穩(wěn)定的.
• 冒泡排序有一個「極端情況」,假如「我們規(guī)定的排序方式是從大到小的」,「但是原序列的順序是從小到大的話」,那么小伙伴們這時候就會發(fā)現(xià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 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("程序運行時間： "+(endTime-startTime)+"ms");  
} 

在這里插入圖片描述

復(fù)雜度分析:

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

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

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

3.2-選擇排序

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

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

• 「每次循環(huán)必定能夠確定一個元素的最終位置」,這一點和冒泡排序是一樣的
• 選擇排序也是不穩(wě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++) { 
   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("程序運行時間： "+(endTime-startTime)+"ms");  
 } 

復(fù)雜度分析:

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

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

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

3.3-插入排序

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

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

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

理解完插入排序算法的基本思想之后我們再來看看該算法的特點:

• 這個其實「不算特點」,只是和上述兩個算法對比之后,大家可以發(fā)現(xiàn)該算法不像上面的冒泡與選擇排序一樣,每次循環(huán)排序都能確定一個元素的最終位置.「插入排序每次循環(huán)排序之后是不能夠唯一確定一個元素的最終位置的.他只能是每次循環(huán)之后確定一些元素的相對位置.」
• 插入排序和冒泡排序一樣也有一個「極端的排序情況」,但是冒泡排序的極端情況是最慘的情況,但是插入排序的極端情況就是最爽的情況.就是在序列已經(jīng)基本有序的時候,插入排序是最快的,時間復(fù)雜度可以達(dá)到O(n)即線性級別.「因為一旦序列有序之后,for循環(huán)仍然需要執(zhí)行,但是在while循環(huán)里面就根本不用執(zhí)行了」,這就是插入排序能夠達(dá)到線性級別的關(guān)鍵.對比冒泡和選擇排序,「他們都是通過兩層for循環(huán)進(jìn)行的,但是插入排序的第二層循環(huán)是通過while并且有相應(yīng)的終止條件」,這就使得插入排序的性能比上面兩者會相對好一點.當(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("程序運行時間： "+(endTime-startTime)+"ms");  
 } 

在這里插入圖片描述

復(fù)雜度分析:

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

• 時間復(fù)雜度 時間復(fù)雜度我們從三個方面來評判,這里就必須要提一下我們上面所說的極端情況了
  • 最佳情況 時間復(fù)雜度能夠達(dá)到線性級別O(n)
  • 平均情況 平均情況下我們的算法復(fù)雜度主要就是在進(jìn)行元素的比較的過程.即進(jìn) temp
  • 最壞情況 最壞情況本質(zhì)上和我們的平均情況是一樣的,因為不管是平均情況還是最壞情況,都是只比較的次數(shù)也是一樣的,所以這樣算下來時間復(fù)雜度也是O(n*n)
• 空間復(fù)雜度

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

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