冒泡排序

    public static int[] sortArray(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true; // 優(yōu)化，標記是否有數(shù)據(jù)交換
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false; // 數(shù)據(jù)交換了
                }
            }
            if (flag) {
                break; // 如果沒有數(shù)據(jù)交換說明數(shù)組已經(jīng)是有序的了梧乘，提前退出
            }
        }
        return arr;
    }

• 思路
  • 對長度為n的數(shù)組遍歷n次澎迎，每次遍歷依次比較相鄰的兩個元素，如果大小關系不符合要求，就交換它倆的位置夹供。這樣每次遍歷都能保證至少一個元素移動到了它應該在的位置辑莫。
  • 注意：以從小到大排序為例，第一次循環(huán)后數(shù)組末尾位置的元素就是最大值罩引，第二次倒數(shù)第二位的元素也是第二大的各吨，依次類推...所以代碼中內(nèi)層循環(huán)的界限是在一直縮小的。
  • 優(yōu)化：用一個flag標記當次循環(huán)中是否有元素進行了交換袁铐。如果沒有任何元素發(fā)生了交換揭蜒，則證明數(shù)組已經(jīng)是有序的了，可以直接跳出循環(huán)剔桨，結束排序屉更。
• 分析
  • 穩(wěn)定性：相鄰元素大小相等時不做交換，所以不會改變大小相等的元素的順序洒缀，是穩(wěn)定的排序算法瑰谜。
  • 空間復雜度：O(1)，只在交換數(shù)據(jù)時需要一塊常數(shù)級的臨時空間树绩，是原地排序算法萨脑。
  • 時間復雜度：最好的情況，數(shù)組本來就是有序的饺饭，時間復雜度為O(n)渤早。最壞的情況，數(shù)組是倒序的瘫俊，需要n次冒泡鹊杖，時間復雜度為O(n2)。經(jīng)過不嚴格的簡單推導扛芽，平均時間復雜度還是O(n2)骂蓖。

插入排序

    public static int[] sortArray(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int value = arr[i]; // 記錄此次循環(huán)要插入的元素
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > value) {
                    arr[j + 1] = arr[j]; // 如果已排序的元素沒有待插入元素大，就向后挪一位
                } else {
                    break; // 找到插入位置川尖，結束循環(huán)
                }
            }
            arr[j + 1] = value; // 將元素插入找到的位置
        }
        return arr;
    }

• 思路
  • 將數(shù)組分為兩個區(qū)間登下，已排序和未排序。已排序區(qū)間最開始就有一個元素空厌，也就是數(shù)組的第一個元素庐船。然后取未排序區(qū)間的元素，在已排序區(qū)間中找到自己的位置嘲更，插進去。直到未排序區(qū)間為空揩瞪。
  • 代碼中赋朦，以從小到大排序為例，下標i前的元素為已排序元素，i及i之后的元素為未排序元素宠哄。每次取一個未排序的元素壹将，倒著去比較已排序元素，如果發(fā)現(xiàn)比某個元素小毛嫉，就插在這個元素之前诽俯。
• 分析
  • 穩(wěn)定性：比較插入時，如果元素相等承粤，可以將未排序的元素插在已排序的元素后邊暴区，可以做到保持原有順序不變，是穩(wěn)定的排序算法辛臊。
  • 空間復雜度：O(1)仙粱，不需要額外的存儲空間，是原地排序算法彻舰。
  • 時間復雜度：最好的情況伐割，數(shù)組本來就是有序的，如果從尾到頭遍歷有序部分刃唤，查找插入位置隔心，每次循環(huán)只需要比較一次就能確定，時間復雜度為O(n)尚胞。最壞的情況济炎，數(shù)組是倒序的，每次查找都要把元素插在有序部分的開頭辐真，需要多次移動元素须尚，時間復雜度為O(n2)。往數(shù)組中插入一個數(shù)據(jù)的平均時間復雜度是O(n)侍咱，我們相當于循環(huán)n次執(zhí)行插入操作耐床，所以平均時間復雜度為O(n2)。

冒泡排序 vs 插入排序

• 它們的穩(wěn)定性和時間楔脯、空間復雜度都相同撩轰，但如果要追求極致，可以發(fā)現(xiàn)冒泡排序在交換元素時需要3個賦值操作昧廷，而插入排序只需要一個堪嫂。當數(shù)據(jù)量很大的時候這點微小的差距累積起來就可以讓插入排序勝過冒泡排序。
• 插入排序的優(yōu)化：參考 五分鐘學會一個高難度算法：希爾排序

選擇排序

• 思路
  • 類似插入排序木柬，以從小到大排序為例皆串，每次遍歷找到未排序部分的最小值放在已排序部分的末尾。
• 分析
  • 穩(wěn)定性：具體實現(xiàn)時會將最小值元素與要放在已排序部分末尾那個位置的元素交換位置眉枕。經(jīng)過多次交換后會破壞穩(wěn)定性恶复。
  • 空間復雜度時間復雜度與冒泡排序和插入排序是一樣的怜森。