分類:
1)插入排序(直接插入排序、希爾排序)
2)交換排序(冒泡排序、快速排序)
3)選擇排序(直接選擇排序、堆排序)
4)歸并排序
5)配置設定排序(基數排序)
所需輔助空間最多:歸并排序
所需輔助空間最少:堆排序
平均速度最快:快速排序
不穩定:快速排序,希爾排序,堆排序。
先來看看8種排序之間的關系:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZwpmL2AjN58FNwkDOwAzN0MTMvw1Nw8CX5AjMxAjMvw1ckF2bsBXdvwFdl5mLuR2cj5Set1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
1.直接插入排序
(1)基本思想:在要排序的一組數中,假設前面(n-1)[n>=2] 個數已經是排
好順序的,現在要把第n個數插到前面的有序數中,使得這n個數
也是排好順序的。如此反複循環,直到全部排好順序。
(2)執行個體
(3)用java實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
2. 希爾排序(最小增量排序)
(1)基本思想:算法先将要排序的一組數按某個增量d(n/2,n為要排序數的個數)分成若幹組,每組中記錄的下标相差d.對每組中全部元素進行直接插入排序,然後再用一個較小的增量(d/2)對它進行分組,在每組中再進行直接插入排序。當增量減到1時,進行直接插入排序後,排序完成。
(2)執行個體:
(3)用java實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | |
3.簡單選擇排序
(1)基本思想:在要排序的一組數中,選出最小的一個數與第一個位置的數交換;
然後在剩下的數當中再找最小的與第二個位置的數交換,如此循環到倒數第二個數和最後一個數比較為止。
(2)執行個體:
(3)用java實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |
4.堆排序
(1)基本思想:堆排序是一種樹形選擇排序,是對直接選擇排序的有效改進。
堆的定義如下:具有n個元素的序列(h1,h2,…,hn),當且僅當滿足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,…,n/2)時稱之為堆。在這裡隻讨論滿足前者條件的堆。由堆的定義可以看出,堆頂元素(即第一個元素)必為最大項(大頂堆)。完全二叉樹可以很直覺地表示堆的結構。堆頂為根,其它為左子樹、右子樹。初始時把要排序的數的序列看作是一棵順序存儲的二叉樹,調整它們的存儲序,使之成為一個堆,這時堆的根節點的數最大。然後将根節點與堆的最後一個節點交換。然後對前面(n-1)個數重新調整使之成為堆。依此類推,直到隻有兩個節點的堆,并對它們作交換,最後得到有n個節點的有序序列。從算法描述來看,堆排序需要兩個過程,一是建立堆,二是堆頂與堆的最後一個元素交換位置。是以堆排序有兩個函數組成。一是建堆的滲透函數,二是反複調用滲透函數實作排序的函數。
(2)執行個體:
初始序列:46,79,56,38,40,84
建堆:
交換,從堆中踢出最大數
剩餘結點再建堆,再交換踢出最大數
依次類推:最後堆中剩餘的最後兩個結點交換,踢出一個,排序完成。
(3)用java實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | |
5.冒泡排序
(1)基本思想:在要排序的一組數中,對目前還未排好序的範圍内的全部數,自上而下對相鄰的兩個數依次進行比較和調整,讓較大的數往下沉,較小的往上冒。即:每當兩相鄰的數比較後發現它們的排序與排序要求相反時,就将它們互換。
(2)執行個體:
(3)用java實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |
6.快速排序
(1)基本思想:選擇一個基準元素,通常選擇第一個元素或者最後一個元素,通過一趟掃描,将待排序列分成兩部分,一部分比基準元素小,一部分大于等于基準元素,此時基準元素在其排好序後的正确位置,然後再用同樣的方法遞歸地排序劃分的兩部分。
(2)執行個體:
(3)用java實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | |
7、歸并排序
(1)基本排序:歸并(Merge)排序法是将兩個(或兩個以上)有序表合并成一個新的有序表,即把待排序序列分為若幹個子序列,每個子序列是有序的。然後再把有序子序列合并為整體有序序列。
(2)執行個體:
(3)用java實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | |
8、基數排序
(1)基本思想:将所有待比較數值(正整數)統一為同樣的數位長度,數位較短的數前面補零。然後,從最低位開始,依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後,數列就變成一個有序序列。
(2)執行個體:
(3)用java實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | |