一隅很、插入排序

插入排序是一種最簡(jiǎn)單直觀的排序算法叔营，它的工作原理是通過(guò)構(gòu)建有序序列所宰，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描仔粥，找到相應(yīng)位置并插入。

  public static void main(String[] s) {
        int[] array = {3,1,6,0,8};
        //循環(huán)的次數(shù)谭羔，也監(jiān)控著每一輪開(kāi)始key的位置
        for (int i = 0; i < array.length - 1; i++) {
            int key = array[i + 1];
            int j;
            //一邊比較一邊為key的插入騰空位
            for (j = i; j >= 0 && key < array[j]; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = key;
        }
        System.out.println(Arrays.toString(array));
    }

二口糕、希爾排序

希爾排序磕蛇，也稱遞減增量排序算法十办，是插入排序的一種更高效的改進(jìn)版本超棺。但希爾排序是非穩(wěn)定排序算法。
先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序件相，待整個(gè)序列中的記錄“基本有序”時(shí)氧苍，再對(duì)全體記錄進(jìn)行依次直接插入排序。

  public static void main(String[] args) {
        int[] arr = {3,1,6,0,8};
        //step:步長(zhǎng)
        for (int step = arr.length / 2; step > 0; step /= 2) {
            //對(duì)一個(gè)步長(zhǎng)區(qū)間進(jìn)行比較 [step,arr.length)
            for (int i = step; i < arr.length; i++) {
                int value = arr[i];
                int j;
                //對(duì)步長(zhǎng)區(qū)間中具體的元素進(jìn)行比較
                for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
                    //j為左區(qū)間的取值紊撕，j+step為右區(qū)間與左區(qū)間的對(duì)應(yīng)值赡突。
                    arr[j + step] = arr[j];
                }
                //此時(shí)step為一個(gè)負(fù)數(shù)惭缰，[j + step]為左區(qū)間上的初始交換值
                arr[j + step] = value;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

三、選擇排序

1）首先在未排序序列中找到最新缭洹（大）元素昂羡，存放到排序序列的起始位置
2）再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素紧憾，然后放到已排序序列的末尾赴穗。
3）重復(fù)第二步，直到所有元素均排序完畢般眉。

  public static void main(String[] args) {
        int[] arr = {3,1,6,0,8};
        for (int i = 0; i < arr.length; i++) {
            // 將當(dāng)前下標(biāo)定義為最小值下標(biāo)
            int minIndex = i;
            for (int j = i+1; j <arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            //如果不是同一個(gè)甸赃，就交換
            if (i != minIndex) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

四、冒泡排序

冒泡排序（Bubble Sort）也是一種簡(jiǎn)單直觀的排序算法络断。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素貌笨，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)锥惋。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成遭商。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端捅伤。

  public static void main(String[] args) {
        int[] arr = {3,1,6,0,8};
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

五、歸并排序

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法困介。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用蘸际。

    public static void main(String[] args) {
        int[] a = {3,1,6,0,8};
        int[] temp = new int[a.length];
        diao(a, 0, a.length-1,temp);
        System.out.println(Arrays.toString(a));
    }

    /**
     * 分和合 的方法
     * @param arr 原數(shù)組
     * @param left 左部分的開(kāi)始
     * @param right 右部分的結(jié)束
     * @param temp 臨時(shí)數(shù)組
     */
    public static void diao(int[] arr, int left, int right, int[] temp) {
        if (left >= right) {//如果左大于等于右 說(shuō)明到合并方法時(shí)只剩下一部分了,沒(méi)有對(duì)比 自然不能發(fā)生比較排序
            return;
        }
        int mid = (left + right) / 2;//中間索引
        diao(arr, left, mid, temp);//左遞歸分
        diao(arr, mid + 1, right, temp);//右遞歸分解
        mergeSort(arr, left, mid, right, temp);//分解完 兩部分比較 排序插入數(shù)組
    }

    /**
     * 合并方法
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @param temp
     */
    public static void mergeSort(int[] arr, int left, int mid, int right, int[] temp) {

        int i = left;//記錄左部分開(kāi)頭
        int j = mid + 1;//右部分開(kāi)頭  同時(shí)也是左部分結(jié)束
        int index = 0;//輔助下標(biāo)
        while (i <= mid && j <= right) {//如果左右開(kāi)頭部分 沒(méi)到各自結(jié)尾 就繼續(xù)合并 直到一部分處理完畢
            //如果左邊小于右邊 將左邊添加到temp
            //同時(shí) index++ i++
            if (arr[i] <= arr[j]) {
                temp[index] = arr[i];
                index++;
                i++;
            } else {//反之 index++  j++
                temp[index] = arr[j];
                index++;
                j++;
            }
        }
        //當(dāng) 兩部分有一個(gè)處理完畢 剩下一個(gè) 將剩下部分的數(shù)字 全部填入temp
        while (i <= mid) {
            temp[index] = arr[i];
            index++;
            i++;
        }
        while (j <= right) {
            temp[index] = arr[j];
            index++;
            j++;
        }
        //將temp數(shù)組部分拷貝到 arr
        //注意不是 temp全部拷貝 而是沒(méi)次調(diào)用合方法中 比較的兩個(gè)部分的數(shù)字 拷貝
        //第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
        //最后一次 tempLeft = 0  right = 7
        index = 0;
        int arrIndex=left;
        while (arrIndex <= right) {
            arr[arrIndex] = temp[index++];
            arrIndex++;
        }
    }

六、快速排序

快速排序是由東尼·霍爾所發(fā)展的一種排序算法姜骡。在平均狀況下，排序 n 個(gè)項(xiàng)目要Ο(n log n)次比較惫周。在最壞狀況下則需要Ο(n2)次比較康栈，但這種狀況并不常見(jiàn)。事實(shí)上登舞，快速排序通常明顯比其他Ο(n log n) 算法更快悬荣，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)。

    public static void main(String[] args) {
        int[] arr = {3, 1, 6, 0, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr, int low, int high) {
        int i, j, temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        //temp就是基準(zhǔn)位
        temp = arr[low];
        while (i < j) {
            //先看右邊践叠，依次往左遞減
            while (temp <= arr[j] && i < j) {
                j--;
            }
            //再看左邊，依次往右遞增
            while (temp >= arr[i] && i < j) {
                i++;
            }
            //如果滿足條件則交換
            if (i < j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換
        arr[low] = arr[i];
        arr[i] = temp;
        //遞歸調(diào)用左半數(shù)組
        quickSort(arr, low, j - 1);
        //遞歸調(diào)用右半數(shù)組
        quickSort(arr, j + 1, high);
    }

七轧简、堆排序

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法匾二。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)察藐，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

    public static void main(String[] args) {
        int[] arr = {3, 1, 6, 0, 8};
        headSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 堆排序
     */
    public static void headSort(int[] list) {
        //構(gòu)造初始堆,從第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始調(diào)整,左右孩子節(jié)點(diǎn)中較大的交換到父節(jié)點(diǎn)中
        for (int i = (list.length) / 2 - 1; i >= 0; i--) {
            headAdjust(list, list.length, i);
        }
        //排序悴务，將最大的節(jié)點(diǎn)放在堆尾譬猫，然后從根節(jié)點(diǎn)重新調(diào)整
        for (int i = list.length - 1; i >= 1; i--) {
            int temp = list[0];
            list[0] = list[i];
            list[i] = temp;
            headAdjust(list, i, 0);
        }
    }

    private static void headAdjust(int[] list, int len, int i) {
        int k = i, temp = list[i], index = 2 * k + 1;
        while (index < len) {
            if (index + 1 < len) {
                if (list[index] < list[index + 1]) {
                    index = index + 1;
                }
            }
            if (list[index] > temp) {
                list[k] = list[index];
                k = index;
                index = 2 * k + 1;
            } else {
                break;
            }
        }
        list[k] = temp;
    }

八、基數(shù)排序

基數(shù)排序是一種非比較型整數(shù)排序算法别洪，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字柳刮，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)痢毒，所以基數(shù)排序也不是只能使用于整數(shù)蚕甥。

    public static void main(String[] args){
        //定義整型數(shù)組
        int[] arr = {3, 1, 6, 0, 8};
        radixSort(arr, getMaxWeishu(arr));
        //調(diào)用基數(shù)排序函數(shù)
        System.out.println(Arrays.toString(arr));
    }
    //pos=1表示個(gè)位，pos=2表示十位
    public static int getNumInPos(int num, int pos) {
        int tmp = 1;
        for (int i = 0; i < pos - 1; i++) {
            tmp *= 10;
        }
        return (num / tmp) % 10;
    }
    //求得最大位數(shù)d
    public static int getMaxWeishu(int[] a) {
        int max = a[0];
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max)
                max = a[i];
        }
        int tmp = 1, d = 1;
        while (true) {
            tmp *= 10;
            if (max / tmp != 0) {
                d++;
            } else {
                break;
            }
        }
        return d;
    }
    public static void radixSort(int[] a, int d) {
        int[][] array = new int[10][a.length + 1];
        for (int i = 0; i < 10; i++) {
            array[i][0] = 0;// array[i][0]記錄第i行數(shù)據(jù)的個(gè)數(shù)
        }
        for (int pos = 1; pos <= d; pos++) {
            for (int i = 0; i < a.length; i++) {// 分配過(guò)程
                int row = getNumInPos(a[i], pos);
                int col = ++array[row][0];
                array[row][col] = a[i];
            }
            for (int row = 0, i = 0; row < 10; row++) {// 收集過(guò)程
                for (int col = 1; col <= array[row][0]; col++) {
                    a[i++] = array[row][col];
                }
                array[row][0] = 0;// 復(fù)位，下一個(gè)pos時(shí)還需使用
            }
        }
    }

總結(jié)

各種排序的穩(wěn)定性敏释，時(shí)間復(fù)雜度、空間復(fù)雜度义屏、穩(wěn)定性總結(jié)如下圖：

image.png