1. 數據結構和算法(十三)排序算法

1.1 排序算法

??所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。

1.2 排序算法分類

• 內部排序：指將需要處理的所有數據都加載到內部存儲器中進行排序。
• 外部排序法：數據量過大，無法全部加載到內存中，需要借助外部存儲進行排序。

1.3 常見的排序算法分類

1.4 算法的時間與空間復雜度

主要還是從算法所占用的「時間」和「空間」兩個維度去考量。

• 時間頻率

  • 一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為時間頻度。記為T(n)。

• 時間復雜度

  • 在時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什么規律。為此，我們引入時間復雜度概念。 一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間復雜度，簡稱時間復雜度。

  • T(n) 不同，但時間復雜度可能相同。 如：T(n)=n2+7n+6 與 T(n)=3n2+2n+2 它們的T(n)?不同，但時間復雜度相同，都為O(n2)。

  • 計算時間復雜度的方法：
    用常數1代替運行時間中的所有加法常數? T(n)=n2+7n+6 => T(n)=n2+7n+1修改后的運行次數函數中，只保留最高階項? T(n)=n2+7n+1 => T(n) = n2 去除最高階項的系數 T(n) = n2 => T(n) = n2 => O(n2)

1.5 常見的時間復雜度

• 常見的時間復雜度
  
  ??常見的算法時間復雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ，隨著問題規模n的不斷增大，上述時間復雜度不斷增大，算法的執行效率越低
  從圖中可見，我們應該盡可能避免使用指數階的算法。

• 常數階O(1)

  • 無論代碼執行了多少行，只要是沒有循環等復雜結構，那這個代碼的時間復雜度就都是O(1).
  int i = 1 int j = 2;i = i + j - i; j = i + j - j;

• 對數階O(log2n)

  • 在while循環里面，每次都將 i 乘以 2，乘完之后，i 距離 n 就越來越近了。假設循環x次之后，i 就大于 2 了，此時這個循環就退出了，也就是說 2 的 x 次方等于 n，那么 x = log2n也就是說當循環 log2n 次以后，這個代碼就結束了。因此這個代碼的時間復雜度為：O(log2n) 。
  int i =1;while(i < n){i = i * 2;}

• 線性階O(n)

  • for循環里面的代碼會執行n遍，因此它消耗的時間是隨著n的變化而變化的，因此這類代碼都可以用O(n)來表示它的時間復雜度
  for(int i = 1; i <= number; i++){j = i * 2;}

• 線性對數階O(nlogN)

  • 將時間復雜度為O(logn)的代碼循環N遍的話，那么它的時間復雜度就是 n * O(logN)，也就是了O(nlogN)
  for(int i = 1; i <= number; i++){while(i < number){i = i * 2;}}

• 平方階O(n2)

  • 如果把 O(n) 的代碼再嵌套循環一遍，它的時間復雜度就是 O(n2)，這段代碼其實就是嵌套了2層n循環，它的時間復雜度就是 O(nn)，即 ?O(n2)?如果將其中一層循環的n改成m，那它的時間復雜度就變成了 O(mn)
  for (i=1;i<n;i++){for (j=0;j<=n;j++){j = i;j++;}}

• 立方階O(n3)、K次方階O(n^k)

  • O(n3)相當于三層n循環。K次方階相當于k層n循環。

1.6 平均時間復雜度和最壞時間復雜度

• 平均時間復雜度是指所有可能的輸入實例均以等概率出現的情況下，該算法的運行時間。
• 最壞情況下的時間復雜度稱最壞時間復雜度。一般討論的時間復雜度均是最壞情況下的時間復雜度。?這樣做的原因是：最壞情況下的時間復雜度是算法在任何輸入實例上運行時間的界限，這就保證了算法的運行時間不會比最壞情況更長。
• 平均時間復雜度和最壞時間復雜度是否一致

排序法平均時間最差情形穩定度額外空間備注

冒泡	O(n2)	O(n2)	穩定	O(1)	n小時較好
交換	O(n2)	O(n2)	不穩定	O(1)	n小時較好
選擇	O(n2)	O(n2)	不穩定	O(1)	n小時較好
插入	O(n2)	O(n2)	穩定	O(1)	大部分已排序時較好
基數	O(logRB)	O(logRB)	穩定	O(n)	B是真數(0-9)，R是基數(個十百)
希爾	O(nlogin)	O(ns)1<s<2	不穩定	O(1)	s是所選分組
快速	O(nlogin)	O(n2)	不穩定	O(nlogin)	n大時較好
歸并	O(nlogin)	O(nlogin)	穩定	O(1)	n大時較好
堆	O(nlogin)	O(nlogin)	不穩定	O(1)	n大時較好

????– 以上為《數據結構和算法(十三)排序算法》，如有不當之處請指出，我后續逐步完善更正，大家共同提高。謝謝大家對我的關注。

——厚積薄發(yuanxw)

總結

以上是生活随笔為你收集整理的数据结构和算法(十三)排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。