Java语言写的各种排序算法【未完】

import java.util.Arrays;
import java.util.Random;
import java.util.ArrayList;

/**
 * 默认升序排列
 * 可以调用reverse(int[] arr)方法反转数组使之逆序
 * 暂时没写完，学会一样就更新一样
 */
public class Sorts{
    private static Random rand = new Random();

    public static void main(String[] args){
        int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51}; 
        straightInsertSort(a);
        System.out.println(Arrays.toString(a));
        int[] b = {49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
        radixSort(b);
        System.out.println(Arrays.toString(b));
    }

    /**
     * 反转数组
     * @param arr 待反转数组
     */
    public static void reverse(int[] arr){
        for(int i = 0; i < arr.length/2; i++){
            swap(arr, i, arr.length-1-i);
        }
    }

    /**
     * 交换数组元素
     * @param arr 待交换的数组
     * @param i   位置1
     * @param j   位置2
     */
    private static void swap(int[] arr, int i , int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    /**
     * ---------------------直接插入排序---------------------
     * 在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，
     * 现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。
     * 如此反复循环，直到全部排好顺序。
     * @param arr 待排序数组
     */
    public static void straightInsertSort(int[] arr){
        if(arr.length < 2) return;
        for(int i = 1; i < arr.length; i++){ //i左侧都已排序
            int temp = arr[i]; //a[i]会变成其他值，故先转移到临时变量
            int j = i -1;
            while(j >= 0 && temp < arr[j]){ // j+1最大值为arr.length-1，故不会越界
                arr[j+1] = arr[j--];
            }
            arr[j+1] = temp;
        }
    }

    /**
     * ---------------------希尔排序（最小增量排序）---------------------
     * 基本思想：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组
     * 每组中记录的下标相差d.对每组中全部元素进行直接插入排序
     * 然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。
     * 当增量减到1时，进行直接插入排序后，排序完成。
     * @param arr 待排序数组
     */
    public static void shellSort(int[] arr){
        int d = arr.length;
        if (d < 2) return; //不符合条件则退出方法
        while(d > 1){
            d = (d-1)/3; //网上看到的，据说d = 3d + 1是最快的排序序列
            for(int i = 0; i < d; i++){ //一共拆成d个数组
                for(int j = i+d; j < arr.length; j += d){ //对每个数组进行插入排序
                    int temp = arr[j];
                    int k = j-d;
                    while(k >= 0 && temp < arr[k]){
                        arr[k+d] = arr[k];
                        k -= d;
                    }
                    arr[k+d] = temp;
                }
            }
        }
    }

    /**
     * ---------------------直接选择排序---------------------
     * 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
     * 然后在剩下的数当中再找最小的与第二个位置的数交换
     * 如此循环到倒数第二个数和最后一个数比较为止。
     * @param arr [description]
     */
    public static void straightSelectSort(int[] arr){
        if (arr.length < 2) return; //不符合条件则退出。
        int start = 0; //起始索引
        int i = 1; //遍历用的索引
        int min; //最小数的索引
        for(int j = 0; j <= arr.length-2; j++){
            min = j;
            for(int k = j; k < arr.length; k++){
                if (arr[k] < arr[min]) min = k;
            }
            if (min != j) swap(arr, min, j);
        }
    }

    /**
     * ---------------------堆排序---------------------
     * 堆的定义如下：具有n个元素的序列（h1,h2,…,hn),
     * 当且仅当满足（h(i) >= h(2i), h(i) >= h(2i+1) ）
     * 或（h(i) <= h(2i), h(i) <= h(2i+1)） (i=1,2,…,n/2)时称之为堆。
     * 在这里只讨论满足前者条件的堆。
     * 由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。
     * 完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
     * 初始时把要排序的数的序列看作是一棵顺序存储的二叉树，
     * 调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。
     * 然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。
     * 依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。
     * 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。
     * 所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
     * @param arr [description]
     */
    public static void heapSort(int[] arr){

    }

    /**
     * ---------------------冒泡排序---------------------
     * 在要排序的一组数中，对当前还未排好序的范围内的全部数，
     * 自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。
     * 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
     * @param arr 要排序的数组
     */
    public static void bubbleSort(int[] arr){
        if (arr.length < 2) return;
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j <= arr.length-2-i; j++){
                if (arr[j] > arr[j+1]) swap(arr, j, j+1);
            }
        }
    }

    /**
     * ---------------------快速排序---------------------
     * 首先在要排序的序列中选取一个中轴值，而后将序列分成三个部分，
     * 其中左边部分中的元素均小于中轴值，中间部分元素均等于中轴值，
     * 右边的部分的元素均大于中轴值，
     * 而后通过递归调用快速排序的过程分别对左右两个部分进行排序，
     * 最后将三部分结果合并即可得到最后的排序序列。
     * @param arr 待排序的数组
     */
    public static void quickSort(int[] arr){ //快速排序入口，调用时不必填三个参数
        quickSort(arr, 0, arr.length-1);
    }

    /**
     * 快速排序执行部分
     * @param arr   待排序数组
     * @param start 开始索引
     * @param end   结束索引
     */
    private static void quickSort(int[] arr, int start, int end){
        if (start >= end) return;
        int index = arr[start + rand.nextInt(end-start+1)]; //中轴值
        int left = start, right = end; //指示左右两端未排序的边界索引
        int i = start; // 用于排序
        while(i <= right){
            if (arr[i] < index){ //小于中轴值则移到左侧
                swap(arr, left++, i++);
            }else if (arr[i] > index){ //大于中轴值则移到右侧
                swap(arr, right--, i); //当前i位置的值未排序，故i不自增
            }else{
                i++;
            }
        }
        //排完后left左侧均为小于index的数，right右侧均为大于index的数
        quickSort(arr, start, left-1);
        quickSort(arr, right+1, end);
    }

    /**
     * ---------------------归并排序---------------------
     * 将两个（或两个以上）有序表合并成一个新的有序表，
     * 即把待排序序列分为若干个子序列，每个子序列是有序的。
     * 然后再把有序子序列合并为整体有序序列。
     * @param arr 待排序数组
     */
    public static void mergeSort(int[] arr){
        mergeSort(arr, 0, arr.length-1);
    }

    /**
     * 归并排序递归部分
     * @param arr   待排序数组
     * @param start 开头索引
     * @param end   末尾索引
     */
    private static void mergeSort(int[] arr, int start, int end){
        if(start >= end) return; //一个元素则不须排序
        int mid = (start + end) / 2;
        mergeSort(arr, start, mid); //分别拆开
        mergeSort(arr, mid+1, end); //经验证，这样不会数组越界
        merge(arr, start, mid, mid+1, end); //归并
    }

    /**
     * 归并排序合并数组
     * 其中end1 + 1 = start2，拆成两部分更直观
     * @param arr    待合并数组
     * @param start1 左半部分开头索引
     * @param end1   左半部分末尾索引
     * @param start2 右半部分开头索引
     * @param end2   右半部分末尾索引
     */
    private static void merge(int[] arr, int start1, int end1, int start2, int end2){
        int[] tmp = new int[end1-start1+end2-start2+2]; //临时存放用的数组
        int i = start1, j = start2, k = 0; //分别用于遍历数组
        while(i <= end1 && j <= end2){ //归并排序
            tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; //若相等，则按原来的次序，优先放arr[i]
        }
        //再把剩余的数组内容存入tmp[]，上一步已经排尽的数组，其i或j的值是大于下界的
        while(i <= end1){
            tmp[k++] = arr[i++];
        }
        while(j <= end2){
            tmp[k++] = arr[j++];
        }
        // 最后把tmp复制回原数组
        System.arraycopy(tmp, 0, arr, start1, tmp.length);
    }

    /**
     * 基数排序
     * 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
     * 然后，从最低位开始，依次进行一次排序。
     * 这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
     * @param arr 待排序数组
     */
    public static void radixSort(int[] arr){
        //创建Integer数组，使中间步骤不必频繁转换类型
        Integer[] array = new Integer[arr.length]; 
        for(int i = 0; i < arr.length; i++){
            array[i] = arr[i];
        }
        //创建链表用于保存同位数的数字，无法创建泛型数组，只能用这种方式
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); 
        for(int i = 0; i < 10; i++){
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            list.add(tmp);
        }
        //先找出最大位数，即最大值的位数
        int max = arr[0];
        for(int i = 1; i < arr.length; i++){
            if (max < arr[i]){
                max = arr[i];
            }
        }
        int place = String.valueOf(max).length(); //最大值的位数
        int dividend = 1; //除数，用于置某位为个位
        //开始排序
        for(int i = 1; i <= place; i++){
            for(Integer num : array){ //数组根据相应位数存入list
                list.get(num / dividend % 10).add(num); 
            }
            //取出数字放回数组
            int index = 0;
            for(ArrayList<Integer> tmp : list){
                while(tmp.size() > 0){
                    array[index++] = tmp.get(0);
                    tmp.remove(0);
                }
            }
            dividend *= 10; //进位
        }
        //把最终结果存回arr
        for(int i = 0; i < arr.length; i++){
            arr[i] = array[i];
        }
    }
}