简单算法之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]);
        }
    }
}