本文來用圖文的方式詳細講解了Python十大經典排序算法 —— 插入排序、選擇排序、快速排序、冒泡排序、歸并排序、希爾排序、插入排序、桶排序、基數排序、計數排序算法，想要學習的你們，繼續閱讀下去吧，如果覺得不錯的話，推薦給身邊的朋友吧。
插入排序
思路
- 從第一個元素開始，該元素可以認為已經被排序；
- 取出下一個元素，在已經排序的元素序列中從后向前掃描；
- 如果該元素（已排序）大于新元素，將該元素移到下一位置；
- 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
- 將新元素插入到該位置；
- 重復步驟2~5。
代碼
圖示
平均時間復雜度
O(n^2)
希爾排序
前言
希爾排序是插排的升級，先將待排序的元素進行分組，在分組的基礎上進行插排，從而降低整體上的時間復雜度。
這里面設計到一個增量的概念，我們依據增量來決定分組的跨度。常用的增量有三種：
- 希爾增量 [1,2,4,8,…,2^(k-1)]
- 海巴德增量 [1,3,7,15,…,2^k-1]
- 塞基維克增量 [1,5,19,41,…,4k-3*2k+1]
一般情況下希爾增量帶來的時間復雜度小于O(n2),但在極壞情況下可能效果不明顯甚至超過這個值。海巴德增量可以將時間復雜控制在O(n(3/2))以下，而塞基維克增量該項參數為O(n^(4/3))。
思路
- 擇定增量
- 分組
- 組內比較
- 重復步驟2,3直到跨度為1
圖示
代碼
選擇排序
思路
- 選出數組中最大（最?。┑脑胤诺介_頭
- 在剩下的元素中選中最大（最?。┰胤诺缴蟼€被選元素之后
- 重復2步驟
圖示
代碼
平均時間復雜度
O(n^2)
堆排序
前言
堆排序，顧名思義，就是基于堆。因此先來介紹一下堆的概念。
堆分為最大堆和最小堆，其實就是完全二叉樹。最大堆要求節點的元素都要大于其孩子，最小堆要求節點元素都小于其左右孩子，兩者對左右孩子的大小關系不做任何要求，其實很好理解。有了上面的定義，我們可以得知，處于最大堆的根節點的元素一定是這個堆中的最大值。其實我們的堆排序算法就是抓住了堆的這一特點，每次都取堆頂的元素，將其放在序列最后面，然后將剩余的元素重新調整為最大堆，依次類推，最終得到排序的序列。
思路
- 把堆頂的最大數取出
- 將剩余的堆繼續調整為最大堆
- 重復步驟1,2
圖示
代碼
平均時間復雜度
O(nlogn)
冒泡排序
思路
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
- 針對所有的元素重復以上的步驟，除了最后一個。
- 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
圖示
代碼
平均時間復雜度
O(n^2)
快速排序
思路
- 先從集合中取出一個數作為“哨兵”
- 將集合中比哨兵大的元素和比哨兵小的元素分列兩側
- 再對左右區間重復第二步，直到各區間只有一個數
圖示
代碼
平均時間復雜度
O(nlogn)
歸并排序
思路
- 將列表拆分成兩個有序子模塊
- 遞歸拆分
- 子模塊內部進行排序并合并成大的模塊
- 遞歸合并
圖示
代碼
平均時間復雜度
O(nlogn)
計數排序
思路
- 找出集合中最小數m和最大數n
- 建一個長為(m-n+1)的列表count_list，所有元素初始化為0
- 遍歷集合，元素減去n得到的結果作為index，將count_list該位上的元素加1。
- 初始化空列表result。
- 將count_list序列化，用索引值減去n,得到的結果追加到result中,索引值對應的位元素值減1，直到它為0。
- 重復步驟5。
圖示
代碼
平均時間復雜度
O(n)
桶排序
前言
桶排序是將待排序集合中處于同一個值域的元素存入同一個桶中，也就是根據元素值特性將集合拆分為多個區域，則拆分后形成的多個桶，從值域上看是處于有序狀態的。對每個桶中元素進行排序，則所有桶中元素構成的集合是已排序的。
思路
- 根據待排序集合中最大元素和最小元素的差值范圍和映射規則，確定申請的桶個數；
- 遍歷待排序集合，將每一個元素移動到對應的桶中；
- 對每一個桶中元素進行排序，并移動到已排序集合中。
圖示
代碼
平均時間復雜度
O(n^2)
基數排序
思路
- 首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶中;
- 接下來將這些桶中的數值重新串接起來，成為以下的數列。接著再進行一次分配，這次是根據十位數來分配；
- 接下來將這些桶中的數值重新串接起來，持續進行以上的動作直至最高位數為止。
圖示
代碼
平均時間復雜度
O(d*2*n), 這里的d是數值位數
本文來自熱心好友原味吐司的投稿，點贊！
更多有關python、深度學習和計算機編程的精彩內容，可以關注微信公眾號：哆啦A夢愛學習
