面試 10：Java 玩轉(zhuǎn)選擇排序和插入排序
昨天給大家講解了 Java 玩轉(zhuǎn)冒泡排序，大家一定覺得并沒有什么難度吧，不知道大佬們玩轉(zhuǎn)了嗎？不知道大家有沒有多加思考，實際上在我們最后的一種思路上，還可以再繼續(xù)改進(jìn)。
我們先看看昨天最終版本的代碼。
public class Test09 {
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void printArr(int[] arr) {
for (int anArr : arr) {
System.out.print(anArr + " ");
}
}
private static void bubbleSort(int[] arr) {
if (arr == null)
return;
// 定義一個標(biāo)記 isSort，當(dāng)其值為 true 的時候代表已經(jīng)有序。
boolean isSort;
for (int i = 0; i < arr.length - 1; i++) {
isSort = true;
for (int j = 1; j < arr.length - i; j++) {
if (arr[j - 1] > arr[j]) {
swap(arr, j - 1, j);
isSort = false;
}
}
if (isSort)
break;
}
}
public static void main(String[] args) {
int[] arr = {6, 4, 2, 1, 8, 3, 7, 9, 5};
bubbleSort(arr);
printArr(arr);
}
}
我們用一個 boolean 變量 isSort 來判斷是否已經(jīng)排序完成，當(dāng)一整趟遍歷都沒有發(fā)生數(shù)據(jù)交換的時候，說明已經(jīng)排序完成，直接 break 退出循環(huán)即可。
我們試想一下這樣的場景：假設(shè)有 100 個數(shù)字的數(shù)組，僅僅前 10 個無序，后面 90 個均有序并且都大于前面 10 個數(shù)字。
我們采用上面的終極算法可以明顯看到，第一趟排序后，最后發(fā)生交換的位置必定大于 10，且這個位置之后的數(shù)據(jù)必定已經(jīng)有序了，但我們還是會去做徒勞的 90 次遍歷，而且我們還要遍歷 10 次！
顯然我們可以找到這樣的思路，在第一次排序后，就記住最后發(fā)生交換的位置，第二次只要從數(shù)組頭部遍歷到這個位置就 OK 了。
我們不妨直接看看代碼實現(xiàn)：
public class Test09 {
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void printArr(int[] arr) {
for (int anArr : arr) {
System.out.print(anArr + " ");
}
}
private static void bubbleSort(int[] arr) {
if (arr == null)
return;
int flag = arr.length;
int k;
for (int i = 0; i < arr.length - 1; i++) {
k = flag;
flag = 0;
for (int j = 1; j < k; j++) {
if (arr[j - 1] > arr[j]) {
swap(arr, j - 1, j);
flag = j;
}
}
if (flag == 0)
break;
}
}
public static void main(String[] args) {
int[] arr = {6, 4, 1, 2, 3, 5, 7, 8, 9};
bubbleSort(arr);
printArr(arr);
}
}
其實算法也就那么一回事兒，用心去理解它的原理，理解后，無論是用哪種語言實現(xiàn)起來都是非常簡單的。那我們今天就來看看另外兩種排序，選擇排序和插入排序。
選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序算法。選擇排序之所以叫選擇排序就是在一次遍歷過程中找到最小元素的角標(biāo)位置，然后把它放到數(shù)組的首端。我們排序過程都是在尋找剩余數(shù)組中的最小元素，所以就叫做選擇排序。
它的思想如下：
- 從待排序序列中，找到關(guān)鍵字最小的元素；起始假定第一個元素為最小
- 如果最小元素不是待排序序列的第一個元素，將其和第一個元素互換；
- 從余下的 N - 1 個元素中，找出關(guān)鍵字最小的元素，重復(fù)1，2步，直到排序結(jié)束。
選擇排序的主要優(yōu)點與數(shù)據(jù)移動有關(guān)。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當(dāng)中至少有一個將被移到其最終位置上，因此對 n 個元素的表進(jìn)行排序總共進(jìn)行至多 n - 1 次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。
我們來看看用 Java 是怎么實現(xiàn)的。
public class Test09 {
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void printArr(int[] arr) {
for (int anArr : arr) {
System.out.print(anArr + " ");
}
}
private static void selectSort(int[] arr) {
if (arr == null)
return;
int i, j, min, len = arr.length;
for (i = 0; i < len - 1; i++) {
min = i; // 未排序的序列中最小元素的下標(biāo)
for (j = i + 1; j < len; j++) {
//在未排序元素中繼續(xù)尋找最小元素，并保存其下標(biāo)
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i)
swap(arr, min, i);
}
}
public static void main(String[] args) {
int[] arr = {6, 4, 2, 1, 8, 3, 7, 9, 5};
selectSort(arr);
printArr(arr);
}
}
上述 java 代碼可以看出我們除了交換元素并未開辟額外的空間，所以額外的空間復(fù)雜度為 O(1)。
對于時間復(fù)雜度而言，選擇排序序冒泡排序一樣都需要遍歷 n(n-1)/2 次,但是相對于冒泡排序來說每次遍歷只需要交換一次元素，這對于計算機(jī)執(zhí)行來說有一定的優(yōu)化。但是選擇排序也是名副其實的慢性子，即使是有序數(shù)組，也需要進(jìn)行 n(n-1)/2 次比較，所以其時間復(fù)雜度為 O(n2)。
即便無論如何也要進(jìn)行 n(n-1)/2 次比較，選擇排序仍是不穩(wěn)定的排序算法，我們舉一個例子如：序列 5 8 5 2 9， 我們知道第一趟選擇第 1 個元素 5 會與 2 進(jìn)行交換，那么原序列中兩個 5 的相對先后順序也就被破壞了。
選擇排序總結(jié)：
- 選擇排序的算法時間平均復(fù)雜度為O(n2)。
- 選擇排序空間復(fù)雜度為 O(1)。
- 選擇排序為不穩(wěn)定排序。
插入排序
對于插入排序，大部分資料都是使用撲克牌整理作為例子來引入的，我們打牌都是一張一張摸牌的，每摸到一張牌就會跟手里所有的牌比較來選擇合適的位置插入這張牌，這也就是直接插入排序的中心思想，我們先來看下動圖：
相信大家看完動圖以后大概知道了插入排序的實現(xiàn)思路了。那么我們就來說下插入排序的思想。
插入排序的思想
- 從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復(fù)步驟 3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復(fù)步驟 2~5
理解上述思想其實并不難，我們來看看用 Java 怎么實現(xiàn)：
public class Test09 {
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void printArr(int[] arr) {
for (int anArr : arr) {
System.out.print(anArr + " ");
}
}
private static void insertionSort(int[] arr) {
if (arr == null)
return;
int j;
int temp;
for (int i = 1; i < arr.length; i++) {
// 設(shè)置哨兵，拿出待插入的值
temp = arr[i];
j = i;
// 然后尋找正確插入的位置
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
}
public static void main(String[] args) {
int[] arr = {6, 4, 2, 1, 8, 3, 7, 9, 5};
insertionSort(arr);
printArr(arr);
}
}
插入排序的時間復(fù)雜度和空間復(fù)雜度分析
對于插入的時間復(fù)雜度和空間復(fù)雜度，通過代碼就可以看出跟選擇和冒泡來說沒什么區(qū)別同屬于 O(n2) 級別的時間復(fù)雜度算法 ，只是遍歷方式有原來的 n n-1 n-2 ... 1，變成了 1 2 3 ... n 了。最終得到時間復(fù)雜度都是 n(n-1)/2。
對于穩(wěn)定性來說，插入排序和冒泡一樣，并不會改變原有的元素之間的順序，如果遇見一個與插入元素相等的，那么把待插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序仍是排好序后的順序，所以插入排序是穩(wěn)定的。
對于插入排序這里說一個非常重要的一點就是：由于這個算法可以提前終止內(nèi)層比較（ arr[j-1] > arr[j]）所以這個排序算法很有用！因此對于一些 NlogN 級別的算法，后邊的歸并和快速都屬于這個級別的，算法來說對于 n 小于一定級別的時候（Array.sort 中使用的是47）都可以用插入算法來優(yōu)化,另外對于近乎有序的數(shù)組來說這個提前終止的方式就顯得更加又有優(yōu)勢了。
插入排序總結(jié)：
- 插入排序的算法時間平均復(fù)雜度為O(n2)。
- 插入排序空間復(fù)雜度為 O(1)。
- 插入排序為穩(wěn)定排序。
- 插入排序?qū)τ诮跤行虻臄?shù)組來說效率更高，插入排序可用來優(yōu)化高級排序算法
到現(xiàn)在，我們的三種簡單排序就告一段落了，下面我們將直接進(jìn)入 歸并排序 和 快速排序 的講解。這兩個算法也是面試上的?？土?，所以你準(zhǔn)備好了么？
