《算法圖解》讀書筆記-03

閱讀上一篇文章

文章目錄

• 第二章：排序
• • 1.選擇排序
  • 2.冒泡排序
  • 3.插入排序
  • 4.堆排序
  • 5.歸并排序
  • 6.快速排序
• 持續更新中...

第二章：排序

衆所周知，紛繁複雜的排序算法是無數面試官折磨畢業生的神奇；現在就讓我們來看看各種各樣的排序算法吧；

1.選擇排序

冒泡排序的邏輯是：

• 從需要排序的序列中選出最小值放置到左邊
• 下一個循環将不考慮最左側的元素
• 序列隻有一個元素時停止排序

冒泡排序的複雜度是 O ( n 2 ) O(n^2) O(n2)

2.冒泡排序

冒泡排序的邏輯是：

• 虛拟掃描頭同時檢查兩個兩個相鄰變量，左大于右則不變，否則交換位置
• 掃描頭向右移動一格，檢查并交換變量
• 此過程循環進行，直到某次循環沒有進行任何操作時，循環終止

冒泡排序的複雜度也是 O ( n 2 ) O(n^2) O(n2)

3.插入排序

插入排序的邏輯是：

• 從右側取一個元素，插入到左側已經排序過的序列中合适的位置
• 左側排序過的序列長度加一，右側未排序過的序列長度減一
• 循環執行直到全部元素都已排序

第一次開始排序時，需要從序列中選出一個最小的放置在最左邊；

插入排序的時間複雜度是 O ( n 2 ) O(n^2) O(n2)

4.堆排序

前面的文章中提到過堆，而使用堆排序也是一種可行的辦法；具體的做法是：先建構一個堆，再一個一個取出元素，然後排序就完成了；

堆的建構方式，元素的取出操作都在前面的文章中提到了；

堆排序的時間複雜度為 O ( n lg ⁡ n ) O(n\lg{n}) O(nlgn)

5.歸并排序

歸并排序的精髓是：把一個序列分割為兩個序列，把剩下的序列一分為二，直到不能再分割為止；然後開始把相鄰的兩個序列合并，每次合并時都進行排序，當從所有序列全部都合成為一個序列時，排序就完成了；

歸并排序的複雜度為 O ( n lg ⁡ n ) O(n\lg{n}) O(nlgn)，和堆排序相同；

6.快速排序

說實話這個排序算法的名字起的相當嚣張；

這個算法首先在序列中随機選擇一個數作為基準值，然後将小于這個數的值放在左邊，将大于這個數的值放在右邊；接着對基準值兩邊的序列執行相同的操作，直到序列被完全排序為止；

快速排序的平均運作時間為 O ( n lg ⁡ n ) O(n\lg{n}) O(nlgn)，顯然對不起這個名字，它和歸并排序和堆排序的時間複雜度是一樣的；

持續更新中…