1、7種常見排序演算法

7種常見排序演算法的時間復雜度、輔助空間以及穩定性對照表，

1.1、冒泡排序

原理： 最簡單的一種排序演算法，假設長度為n的陣列arr，要按照從小到大的排序，則冒泡排序的具體程序可以描述為：首先從陣列的第一個元素開始到陣列的最后一個元素為止，對陣列中相鄰的兩個元素進行比較，如果相鄰兩個元素中左邊的元素大于右邊的元素，則交換兩個元素的位置，此時陣列最右端的元素即為該陣列中所有元素的最大值，接著對該陣列剩下的（n-1）個元素進行冒泡排序，直到整個陣列有序排列，

時間復雜度： O(n^2)，

動態直觀圖：

代碼實作：

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3,78,34,50,89,1,45,7};
        System.out.println("排序之前：" + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("排序之后：" + Arrays.toString(arr));
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        for(int i = arr.length - 1; i >= 0; i--){
            for(int j = 0; j < i; j++){
                if(arr[j] > arr[j + 1]){
                    int tem = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tem;
                }
            }
        }
    }
}

結果：

排序之前：[3, 78, 34, 50, 89, 1, 45, 7]
排序之后：[1, 3, 7, 34, 45, 50, 78, 89]

1.2、簡單選擇排序

**原理：**在嚴蔚敏版本的《資料結構》中對選擇排序的基本描述為：每一輪在n-i+1(i1,2,…,n-1)個記錄中選擇關鍵字最小的記錄作為有序序列中第 i個記錄，假設長度為n的陣列arr，要按照從小到大排序，那么先從n個數字中找到最小值min1，如果最小值min1的位置不在陣列的最左端（也就是min1不等于arr[0]），則將最小值arr[0] = min1，接著在剩下的(n-1)個數字中找到最小值min2，如果最小值min2不等于arr[1]，那么則arr[1] = min2，依次類推，知道陣列arr有序排列，

時間復雜度： O(n^2)，

直觀圖解：

代碼實作：

import java.util.Arrays;

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3,78,34,50,89,1,45,7};
        System.out.println("排序之前：" + Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序之后：" + Arrays.toString(arr));
    }

    /**
     * 簡單選擇排序
     * @param arr
     */
    static void selectSort(int[] arr){
        for(int i=0;i<arr.length; i++){
            int index = i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[index] > arr[j]){
                    index = j;
                }
            }

            if(index == i){
                continue;
            } else {
                int tem = arr[index];
                arr[index] = arr[i];
                arr[i] = tem;
            }
        }
    }
    
}

結果：

排序之前：[3, 78, 34, 50, 89, 1, 45, 7]
排序之后：[1, 3, 7, 34, 45, 50, 78, 89]

1.3、直接插入排序

原理： 插入排序的基本思想就是將無序序列插入到有序序列中，例如：將陣列arr=[4,2,8,0,5,1]排序，可以將4看做是一個有序序列（圖中用藍色標出），將[2,8,0,5,1]看做是一個無序序列，無序序列中2比4小，于是將2插入到4的左邊，于是將2插入到4的左邊，此時有序序列變成了[2,4]，無序序列變成了[8,0,5,1]，無序序列中8比4大，所以將8插入到4的右邊，有序序列變成了[2,4,8]，無序序列變成了[0,5,1]，依次類推最終陣列按照從小到大的排序，

時間復雜度： O(n^2)，

直觀圖：


代碼實作：

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{4,2,8,0,5,1};
        System.out.println("排序之前：" + Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序之后：" + Arrays.toString(arr));
    }

    static void insertSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            //如果陣列長度小于1直接回傳
            if(arr.length<2)
                return;
            
            //就是j之前的元素都看做是一個有序序列
            for(int j=i;j>0;j--){
                if(arr[j] < arr[j-1]){
                    int tem = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tem;
                }
            }

        }
    }
}

結果：

排序之前：[4, 2, 8, 0, 5, 1]
排序之后：[0, 1, 2, 4, 5, 8]

1.4、希爾排序

待續……

1.5、歸并排序

待續……

1.6、快速排序

原理： 快速怕排序的基本思想是：通過一次排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序，

實際上： 快速排序 = 冒泡 + 分治 + 遞回，

一趟快速排序的具體程序可描述為： 從待排序列中任意取出一個記錄（通常選取第一個記錄）作為基準值，然后將記錄中比它小的記錄都安置在它的位置之前，將記錄中關鍵字比它大的記錄都安置在它的位置之后，這樣，以該基準值為分界線，將待排序序列分成兩個子序列，

一趟快速排序的具體做法為： 設定兩個指標low和high分別指向待排序列的開始和結尾，記錄下基準值baseval（待排序列的第一個記錄），然后先從high所指的位置向前搜索直到找到一個小于baseval的記錄并互相交換，接著從low所指向的位置向后搜索直到找到一個大于baseval的記錄并互相交換，重復這兩個步驟直到low=high為止，

時間復雜度： O(nlogn)，

直觀圖：



代碼實作：

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{4,2,8,0,5,1};
        System.out.println("排序之前：" + Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println("排序之后：" + Arrays.toString(arr));
    }

    /**
     * 快速排序
     * @param arr 陣列
     * @param left 起始位置0
     * @param right 末尾位置 (arr.length-1)
     */
    static void quickSort(int arr[],int left,int right){
        //左右兩指標相與直接回傳
        if(left >= right){
            return;
        }
        //為了方便起見，我們將i和j分別代表左右指標
        int i = left;
        int j = right;

        //獲取基準數(一般是以第一個數為基準數)
        int baseval = arr[left];
        while (i<j){
            //從右向左找比基準數小的記錄,
            while (i<j && arr[j] >= baseval){
                //如果不小于，j指標就繼續左移
                j--;
            }

            //從左向右找比基準數大的記錄,
            while (i<j && arr[i] <= baseval){
                //如果不大于，i指標就繼續右移
                i++;
            }

            //當j指標找打了比基準數小的值，當i指標找到比基準值大的值，交換兩者的位置
            int tem = arr[i];
            arr[i] = arr[j];
            arr[j] = tem;
        }

        //當兩指標相遇時，也就是i=j了，將此位置的值與基準值baseval交換
        arr[left] = arr[i];
        arr[i] = baseval;

        //遞回排序左右兩邊的序列
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }
}

執行結果：

排序之前：[4, 2, 8, 0, 5, 1]
排序之后：[0, 1, 2, 4, 5, 8]

1.7、堆排序

待續……