lyndoo

冒泡排序（Bubble Sort）

平均時間復雜度：O(N^2)

最好時間復雜度：O(N)

最壞時間復雜度：O(N^2)

空間復雜度：O(1)

• 冒泡排序是一種計算機科學領域的較簡單的排序算法。
• 它重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。
• 走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素列已經排序完成。
• 這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

void bubbleSort(int[] array) {
    int temp;
    for (int i = 0; i < array.length - 1; i++) {//從第0個元素開始，循環數組元素個數-1次
        for (int j = 0; j < array.length - 1 - i; j++) {
            //每次都和之后的一個元素進行對比
            if (array[j] > array[j + 1]) {
                //如果當前元素大于之后的元素，則交換兩個元素
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        //每輪結束數組剩余數中的最大（最小）的數已經交換到 array.length - i 的索引處
        //第一輪是:  array.length - 0
        //第二輪是:  array.length - 1
        //.....
    }
}

如果某一次循環中，一次也沒有交換數據，則說明該數組已經是一個有序數組

優化代碼：

void bubbleSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {//從第0個元素開始，循環數組元素個數-1次
    	boolean flag = false;
        for (int j = 0; j < array.length - 1 - i; j++) {
            //每次都和之后的一個元素進行對比
            if (array[j] > array[j + 1]) {
                //如果當前元素大于之后的元素，則交換兩個元素
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                
                flag = true;
            }
        }
        //每輪結束數組剩余數中的最大（最小）的數已經交換到 array.length - i 的索引處
        //第一輪是:  array.length - 0
        //第二輪是:  array.length - 1
        //.....
        
        if (!flag) {
            break;//如果當前循環沒有交換任意兩個元素，則說明排序已完成，可以直接結束
        }
    }
}

選擇排序（Selection sort）

平均時間復雜度：O(N^2)

最好時間復雜度：O(N^2)

最壞時間復雜度：O(N^2)

空間復雜度：O(1)

• 選擇排序是一種簡單直觀的排序算法。它的工作原理是：
• 第一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。
• 以此類推，直到全部待排序的數據元素的個數為零。選擇排序是不穩定的排序方法。

void selectSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {//從第0個元素開始
        int index = i;
        int num = array[i];
        for (int j = i + 1; j < array.length; j++) {
            //每次都和之后所有的數組元素進行對比
            if (array[j] < num) { 
                //如果當前對比的元素大于之前的元素，則把當前元素的值替換之前的元素值，進行下一輪的比較
                //直至找到數組剩余數據中最小的值
                num = array[j];
                index = j;
            }
        }

        //找到最小的元素值位置，進行交換
        int temp = array[i];
        array[i] = array[index];
        array[index] = temp;
    }
}

插入排序

平均時間復雜度：O(N^2)

最好時間復雜度：O(N)

最壞時間復雜度：O(N^2)

空間復雜度：O(1)

• 一般也被稱為直接插入排序。對于少量元素的排序，它是一個有效的算法

• 插入排序是一種最簡單的排序方法，它的基本思想是將一個記錄插入到已經排好序的有序表中，從而一個新的、記錄數增1的有序表。

• 在其實現過程使用雙層循環，外層循環對除了第一個元素之外的所有元素，內層循環對當前元素前面有序表進行待插入位置查找，并進行移動

• 形象的比喻就是打撲克牌的時候發牌階段，從第二張牌開始就和之前發的牌比較，找到合適的位置，插入。之后的牌則依次后移。

//從第1個元素開始循環，第0個元素默認是有序數組
for (int i = 1; i < array.length; i++) {
    int num = array[i];
    int index = i - 1;
    while (index >= 0 && num < array[index]) {
        //和之前的有序表進行比較，如果大于之前的元素，則前一個元素向后進行移位，直到找到合適的位置結束
        array[index + 1] = array[index];
        index--;
    }
    array[index + 1] = num;//把當前元素插入到找到的位置的后一位
}

時間統計

int[] 數組長度：10000 十次排序：

冒泡排序 最短104ms 最長167ms 平均126.4ms
選擇排序 最短13ms 最長43ms 平均30.4ms
插入排序 最短11ms 最長18ms 平均12.4ms

int[] 數組長度：50000 十次排序：

冒泡排序 最短3498ms 最長3661ms 平均3573.9ms
選擇排序 最短365ms 最長408ms 平均373.2ms
插入排序 最短288ms 最長303ms 平均292.8ms

int[] 數組長度：100000 十次排序：

冒泡排序 最短14463ms 最長14596ms 平均14502.1ms
選擇排序 最短1410ms 最長1441ms 平均1417.4ms
插入排序 最短1162ms 最長1181ms 平均1168.0ms