[[377307]]

 1.算法的評判標準

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

這個只要是稍微懂一點算法的小伙伴一定知道?！高@兩個標準就是時間復雜度和空間復雜度」

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

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

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

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

這個數據結構就是HashMap,HashMap就是一種采取犧牲空間換時間的數據結構.「Map能夠直接獲取到你想要鍵的元素」.

知道HashMap這么強大之后,大家就能知道為啥大廠問到數據結構的源碼的時候一般都是會問HashMap的源碼了,因為它這樣設計是真的流弊.

2.排序算法的分類

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

排序類型

在這里插入圖片描述

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

• 是否穩定

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

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

3.十大經典排序算法-冒泡排序,選擇排序,插入排序

3.1-冒泡排序

算法思想:

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

[[377308]]

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

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

• 每次排序都能「至少確定一個元素的最終位置」
• 冒泡冒泡排序是「穩定的」,「只有當元素的大小不一樣時,元素之間才會交換位置」,這就使得相同元素的相對位置在排序之前以及排序之后都是不變的,所以冒泡排序是穩定的.
• 冒泡排序有一個「極端情況」,假如「我們規定的排序方式是從大到小的」,「但是原序列的順序是從小到大的話」,那么小伙伴們這時候就會發現,我們「每次比較元素之后都需要將這兩個元素進行交換」.這種情況就是冒泡排序最極端的情況.

算法圖解:

在這里插入圖片描述

示例代碼:

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)+"次排序結果:"); 
  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");  
} 

在這里插入圖片描述

復雜度分析:

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

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

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

3.2-選擇排序

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

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

• 「每次循環必定能夠確定一個元素的最終位置」,這一點和冒泡排序是一樣的
• 選擇排序也是不穩定的,這里大家可能會不理解,還是老樣子我們還是通過下面的圖來掩飾一下大家就懂了:

算法圖解:

在這里插入圖片描述

示例代碼:

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)+"次排序結果:"); 
   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");  
 } 

復雜度分析:

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

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

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

3.3-插入排序

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

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

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

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

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

算法圖解:

在這里插入圖片描述

示例代碼:

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+"次排序結果:"); 
   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");  
 } 

在這里插入圖片描述

復雜度分析:

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

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

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

本文轉載自微信公眾號「萌萌噠的瓤瓤」，可以通過以下二維碼關注。轉載本文請聯系萌萌噠的瓤瓤公眾號。