簡單算法之9種排序（一）

甭管什么，筆者就喜歡湊個9。這次，關于排序的算法還是9種，小結一下。排序的算法，盡管有很多的方法例子，但這次是自己總結的，挺有意思算法希望大家喜歡。直接上代碼樓，以下算法，都經過筆者親測，并修改使之有效（粘貼可用）。

package com.css.java.learning.massbag;
import java.util.Arrays;
/**算法：
 * 排序相關小結
 * @author Red_ant
 * 20181119
 */
public class OrderMethod {
    /*1、冒泡排序
     * 通過相鄰兩個元素比較的方式，依次選出合適的元素放到
     * 數組的第i位。
     */
    public static int[] bubbleSort(int[] nums){
        int num = 0;
        for (int i = 0; i < nums.length -1; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {//兩兩比較，符合條件的元素居于前面
                if(nums[j] > nums[j + 1]){
                    num = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = num;
                }
            }
        }
        return nums;
    }
    /*2、選擇排序
     * 每一趟從待排序列，選擇最小的元素放到已排序好的序列末尾，剩下的為待排序序列，
     * 重復上述步驟，直至完成。
     */
    public static int[] selectSort(int[] nums){
        int num = 0;
        for (int i = 0; i < nums.length -1; i++) {
            int index = i;
            for (int j = i + 1; j < nums.length; j++) {//選擇合適的元素，直接放到數組的第i位
                if(nums[index] > nums[j]){
                    index = j;
                }
                if(index != i){
                    num = nums[i];
                    nums[i] = nums[index];
                    nums[index] = num;
                }
            }
        }
        return nums;
    }
    /*3、選擇排序：堆排序
     * 堆排序是一種樹形結構選擇排序
     * 堆排序需要兩個過程，建立堆，堆頂與堆最后一個元素交換位置。所以堆排序有兩個函數組成：
     * 建堆的***函數，反復調用***函數實現排序的函數
     * 基本思路：
     * 將序列建成一個堆，根據升序降序選擇大頂堆或小頂堆
     * 將堆頂元素與末尾元素交換，將最大元素沉到數組末端
     * 重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序。
     */
    public static int[] HeapSorts(int[] nums){
        //建立大頂
        for (int i = nums.length/2 - 1; i >= 0; i--) {
            //從第一個非葉子節點從下至上，從右至左調整結構
            suitHeap(nums, i, nums.length);
        }
        //調整堆結構，交換堆頂元素與 末尾元素
        for (int j = nums.length - 1; j > 0; j--) {
            exchangeNum(nums, 0, j);//交換堆頂元素與末尾元素
            suitHeap(nums, 0, j);
        }
        return nums;
    }

    private static void exchangeNum(int[] nums, int i, int i2) {
        int index = nums[i];
        nums[i] = nums[i2];
        nums[i2] = index;
    }
    private static void suitHeap(int[] nums, int i, int length) {
        int index = nums[i];//取出當前元素
        for (int j = i*2 + 1; j < length; j = j*2+1) {
            //從i節點的左節點開始，即2i+1處
            if(j+1 < length && nums[j] < nums[j+1]){
                //如果，左子節點小于右子節點，j指向右子節點
                j++;
            }
            if(nums[j] > index){
                //如果子節點大于父節點，將子節點賦值給父節點
                nums[i] = nums[j];
                i = j;
            }else{
                break;
            }
        }
        nums[i] = index;//將index值放到最終位置
    }

    /*4、java Arrays排序
     * 該方法是Arrays類的靜態方法，在需要對數組進行排序時，非常好用
     */
    public static int[] ArraySort(int[] nums){
        Arrays.sort(nums);
        return nums;
    }
    /*5、插入排序：直接插入排序
     * 將數組分為兩部分，將后部分元素逐一與前部分元素比較
     * 然后依據比較結果進行移動元素
     */
    public static int[] insertSort(int[] nums){
        //從頭部第一個當做已經排序好的，把后面的一個一個的插入到已經排序好的列表中
        for (int i = 1; i < nums.length; i++) {
            int j;
            int index = nums[i];//index為待插入的元素
            for (j = i; j > 0 && index < nums[j - 1]; j--) {
                nums[j] = nums[j -1];
            }
            nums[j] = index;
        }
        return nums;
    }

    /*6、插入排序：希爾排序
     * 建堆，對頂與堆的最后一個元素進行排序
     * 希爾排序是插入排序的一種，先取一個小于n的整數作為第一個增量，把文件的全部記錄分組。
     * 所有距離為d1的倍數的記錄放在同一個組中，先在各組內進行直接插入排序。實際上是一種分組插入排序的方法。
     */
    public static int[] shellSrot(int[] nums){
        int index = nums.length/2;
        while (index >= 1) {
            for (int i = index; i < nums.length; i++) {
                if(nums[i] < nums[i - index]){
                    int j;
                    int x = nums[i];//當前待插入的元素
                    nums[i] = nums[i - index];
                    for (j = i - index; j >= 0 && x < nums[j]; j = j-index) {
                        nums[j + index] = nums[j];
                    }
                    nums[j + index] = x;//插入元素
                }
            }
            index = index/2;
        }
        return nums;
    }
    /*7、交換排序：快速排序
     * 基本思想：
     * A選擇一個基準元素，通常選擇第一個元素或最后一個元素
     * B通過一趟排序將待排序的記錄分割成獨立的兩部分：記錄均值比基準元素值小，元素值比基準元素值大
     * C此時基準元素在排序好的正確位置
     * D分別對這兩部分記錄，用同樣的方法繼續進行排序，直到整個序列有序。
     */
    public static int[] quickSort(int[] nums, int...is){
        int low,hight;
        if(is.length == 0){
            low = 0;
            hight = nums.length - 1;
        }else{
            low = is[0];
            hight = is[1];
        }
        if(low < hight){//判斷，讓遞歸函數退出，否則無限循環
            int middle = getMiddle(nums, low, hight);
            quickSort(nums, 0, middle - 1);//基準元素小
            quickSort(nums, middle + 1, hight);//比基準元素大
        }
        return nums;
    }
    //獲取，均值
    private static int getMiddle(int[] nums, int low, int hight) {
        int index = nums[low];//選擇基準元素
        while (low < hight) {
            //從hight開始，找出比基準小的，與low換位置
            while (low < hight && nums[hight] >= index) {
                hight--;
            }
            nums[low] = nums[hight];
            //從low開始找比基準大，放到之前hight空出來的位置上
            while (low < hight && nums[low] <= index) {
                low++;
            }
            nums[hight] = nums[low];
        }
        //此時low = hight是基準元素的位置，也是空缺的位置
        nums[low] = index;
        return low;
    }
    /*
     * 8、歸并排序
     * 基本思想：
     * 歸并排序是，將兩個或兩個以上有序表合并成一個新的有序表。
     * 即把待排序的序列分為若干個子序列，每個子序列是有序的，然后再把有序序列合并成整體有序序列
     */
    public static int[] mergeSort(int[] nums){
        sortmerge(nums, 0, nums.length - 1);
        return nums;
    }
    private static void sortmerge(int[] nums, int i, int j) {
        if(i >= j){
            return;
        }
        //找出中間索引
        int middle = (i + j)/2;
        //對左邊數組進行遞歸
        sortmerge(nums, i, middle);
        //對右邊數組進行遞歸
        sortmerge(nums, middle + 1, j);
        //合并數組
        merge(nums, i, middle, j);
    }
    private static void merge(int[] nums, int i, int middle, int j) {
        //創建臨時中間量數組
        int[] tmpArr = new int[nums.length];
        //右數組第一個元素索引
        int mid = middle + 1;
        //記錄臨時數組索引
        int second = i;
        //緩存左側數組第一個元素的索引
        int tmp = i;
        while (i <= middle && mid <= j) {
            //從兩個數組中取出最小的放到臨時數組中
            if(nums[i] <= nums[mid]){
                tmpArr[second++] = nums[i++];
            }else{
                tmpArr[second++] = nums[mid++];
            }
        }
        //剩余部分依次放入臨時數組
        while (mid <= j) {
            tmpArr[second++] = nums[mid++];
        }
        while (i <= middle) {
            tmpArr[second++] = nums[i++];
        }
        //將臨時數組中內容，拷貝到原數組中
        while (tmp <= j) {
            nums[tmp] = tmpArr[tmp++];
        }
    }
    /*9、基數排序（桶）
     * 將數組中的所有元素按照元素中最長的位數進行統一格式，不足位數的前面補充0
     * 然后，一次比較每一位的數字，得到最終的比較結果
     * 基本思想：
     * A遍歷找出最大的數（確定最大的數是幾）
     * B開辟臨時數組，用于中間過程的計算
     * C用一個count數組統計原數組中某一位(從低位向高位統計)相同的數據出現的次數；
     * D用一個start數組計算原數組中某一位(從最低位向最高位計算)相同數據出現的位置；
     * E將桶中數據從小到大用臨時數組收集起來；
     * F重復(3)(4)(5)直到所有位都被統計并計算過，用臨時數組收集起來；
     * G將臨時數組拷回到原數組中；
     */
    public static int[] radixSort(int[] nums) {
                int exp;    // 指數。當對數組按各位進行排序時，exp=1；按十位進行排序時，exp=10；...
                int max = getMax(nums);    // 數組a中的最大值
                // 從個位開始，對數組a按"指數"進行排序
                for (exp = 1; max/exp > 0; exp *= 10) {
                    countSort(nums, exp);
                }
                return nums;
        }
    //獲取數組中最大的元素
    private static int getMax(int[] nums) {
        int i, max;
            max = nums[0];
            for (i = 1; i < nums.length; i++)
                    if (nums[i] > max)
                            max = nums[i];
            return max;
    }
    /*
     * 對數組按照"某個位數"進行排序(桶排序)
     * 參數說明：
     * exp -- 指數。對數組a按照該指數進行排序。
     * (01) 當exp=1表示按照"個位"對數組a進行排序
     * (02) 當exp=10表示按照"十位"對數組a進行排序
     * (03) 當exp=100表示按照"百位"對數組a進行排序
     */
    private static void countSort(int[] a, int exp) {
        int[] output = new int[a.length]; // 存儲"被排序數據"的臨時數組
        int[] buckets = new int[10];
        // 將數據出現的次數存儲在buckets[]中
        for (int i = 0; i < a.length; i++)
            buckets[(a[i] / exp) % 10]++;
        // 更改buckets[i]。目的是讓更改后的buckets[i]的值，是該數據在output[]中的位置。
        for (int i = 1; i < 10; i++)
            buckets[i] += buckets[i - 1];
        // 將數據存儲到臨時數組output[]中
        for (int i = a.length - 1; i >= 0; i--) {
            output[buckets[(a[i] / exp) % 10] - 1] = a[i];
            buckets[(a[i] / exp) % 10]--;
        }
        // 將排序好的數據賦值給a[]
        for (int i = 0; i < a.length; i++) {
            a[i] = output[i];
        }
        // 用完清空
        output = null;
        buckets = null;
    }

    public static void main(String[] args) {
        int[] nums = {1221,232,1242,24,12,4,1,43,14,4,21,4,14,4,1,41,2};
        //nums = bubbleSort(nums);冒泡
        //nums = selectSort(nums);選擇
        //nums = ArraySort(nums);數組
        //nums = insertSort(nums);插入
        //nums = shellSrot(nums);希爾
        //nums = HeapSorts(nums);選擇排序：堆排序
        //nums = quickSort(nums);快速
        //nums = mergeSort(nums);歸并
        nums = radixSort(nums);
        for (int k = 0; k < nums.length; k++) {
            System.err.println("排序之后的"+nums[k]);
        }
    }
}