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

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

package com.css.java.learning.massbag;
import java.util.Arrays;
/**算法：
 * 排序相關(guān)小結(jié)
 * @author Red_ant
 * 20181119
 */
public class OrderMethod {
    /*1、冒泡排序
     * 通過相鄰兩個(gè)元素比較的方式，依次選出合適的元素放到
     * 數(shù)組的第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、選擇排序
     * 每一趟從待排序列，選擇最小的元素放到已排序好的序列末尾，剩下的為待排序序列，
     * 重復(fù)上述步驟，直至完成。
     */
    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++) {//選擇合適的元素，直接放到數(shù)組的第i位
                if(nums[index] > nums[j]){
                    index = j;
                }
                if(index != i){
                    num = nums[i];
                    nums[i] = nums[index];
                    nums[index] = num;
                }
            }
        }
        return nums;
    }
    /*3、選擇排序：堆排序
     * 堆排序是一種樹形結(jié)構(gòu)選擇排序
     * 堆排序需要兩個(gè)過程，建立堆，堆頂與堆最后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組成：
     * 建堆的***函數(shù)，反復(fù)調(diào)用***函數(shù)實(shí)現(xiàn)排序的函數(shù)
     * 基本思路：
     * 將序列建成一個(gè)堆，根據(jù)升序降序選擇大頂堆或小頂堆
     * 將堆頂元素與末尾元素交換，將最大元素沉到數(shù)組末端
     * 重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整+交換步驟，直到整個(gè)序列有序。
     */
    public static int[] HeapSorts(int[] nums){
        //建立大頂
        for (int i = nums.length/2 - 1; i >= 0; i--) {
            //從第一個(gè)非葉子節(jié)點(diǎn)從下至上，從右至左調(diào)整結(jié)構(gòu)
            suitHeap(nums, i, nums.length);
        }
        //調(diào)整堆結(jié)構(gòu)，交換堆頂元素與 末尾元素
        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];//取出當(dāng)前元素
        for (int j = i*2 + 1; j < length; j = j*2+1) {
            //從i節(jié)點(diǎn)的左節(jié)點(diǎn)開始，即2i+1處
            if(j+1 < length && nums[j] < nums[j+1]){
                //如果，左子節(jié)點(diǎn)小于右子節(jié)點(diǎn)，j指向右子節(jié)點(diǎn)
                j++;
            }
            if(nums[j] > index){
                //如果子節(jié)點(diǎn)大于父節(jié)點(diǎn)，將子節(jié)點(diǎn)賦值給父節(jié)點(diǎn)
                nums[i] = nums[j];
                i = j;
            }else{
                break;
            }
        }
        nums[i] = index;//將index值放到最終位置
    }

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