相關文章：

• 排序（二）：分而治之——快速排序 && 歸并排序

• 排序（三）：誰主沉浮——堆與堆排序

leetcode：https://leetcode-cn.com/problems/sort-an-array/

插入排序

程序

插入排序的程序分為兩步：

• 首先和當前位置的前一個元素進行比較，如果前一個元素比當前元素大，則后續進行調整，將前面的大元素不斷向后移動，并找到合適的位置將當前元素插入進去；
• 如果發現前一個元素比當前元素小，則不會進行調整，默認前面的元素已經有序，

示意圖如下：

插入排序的特點是：基于比較、資料移動完成排序，一次比較操作后不發生資料移動或僅僅交換一對相鄰的資料元素，

代碼

class Solution {
    public int[] sortArray(int[] nums) {
        int i,j;
        for(i = 1; i < nums.length; i++){
            if(nums[i] < nums[i-1]){
                int temp = nums[i];
                nums[i] = nums[i-1];
                for(j = i-2; j >= 0 && nums[j] > temp; j--){
                    nums[j+1] = nums[j];
                }
                nums[j+1] = temp;
            }
        }
        return nums;
    }
}

時間復雜度

逆序：對于數對 ( π ( i ) , π ( j ) ) (\pi(i), \pi(j)) (π(i),π(j)) ，有 j < j j < j j<j 而 π ( i ) > π ( j ) \pi(i)>\pi(j) π(i)>π(j) ，

插入排序的實質是消除數對的逆序，一個含有 n 個元素的序列有 n ( n ? 1 ) 2 \frac{n(n-1)}{2} 2n(n?1)? 個數對，則最多有 n ( n ? 1 ) 2 \frac{n(n-1)}{2} 2n(n?1)? 個逆序，平均有 n ( n ? 1 ) 4 \frac{n(n-1)}{4} 4n(n?1)? 個逆序，而插入排序在一次數對比較之后最后消除一對逆序，

基于此，分析插入排序的最好情況 B ( n ) B(n) B(n)，平均情況 A ( n ) A(n) A(n) 和最壞情況 W ( n ) W(n) W(n)，

• 最好情況：元素升序有序，那么我們只需要進行 n-1 次元素比較，0 次元素移動即可， B ( n ) ∈ O ( n ) B(n) \in O(n) B(n)∈O(n)，
• 最壞情況：元素降序有序，那么我們需要進行 n ( n ? 1 ) 2 \frac{n(n-1)}{2} 2n(n?1)? 次元素比較，同樣次數的元素移動， W ( n ) ∈ O ( n 2 ) W(n) \displaystyle \in O(n^2) W(n)∈O(n2)，
• 平均時間復雜度：平均比較 n ( n ? 1 ) 4 \frac{n(n-1)}{4} 4n(n?1)? 次， A ( n ) ∈ O ( n 2 ) A(n) \displaystyle \in O(n^2) A(n)∈O(n2)，

代碼優化

定理：任何一個基于關鍵字的比較且每一次比較最多消除一個逆序的排序演算法，最壞的情況下至少比較 n ( n ? 1 ) 2 \frac{n(n-1)}{2} 2n(n?1)? 次，平均情況至少比較 n ( n ? 1 ) 4 \frac{n(n-1)}{4} 4n(n?1)? 次，無法從 O ( n 2 ) O(n^2) O(n2) 的復雜度降低，

冒泡排序

程序

• 將待排序的資料元素的關鍵字順次兩兩比較，若為逆序則將兩個資料元素交換
• 將待排序的資料元素照此方法從頭到尾處理一遍稱作一趟起泡排序，它將關鍵字值最大的資料元素交換到排序的最終位置，
• 對含 n 個記錄的檔案排序最多需要 n-1 趟冒泡排序，
  

代碼

class Solution {
    public int[] sortArray(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < nums.length-i-1; j++){
                if(nums[j] > nums[j+1]){
                    int temp = nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        return nums;
    }
}

時間復雜度

• 最壞情況：序列是逆序，需要比較的次數為 n(n-1)/2，則對應時間復雜度為 W ( n ) ∈ O ( n 2 ) W(n) \displaystyle \in O(n^2) W(n)∈O(n2) ，
• 最好情況：序列已經是升序有序序列，則進行一次比較即可，第一次比較發現沒有發生資料移動，則排序結束，比較次數為 n - 1 次，則時間復雜度為 B ( n ) ∈ O ( n 2 ) ) B(n) \displaystyle \in O(n^2)) B(n)∈O(n2)) ，
• 平均情況： A ( n ) ∈ O ( n 2 ) ) A(n) \displaystyle \in O(n^2)) A(n)∈O(n2))

代碼優化

優化1：記下最后一次交換的位置，后邊沒有交換，必然是有序的，然后下一次排序從第一個比較到上次記錄的位置結束即可，同時引入布爾變數 sorted 作為標記，如果在一趟排序中沒有交換元素，說明這組資料已經有序，不用再繼續下去，

class Solution {
    public int[] sortArray(int[] nums) {
        int temp = 0;
        int LastExchangeIndex = 0;  //上一次交換位置
        int border = nums.length-1;  //無序串列邊界
        
        for(int i = 0; i < nums.length; i++){
            boolean sorted = true;
            for(int j = 0; j < border; j++){
                if(nums[j] > nums[j+1]){
                    temp = nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = temp;
                    LastExchangeIndex = j;
                    sorted = false;
                }
            }
            if(sorted)
                break;
            border = LastExchangeIndex;
        }
        return nums;
    }
}

優化2：雙邊界冒泡排序，見《計算機演算法——設計與分析導論》習題4.5，以序列(2,3,4,5,1) 為例，在普通冒泡排序下，需要盲目比較左側有序子列，引入左側邊界解決這一問題：找到首個交換位置 pos，則下一趟冒泡排序的起始位置 border_left = pos - 1 or 0，

class Solution {
    public int[] sortArray(int[] nums) {        
        //雙邊界冒泡排序
        int FirstExchangeIndex = 0;
        int LastExchangeIndex = 0;
        int border_left = 0;
        int border_right = nums.length - 1;
        for(int i = 0; i < nums.length; i++){
            boolean sorted_left = true;
            boolean sorted = true;
            for(int j = border_left; j < border_right; j++){
                if(nums[j] > nums[j+1]){
                    //記錄首個交換的位置
                    if(sorted_left){
                        border_left = j-1 >= 0 ? j-1:0;  //左邊界更新
                        sorted_left = false;
                    }
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                    sorted = false;
                    LastExchangeIndex = j;
                }
            }
            if(sorted)
                break;
            border_right = LastExchangeIndex;
        }
        return nums;
    }
}        

優化3：雞尾酒排序，又稱雙向冒泡排序、攪拌排序，排序程序像鐘擺一樣，奇數輪從左到右，偶數輪從右到左，示意圖如下：

雞尾酒排序適用于基本有序的序列，還以序列(2,3,4,5,1)為例，雞尾酒排序只需要訪問一次序列就可以完成排序，但如果使用冒泡排序則需要四次，在亂數序列的狀態下，雞尾酒排序與冒泡排序的效率相當（都為 O ( n 2 ) O(n^2) O(n2) ），缺點是代碼量較大，

• 最差時間復雜度 O ( n 2 ) O(n^2) O(n2)
• 最優時間復雜度 O ( n ) O(n) O(n)
• 平均時間復雜度 O ( n 2 ) O(n^2) O(n2)

class Solution {
    public int[] sortArray(int[] nums) {
        int border_right = nums.length - 1;
        int border_left = 0;
        int LastExchangeIndex_right = 0;
        int LastExchangeIndex_left = 0;
        
        for(int i = 0; i < nums.length/2; i++){
            //正向
            boolean sorted = true;
            for(int j = 0; j < border_right; j++){
                if(nums[j] > nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                    LastExchangeIndex_right = j;
                    sorted = false;
                }
            }
            if(sorted)
                break;
            border_right = LastExchangeIndex_right;

            //反向
            sorted = true;
            for(int j = nums.length-1-i; j > border_left; j--){
                if(nums[j] < nums[j-1]){
                    int temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp;
                    LastExchangeIndex_left = j;
                    sorted = false;
                }
            }
            if(sorted)
                break;
            border_left = LastExchangeIndex_left;
        }
        return nums;
    }
}