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