演算法 - 選擇排序和冒泡排序

今天講一下選擇排序和冒泡排序，這是兩種很簡單的排序演算法。

一、冒泡排序法（BubbleSort）

從數組的第一個元素開始，進行兩兩比較，較大的移到前面，較小的移到後面，經過一輪比較後，最大的數將會被移動到最後面。

最無腦版本：

public int[] bubbleSort(int[] arr){ for(int i = 0; i < arr.length; i++){ for(int j = 0;j < arr.length-1; j++){ if(arr[j] > arr[j+1]){ int temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } //列印數組，查看排序過程 /*for (int ii : arr) { System.out.print(ii+"->"); } System.out.println("");*/ } return arr;}

去掉注釋代碼，程序輸出：

5->2->7->3->8->1->6->9

2->5->3->7->1->6->8->9

2->3->5->1->6->7->8->9

2->3->1->5->6->7->8->9

2->1->3->5->6->7->8->9

1->2->3->5->6->7->8->9

1->2->3->5->6->7->8->9

1->2->3->5->6->7->8->9

這個版本有兩個大問題：

1. 假設我們把每次內循環完成稱為「一輪」，每一輪過後，數組arr的最後一位元素已經是最大的了，而我們還是把它進行了比較，所以內層循環的「上限」需要修改。
2. 通過上面輸出我們可以發現，最後三輪比較沒有交換任何元素，也就是說已經排序完成，可是我們的程序還是在「傻傻的」運行，所以我們應該設置一個flag，當檢測到數組排好序後，終止程序。

修改版：

public int[] bubbleSort(int[] arr){ boolean swapNone; for(int i = 0; i < arr.length; i++){ swapNone = true; //初始化flag for(int j = 0;j < arr.length-1-i; j++){ //這裡注意是j < arr.length-1-i if(arr[j] > arr[j+1]){ int temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; swapNone = false;//記錄交換 } } //如果無交換，結束 if(swapNone)break; //列印數組，查看排序過程 /*for (int ii : arr) { System.out.print(ii+"->"); } System.out.println("");*/ } return arr;}

去掉注釋代碼，程序輸出：

5->2->7->3->8->1->6->9

2->5->3->7->1->6->8->9

2->3->5->1->6->7->8->9

2->3->1->5->6->7->8->9

2->1->3->5->6->7->8->9

1->2->3->5->6->7->8->9

完美！

那麼，冒泡排序的時間複雜度是O（n^2），空間複雜度是O（1）。

一般來說，冒泡排序是穩定的排序演算法，但是如果比較條件中 arr[j]<arr[j+1]的「<」改為「<=」，那麼冒泡排序就不穩定了。關於穩定性分析，我會在其他文章講到。

二、選擇排序法（SelectionSort）

選擇排序的思路，和人類的思維是很相似的：先找出最小的來，放在第一位；然後再找出第二小的，放到第二位；再找出第三小的，以此類推。

代碼如下：

public int[] selectionSort(int[] arr){ for(int i = 0; i < arr.length; i++){ //第i輪查找，找出第i小的，放到第i位 int minIndex = i; //從i+1開始和第i個進行比較 for(int j = i+1; j < arr.length-1; j++){ //n個數共需要比較n-1次，最大的數自動被「擠」到最後 if(arr[j] < arr[minIndex]){ minIndex = j; } } if(minIndex != i){ int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } //列印數組，查看排序過程 /*for (int ii : arr) { System.out.print(ii+"->"); } System.out.println("");*/ } return arr; }

去掉注釋代碼，程序輸出：

1->5->2->7->3->8->9->6

1->2->5->7->3->8->9->6

1->2->3->7->5->8->9->6

1->2->3->5->7->8->9->6

1->2->3->5->6->8->9->7

1->2->3->5->6->7->9->8

1->2->3->5->6->7->8->9

完美！

那麼，選擇排序的時間複雜度是O（n^2），空間複雜度是O（1）。

穩定性不敢講，有大佬知道的，可以在評論區告訴我。大家也可以自行百度~~~