排序算法平均時間復(fù)雜度冒泡排序O(n2)選擇排序O(n2)插入排序O(n2)希爾排序O(n1.5)快速排序O(N*logN)歸并排序O(N*logN)堆排序O(N*logN)基數(shù)排序O(d(n+r))

一. 冒泡排序(BubbleSort)

1. 基本思想：

   兩個數(shù)比較大小，較大的數(shù)下沉，較小的數(shù)冒起來。

2. 過程：

• 比較相鄰的兩個數(shù)據(jù)，如果第二個數(shù)小，就交換位置。
• 從后向前兩兩比較，一直到比較最前兩個數(shù)據(jù)。最終最小數(shù)被交換到起始的位置，這樣第一個最小數(shù)的位置就排好了。
• 繼續(xù)重復(fù)上述過程，依次將第2.3...n-1個最小數(shù)排好位置。

• 
  
• 冒泡排序

1. 平均時間復(fù)雜度：

   O(n2)

2. java代碼實(shí)現(xiàn)：

3. public static void BubbleSort(int [] arr){
4. int temp;//臨時變量
5. for(int i=0; i
6. for(int j=arr.length-1; j>i; j--){
7. if(arr[j] <>
8. temp = arr[j];
9. arr[j] = arr[j-1];
10. arr[j-1] = temp;
11. }
12. }
13. }
14. }

15. 優(yōu)化：

• 針對問題：

• 數(shù)據(jù)的順序排好之后，冒泡算法仍然會繼續(xù)進(jìn)行下一輪的比較，直到arr.length-1次，后面的比較沒有意義的。

• 方案：

• 設(shè)置標(biāo)志位flag，如果發(fā)生了交換flag設(shè)置為true；如果沒有交換就設(shè)置為false。
• 這樣當(dāng)一輪比較結(jié)束后如果flag仍為false，即：這一輪沒有發(fā)生交換，說明數(shù)據(jù)的順序已經(jīng)排好，沒有必要繼續(xù)進(jìn)行下去。
• public static void BubbleSort1(int [] arr){
• int temp;//臨時變量
• boolean flag;//是否交換的標(biāo)志
• for(int i=0; i
• flag = false;
• for(int j=arr.length-1; j>i; j--){
• if(arr[j] <>
• temp = arr[j];
• arr[j] = arr[j-1];
• arr[j-1] = temp;
• flag = true;
• }
• }
• if(!flag) break;
• }
• }

二. 選擇排序(SelctionSort)

1. 基本思想：

2. 在長度為N的無序數(shù)組中，第一次遍歷n-1個數(shù)，找到最小的數(shù)值與第一個元素交換；
3. 第二次遍歷n-2個數(shù)，找到最小的數(shù)值與第二個元素交換；
4. 。。。
5. 第n-1次遍歷，找到最小的數(shù)值與第n-1個元素交換，排序完成。

6. 過程：

1. 
   
2. 選擇排序

3. 平均時間復(fù)雜度：

   O(n2)

4. java代碼實(shí)現(xiàn)：

5. public static void select_sort(int array[],int lenth){
6. for(int i=0;i<>
7. int minIndex = i;
8. for(int j=i+1;j<>
9. if(array[j]<>
10. minIndex = j;
11. }
12. }
13. if(minIndex != i){
14. int temp = array[i];
15. array[i] = array[minIndex];
16. array[minIndex] = temp;
17. }
18. }
19. }

三. 插入排序(Insertion Sort)

1. 基本思想：

2. 在要排序的一組數(shù)中，假定前n-1個數(shù)已經(jīng)排好序，現(xiàn)在將第n個數(shù)插到前面的有序數(shù)列中，使得這n個數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。

3. 過程：

1. 
   
2. 插入排序

1. 
   
2. 相同的場景

3. 平均時間復(fù)雜度：

   O(n2)

4. java代碼實(shí)現(xiàn)：

5. public static void insert_sort(int array[],int lenth){
6. int temp;
7. for(int i=0;i<>
8. for(int j=i+1;j>0;j--){
9. if(array[j] <>
10. temp = array[j-1];
11. array[j-1] = array[j];
12. array[j] = temp;
13. }else{ //不需要交換
14. break;
15. }
16. }
17. }
18. }

四. 希爾排序(Shell Sort)

1. 前言：

2. 數(shù)據(jù)序列1： 13-17-20-42-28 利用插入排序，13-17-20-28-42. Number of swap:1;
3. 數(shù)據(jù)序列2： 13-17-20-42-14 利用插入排序，13-14-17-20-42. Number of swap:3;
4. 如果數(shù)據(jù)序列基本有序，使用插入排序會更加高效。

5. 基本思想：

6. 在要排序的一組數(shù)中，根據(jù)某一增量分為若干子序列，并對子序列分別進(jìn)行插入排序。
7. 然后逐漸將增量減小,并重復(fù)上述過程。直至增量為1,此時數(shù)據(jù)序列基本有序,最后進(jìn)行插入排序。

8. 過程：

1. 
   
2. 希爾排序

3. 平均時間復(fù)雜度：

4. java代碼實(shí)現(xiàn)：

5. public static void shell_sort(int array[],int lenth){
6. int temp = 0;
7. int incre = lenth;
8. while(true){
9. incre = incre/2;
10. for(int k = 0;k
11. for(int i=k+incre;i<>
12. for(int j=i;j>k;j-=incre){
13. if(array[j]<>
14. temp = array[j-incre];
15. array[j-incre] = array[j];
16. array[j] = temp;
17. }else{
18. break;
19. }
20. }
21. }
22. }
23. if(incre == 1){
24. break;
25. }
26. }
27. }

五. 快速排序(Quicksort)

1. 基本思想：（分治）

• 先從數(shù)列中取出一個數(shù)作為key值；
• 將比這個數(shù)小的數(shù)全部放在它的左邊，大于或等于它的數(shù)全部放在它的右邊；
• 對左右兩個小數(shù)列重復(fù)第二步，直至各區(qū)間只有1個數(shù)。

1. 輔助理解：挖坑填數(shù)

• 初始時 i = 0; j = 9; key=72
• 由于已經(jīng)將a[0]中的數(shù)保存到key中，可以理解成在數(shù)組a[0]上挖了個坑，可以將其它數(shù)據(jù)填充到這來。
• 從j開始向前找一個比key小的數(shù)。當(dāng)j=8，符合條件，

  a[0] = a[8] ; i++ ;

  將a[8]挖出再填到上一個坑a[0]中。
• 這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]，這怎么辦了？簡單，再找數(shù)字來填a[8]這個坑。
• 這次從i開始向后找一個大于key的數(shù)，當(dāng)i=3，符合條件，

  a[8] = a[3] ; j-- ;

  將a[3]挖出再填到上一個坑中。
• 數(shù)組：72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85
• 0 1 2 3 4 5 6 7 8 9
• 此時 i = 3; j = 7; key=72
• 再重復(fù)上面的步驟，先從后向前找，再從前向后找。
• 從j開始向前找，當(dāng)j=5，符合條件，將a[5]挖出填到上一個坑中，

  a[3] = a[5]; i++;

• 從i開始向后找，當(dāng)i=5時，由于i==j退出。
• 此時，i = j = 5，而a[5]剛好又是上次挖的坑，因此將key填入a[5]。
• 數(shù)組：48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85
• 0 1 2 3 4 5 6 7 8 9
• 可以看出a[5]前面的數(shù)字都小于它，a[5]后面的數(shù)字都大于它。因此再對a[0…4]和a[6…9]這二個子區(qū)間重復(fù)上述步驟就可以了。
• <數(shù)組：48 -="" 6="" -="" 57="" -="" 42="" -="" 60="" -="" 72="" -="" 83="" -="" 73="" -="" 88="" -="">
• 0 1 2 3 4 5 6 7 8 9

1. 平均時間復(fù)雜度：

   O(N*logN)

2. 代碼實(shí)現(xiàn)：

3. public static void quickSort(int a[],int l,int r){
4. if(l>=r)
5. return;
6. int i = l; int j = r; int key = a[l];//選擇第一個數(shù)為key
7. while(i<>
8. while(i=key)//從右向左找第一個小于key的值
9. j--;
10. if(i<>
11. a[i] = a[j];
12. i++;
13. }
14. while(i
15. i++;
16. if(i<>
17. a[j] = a[i];
18. j--;
19. }
20. }
21. //i == j
22. a[i] = key;
23. quickSort(a, l, i-1);//遞歸調(diào)用
24. quickSort(a, i+1, r);//遞歸調(diào)用
25. }
26. key值的選取可以有多種形式，例如中間數(shù)或者隨機(jī)數(shù)，分別會對算法的復(fù)雜度產(chǎn)生不同的影響。

六. 歸并排序(Merge Sort)

1. 基本思想：

   參考
2. 歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應(yīng)用。
3. 首先考慮下如何將2個有序數(shù)列合并。這個非常簡單，只要從比較2個數(shù)列的第一個數(shù)，誰小就先取誰，取了后就在對應(yīng)數(shù)列中刪除這個數(shù)。然后再進(jìn)行比較，如果有數(shù)列為空，那直接將另一個數(shù)列的數(shù)據(jù)依次取出即可。
4. //將有序數(shù)組a[]和b[]合并到c[]中
5. void MemeryArray(int a[], int n, int b[], int m, int c[])
6. {
7. int i, j, k;
8. i = j = k = 0;
9. while (i < n="" &&="" j=""><>
10. {
11. if (a[i] <>
12. c[k++] = a[i++];
13. else
14. c[k++] = b[j++];
15. }
16. while (i <>
17. c[k++] = a[i++];
18. while (j <>
19. c[k++] = b[j++];
20. }
21. 解決了上面的合并有序數(shù)列問題，再來看歸并排序，其的基本思路就是將數(shù)組分成2組A，B，如果這2組組內(nèi)的數(shù)據(jù)都是有序的，那么就可以很方便的將這2組數(shù)據(jù)進(jìn)行排序。如何讓這2組組內(nèi)數(shù)據(jù)有序了？
22. 可以將A，B組各自再分成2組。依次類推，當(dāng)分出來的小組只有1個數(shù)據(jù)時，可以認(rèn)為這個小組組內(nèi)已經(jīng)達(dá)到了有序，然后再合并相鄰的2個小組就可以了。這樣通過

    先遞歸的分解數(shù)列

    ，

    再合并數(shù)列

    就完成了歸并排序。

23. 過程：

1. 
   
2. 歸并排序

3. 平均時間復(fù)雜度：

   O(NlogN)
4. 歸并排序的效率是比較高的，設(shè)數(shù)列長為N，將數(shù)列分開成小數(shù)列一共要logN步，每步都是一個合并有序數(shù)列的過程，時間復(fù)雜度可以記為O(N)，故一共為O(N*logN)。

5. 代碼實(shí)現(xiàn)：

6. public static void merge_sort(int a[],int first,int last,int temp[]){
7. if(first <>
8. int middle = (first + last)/2;
9. merge_sort(a,first,middle,temp);//左半部分排好序
10. merge_sort(a,middle+1,last,temp);//右半部分排好序
11. mergeArray(a,first,middle,last,temp); //合并左右部分
12. }
13. }
14. //合并 ：將兩個序列a[first-middle],a[middle+1-end]合并
15. public static void mergeArray(int a[],int first,int middle,int end,int temp[]){
16. int i = first;
17. int m = middle;
18. int j = middle+1;
19. int n = end;
20. int k = 0;
21. while(i<=m &&=""><>
22. if(a[i] <=>
23. temp[k] = a[i];
24. k++;
25. i++;
26. }else{
27. temp[k] = a[j];
28. k++;
29. j++;
30. }
31. }
32. while(i<>
33. temp[k] = a[i];
34. k++;
35. i++;
36. }
37. while(j<>
38. temp[k] = a[j];
39. k++;
40. j++;
41. }
42. for(int ii=0;ii<>
43. a[first + ii] = temp[ii];
44. }
45. }

七. 堆排序(HeapSort)

1. 基本思想：

• 圖示：

  （88,85,83,73,72,60,57,48,42,6）

• 
  
• Heap Sort

1. 平均時間復(fù)雜度：

   O(NlogN)
2. 由于每次重新恢復(fù)堆的時間復(fù)雜度為O(logN)，共N - 1次重新恢復(fù)堆操作，再加上前面建立堆時N / 2次向下調(diào)整，每次調(diào)整時間復(fù)雜度也為O(logN)。二次操作時間相加還是O(N * logN)。

3. java代碼實(shí)現(xiàn)：

4. //構(gòu)建最小堆
5. public static void MakeMinHeap(int a[], int n){
6. for(int i=(n-1)/2 ; i>=0 ; i--){
7. MinHeapFixdown(a,i,n);
8. }
9. }
10. //從i節(jié)點(diǎn)開始調(diào)整,n為節(jié)點(diǎn)總數(shù) 從0開始計算 i節(jié)點(diǎn)的子節(jié)點(diǎn)為 2*i+1, 2*i+2
11. public static void MinHeapFixdown(int a[],int i,int n){
12. int j = 2*i+1; //子節(jié)點(diǎn)
13. int temp = 0;
14. while(j<>
15. //在左右子節(jié)點(diǎn)中尋找最小的
16. if(j+1<>
17. j++;
18. }
19. if(a[i] <=>
20. break;
21. //較大節(jié)點(diǎn)下移
22. temp = a[i];
23. a[i] = a[j];
24. a[j] = temp;
25. i = j;
26. j = 2*i+1;
27. }
28. }
29. public static void MinHeap_Sort(int a[],int n){
30. int temp = 0;
31. MakeMinHeap(a,n);
32. for(int i=n-1;i>0;i--){
33. temp = a[0];
34. a[0] = a[i];
35. a[i] = temp;
36. MinHeapFixdown(a,0,i);
37. }
38. }

八. 基數(shù)排序(RadixSort)

BinSort

1. 基本思想：

2. BinSort想法非常簡單，首先創(chuàng)建數(shù)組A[MaxValue]；然后將每個數(shù)放到相應(yīng)的位置上（例如17放在下標(biāo)17的數(shù)組位置）；最后遍歷數(shù)組，即為排序后的結(jié)果。

3. 圖示：

1. 
   
2. BinSort

• 問題：

  當(dāng)序列中存在較大值時，BinSort 的排序方法會浪費(fèi)大量的空間開銷。

1. RadixSort

2. 基本思想：

   基數(shù)排序是在BinSort的基礎(chǔ)上，通過基數(shù)的限制來減少空間的開銷。

3. 過程：

1. 
   
2. 過程1

1. 
   
2. 過程2
3. （1）首先確定基數(shù)為10，數(shù)組的長度也就是10.每個數(shù)34都會在這10個數(shù)中尋找自己的位置。
4. （2）不同于BinSort會直接將數(shù)34放在數(shù)組的下標(biāo)34處，基數(shù)排序是將34分開為3和4，第一輪排序根據(jù)最末位放在數(shù)組的下標(biāo)4處，第二輪排序根據(jù)倒數(shù)第二位放在數(shù)組的下標(biāo)3處，然后遍歷數(shù)組即可。

5. java代碼實(shí)現(xiàn)：

6. public static void RadixSort(int A[],int temp[],int n,int k,int r,int cnt[]){
7. //A:原數(shù)組
8. //temp:臨時數(shù)組
9. //n:序列的數(shù)字個數(shù)
10. //k:最大的位數(shù)2
11. //r:基數(shù)10
12. //cnt:存儲bin[i]的個數(shù)
13. for(int i=0 , rtok=1; i
14. //初始化
15. for(int j=0;j<>
16. cnt[j] = 0;
17. }
18. //計算每個箱子的數(shù)字個數(shù)
19. for(int j=0;j<>
20. cnt[(A[j]/rtok)%r]++;
21. }
22. //cnt[j]的個數(shù)修改為前j個箱子一共有幾個數(shù)字
23. for(int j=1;j<>
24. cnt[j] = cnt[j-1] + cnt[j];
25. }
26. for(int j = n-1;j>=0;j--){ //重點(diǎn)理解
27. cnt[(A[j]/rtok)%r]--;
28. temp[cnt[(A[j]/rtok)%r]] = A[j];
29. }
30. for(int j=0;j<>
31. A[j] = temp[j];
32. }
33. }
34. }