Arrays排序

    public static void arraysSort(int[] arr){
        // 数组为null时 如何去判断?
        if (arr == null || arr.length<=1) {
            System.out.println("arraySort()判断接收到的数组为null");
            return ;
        }

//        Arrays.sort(arr);     // 升序  部分升序: 形参为arr,0,3  左闭右开

        Integer[] reverseArr = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            reverseArr[i] = arr[i];
        }

        Arrays.sort(reverseArr, Collections.reverseOrder());

        for (int i = 0; i < arr.length; i++) {
            arr[i] = reverseArr[i];
        }
    }

1 selection sort

    public static void selectionSort(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];
            int index = i;

            for (int j = i+1; j < arr.length; j++) {
                if (min > arr[j]){
                    min = arr[j];
                    index = j;
                }
            }

            int temp = arr[i];
            arr[i] = min;
            arr[index] = temp;
        }
    }

2 heap sort

    public static void max_heapify(int[] arr, int n) {
        int c = 0;

        for (int i = (n-1)/2; i >= 0 ; i--) {
            c = 2*i + 1;

            if (c != n && arr[c] < arr[c+1])
                c++;

            if (arr[i] < arr[c]){
                int temp = arr[c];
                arr[c] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public static void heapSort(int[] arr){

        for (int i = arr.length-1; i > 0 ; i--) {
            max_heapify(arr, i);
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
        }
        
    }

3 bubble sort

    public static void bubbleSort(int[] arr) {

        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {

                if (arr[j] > arr[j+1]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }

            }
        }

    }

4 quick sort

    public static void quickSort(int[] arr, int left, int right) {
        if (left>right) return ;

        int i, j, temp, t;
        i = left;
        j = right;
        temp = arr[left];

        while (i != j){
            while (arr[j] >= temp && i<j)
                j--;
            while (arr[i] <= temp && i<j)
                i++;

            if (i < j){
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }

        arr[left] = arr[i];
        arr[i] = temp;

        quickSort(arr, left, i-1);
        quickSort(arr, i+1, right);
        
    }

5 insertion sort

    public static void insertionSort(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j-1]){
                    int temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
        }

    }

6 shell sort

    public static void shellSort(int[] arr){

        for (int i = arr.length/2; i > 0; i/=2) {

            for (int j = i; j < arr.length; j++) {
                for (int k = j; k > 0 && k+1 >0 ; k--) {

                    if (arr[k] < arr[k-1]){
                        int temp = arr[k-1];
                        arr[k-1] = arr[k];
                        arr[k] = temp;
                    }

                }
            }

        }

    }

7 merge sort

    public static void mergeArr(int[] arr, int left, int mid, int right){
        
        int[] temp = new int[arr.length];
        int p1=left, p2=mid+1, k=left;

        while (p1<=mid && p2<=right){
            if (arr[p1] < arr[p2]) temp[k++] = arr[p1++];
            else temp[k++] = arr[p2++];
        }

        while (p1<=mid) temp[k++] = arr[p1++];
        while (p2<=right) temp[k++] = arr[p2++];

        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }

    }

    public static void mergeSort(int[] arr, int left, int right){
        if (left>=right)return;

        int mid = (left+right)/2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        mergeArr(arr, left, mid, right);
    }    

8 bucket sort

    public static void bucketSort(int[] arr){

        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            max = arr[i] > max ? arr[i] : max;
        }

        int[] bucket = new int[max+1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }

        int res = 0;
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i]-- > 0)
                arr[res++] = i ;
        }

    }

9 count sort

    public static void countSort(int[] arr, int left, int right) {

        int[] bucket = new int[right-left+1];
        for (int i = 0; i < arr.length; i++) {
            bucket[ arr[i]-left ]++;
        }

        int res = 0;
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i]-- > 0)
                arr[res++] = i + left;
        }

    }

10 radix sort

    public static void radixSort(int[] arr){

        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            max = arr[i] > max ? arr[i] : max;
        }

        int d = 1;
        while (max/10>0){
            d++;
            max/=10;
        }

        int[][] bs = new int[10][arr.length];
        int base = 10;

        for (int i = 0; i < d; i++) {
            int[] bLen = new int[10];

            for (int j = 0; j < arr.length; j++) {
                int w = arr[j] % base / (base/10);
                bs[w][bLen[w]] = arr[j];
                bLen[w]++;
            }

            int res = 0;
            for (int b = 0; b < bs.length; b++) {
                for (int p = 0; p < bLen[b]; p++) {
                    arr[res++] = bs[b][p];
                }
            }
        }
        
    }