面試 10：玩轉 Java 選擇排序和插入排序

面試 10：Java 玩轉選擇排序和插入排序

昨天給大家講解了

，大家一定覺得并沒有什麼難度吧，不知道大佬們玩轉了嗎？不知道大家有沒有多加思考，實際上在我們最後的一種思路上，還可以再繼續改進。

我們先看看昨天最終版本的代碼。

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;
        // 定義一個标記 isSort，當其值為 true 的時候代表已經有序。
        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

來判斷是否已經排序完成，當一整趟周遊都沒有發生資料交換的時候，說明已經排序完成，直接 break 退出循環即可。

我們試想一下這樣的場景：假設有 100 個數字的數組，僅僅前 10 個無序，後面 90 個均有序并且都大于前面 10 個數字。

我們采用上面的終極算法可以明顯看到，第一趟排序後，最後發生交換的位置必定大于 10，且這個位置之後的資料必定已經有序了，但我們還是會去做徒勞的 90 次周遊，而且我們還要周遊 10 次！

顯然我們可以找到這樣的思路，在第一次排序後，就記住最後發生交換的位置，第二次隻要從數組頭部周遊到這個位置就 OK 了。

我們不妨直接看看代碼實作：

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);
    }
}

其實算法也就那麼一回事兒，用心去了解它的原理，了解後，無論是用哪種語言實作起來都是非常簡單的。那我們今天就來看看另外兩種排序，選擇排序和插入排序。

選擇排序

選擇排序（Selection sort）是一種簡單直覺的排序算法。選擇排序之是以叫選擇排序就是在一次周遊過程中找到最小元素的角标位置，然後把它放到數組的首端。我們排序過程都是在尋找剩餘數組中的最小元素，是以就叫做選擇排序。

它的思想如下：

從待排序序列中，找到關鍵字最小的元素；起始假定第一個元素為最小
如果最小元素不是待排序序列的第一個元素，将其和第一個元素互換；
從餘下的 N - 1 個元素中，找出關鍵字最小的元素，重複1，2步，直到排序結束。

圖檔來源于網絡

選擇排序的主要優點與資料移動有關。如果某個元素位于正确的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個将被移到其最終位置上，是以對 n 個元素的表進行排序總共進行至多 n - 1 次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬于非常好的一種。

我們來看看用 Java 是怎麼實作的。

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; // 未排序的序列中最小元素的下标
            for (j = i + 1; j < len; j++) {
                //在未排序元素中繼續尋找最小元素，并儲存其下标
                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 代碼可以看出我們除了交換元素并未開辟額外的空間，是以額外的空間複雜度為 O(1)。

對于時間複雜度而言，選擇排序序冒泡排序一樣都需要周遊 n(n-1)/2 次,但是相對于冒泡排序來說每次周遊隻需要交換一次元素，這對于計算機執行來說有一定的優化。但是選擇排序也是名副其實的慢性子，即使是有序數組，也需要進行 n(n-1)/2 次比較，是以其時間複雜度為 O(n²)。

即便無論如何也要進行 n(n-1)/2 次比較，選擇排序仍是不穩定的排序算法，我們舉一個例子如：序列 5 8 5 2 9，我們知道第一趟選擇第 1 個元素 5 會與 2 進行交換，那麼原序列中兩個 5 的相對先後順序也就被破壞了。

選擇排序總結：

選擇排序的算法時間平均複雜度為O(n²)。
選擇排序空間複雜度為 O(1)。
選擇排序為不穩定排序。

插入排序

對于插入排序，大部分資料都是使用撲克牌整理作為例子來引入的，我們打牌都是一張一張摸牌的，每摸到一張牌就會跟手裡所有的牌比較來選擇合适的位置插入這張牌，這也就是直接插入排序的中心思想，我們先來看下動圖：

相信大家看完動圖以後大概知道了插入排序的實作思路了。那麼我們就來說下插入排序的思想。

插入排序的思想

從第一個元素開始，該元素可以認為已經被排序
取出下一個元素，在已經排序的元素序列中從後向前掃描
如果該元素（已排序）大于新元素，将該元素移到下一位置
重複步驟 3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到該位置後
重複步驟 2~5

了解上述思想其實并不難，我們來看看用 Java 怎麼實作：

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++) {
            // 設定哨兵，拿出待插入的值
            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);
    }
}

插入排序的時間複雜度和空間複雜度分析

對于插入的時間複雜度和空間複雜度，通過代碼就可以看出跟選擇和冒泡來說沒什麼差別同屬于 O(n²) 級别的時間複雜度算法，隻是周遊方式有原來的 n n-1 n-2 ... 1，變成了 1 2 3 ... n 了。最終得到時間複雜度都是 n(n-1)/2。

對于穩定性來說，插入排序和冒泡一樣，并不會改變原有的元素之間的順序，如果遇見一個與插入元素相等的，那麼把待插入的元素放在相等元素的後面。是以，相等元素的前後順序沒有改變，從原無序序列出去的順序仍是排好序後的順序，是以插入排序是穩定的。

對于插入排序這裡說一個非常重要的一點就是：由于這個算法可以提前終止内層比較（ arr[j-1] > arr[j]）是以這個排序算法很有用！是以對于一些 NlogN 級别的算法，後邊的歸并和快速都屬于這個級别的，算法來說對于 n 小于一定級别的時候（Array.sort 中使用的是47）都可以用插入算法來優化,另外對于近乎有序的數組來說這個提前終止的方式就顯得更加又有優勢了。

插入排序總結：

插入排序的算法時間平均複雜度為O(n²)。
插入排序空間複雜度為 O(1)。
插入排序為穩定排序。
插入排序對于近乎有序的數組來說效率更高，插入排序可用來優化進階排序算法

到現在，我們的三種簡單排序就告一段落了，下面我們将直接進入歸并排序和快速排序的講解。這兩個算法也是面試上的常客了，是以你準備好了麼？

文章參考來源：

https://juejin.im/post/5a96d6b15188255efc5f8bbd

面試 10：玩轉 Java 選擇排序和插入排序

面試 10：Java 玩轉選擇排序和插入排序

選擇排序

插入排序

插入排序的思想

插入排序的時間複雜度和空間複雜度分析

繼續閱讀

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希