基于比较排序，时间复杂度的极限是O(N*logN)
追求稳定性，用归并
追求额外空间复杂度，用堆
追求绝对的速度，快排（常数时间最少）

对数器

package cn.org.wyxxt;

import cn.org.wyxxt.sort.insertion.Insertion;

import java.util.Arrays;

public class DataChecker {
    static int[] generateRandomArray(int maxSize, int maxValue) {
        //Math.random() [0,1)
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            // [-?,+?]
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    static void check() {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean same = true;
        for (int times = 0; times < testTime; times++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr);

            comparator(arr);
            Insertion.sort(arr2);


            if (!isEqual(arr, arr2)) {
                System.out.println(Arrays.toString(arr));
                System.out.println(Arrays.toString(arr2));
                same = false;
                break;
            }
        }

        System.out.println(same ? "Nice!" : "Fucking fucked!");
    }

    public static void main(String[] args) {
        check();
    }
}

选择排序

package cn.org.wyxxt.sort.selection;

public class Selection {

    public static void main(String[] args) {
        int[] arr = {1,4,8,2,9,0,3,6,5,7};
        sort(arr);
        print(arr);
    }

   public static void sort(int[] arr) {
        for (int i=0;i<arr.length-1;i++) {
            int minPos = i;

            for (int j=i+1;j<arr.length;j++) {
                minPos = arr[j]<arr[minPos] ? j : minPos;
            }
            swap(arr,i,minPos);
        }
    }

    static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void print(int[] arr) {
        for (int i=0;i<arr.length;i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

冒泡排序

package cn.org.wyxxt.sort.bubble;

public class Bubble {

    public static void main(String[] args) {
        int[] arr = {1,4,9,2,5,0,3,6,8,7};
        sort(arr);
        print(arr);
    }

    public static void sort(int[] arr) {
        for(int j=arr.length-1;j>0;j--) {
            findMax(arr, j);
        }

    }

    static void findMax(int[] arr,int n) {
        for (int i=0;i<n;i++) {
            if (arr[i]>arr[i+1]) swap(arr,i,i+1);
        }
    }


    static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void print(int[] arr) {
        for (int i=0;i<arr.length;i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

插入排序*

package cn.org.wyxxt.sort.insertion;

public class Insertion {
    public static void main(String[] args) {
        int[] arr = {8,6,3,9,5,1,7,4,2,0};
        sort(arr);
        print(arr);
    }

    public static void sort(int[] arr) {
        for (int i=1;i<arr.length;i++) {
            for (int j=i;j>0;j--) {
                if (arr[j]<arr[j-1]) {
                    swap(arr,j,j-1);
                }
            }
        }
    }

    static void swap(int[] arr,int i,int j) {
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
    }

    static void print(int[] arr) {
        for (int i=0;i<arr.length;i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

希尔排序

package cn.org.wyxxt.sort.shell;

public class Shell2 {

    public static void main(String[] args) {
        int[] arr = {9, 6, 3, 1, 4, 0, 8, 5, 2, 7};
        sort(arr);
        print(arr);
    }

    public static void sort(int[] arr) {
        int h = 1;
        while (h <= arr.length / 3) {
            h = h * 3 + 1;
        }

        for (int gap = h; gap > 0; gap = (gap - 1) / 3) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (arr[j] < arr[j - gap]) {
                        swap(arr, j, j - gap);
                    }
                }
            }
        }
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

归并排序*

package cn.org.wyxxt.sort.merge;

public class Merge {

    public static void main(String[] args) {
        int[] arr = {1, 6, 0, 2, 7, 3, 9, 8, 5, 4};
//        int[] arr = {1, 4, 7, 8, 3, 6, 9};
        sort(arr, 0, arr.length - 1);
        print(arr);
    }

    public static void sort(int[] arr, int left, int right) {
        if (left == right) return;
        //分成两半
        int mid = left + (right - left) / 2;
        //左边排序
        sort(arr, left, mid);
        //右边排序
        sort(arr, mid + 1, right);
        merge(arr, left, mid + 1, right);
    }

    static void merge(int[] arr, int leftPtr, int rightPtr, int rightBound) {
        int mid = rightPtr - 1;
        int[] temp = new int[rightBound - leftPtr + 1];

        int i = leftPtr;
        int j = rightPtr;
        int k = 0; //temp的第一个位置

        while (i <= mid && j <= rightBound) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];

            /**
             if (arr[i] <= arr[j]) { // <= 稳定性考虑
             temp[k++] = arr[i++];
             } else {
             temp[k++] = arr[j++];
             }
             */
        }

        while (i <= mid) temp[k++] = arr[i++];
        while (j <= rightBound) temp[k++] = arr[j++];

//        print(temp);
        for (int m = 0; m < temp.length; m++) arr[leftPtr + m] = temp[m];
    }


    static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

快速排序*

package cn.org.wyxxt.sort.quick;

public class Quick {
    public static void main(String[] args) {
        int[] arr = {7, 4, 1, 2, 8, 3, 9, 6, 5, 10};
        sort(arr, 0, arr.length - 1);
        print(arr);
    }

    public static void sort(int[] arr, int leftBound, int rightBound) {
        if (leftBound >= rightBound) return;
        int mid = partition(arr, leftBound, rightBound);
        sort(arr, leftBound, mid - 1);
        sort(arr, mid + 1, rightBound);
    }

    static int partition(int[] arr, int leftBound, int rightBound) {
        int pivot = arr[rightBound];
        int left = leftBound;
        int right = rightBound - 1;

        while (left <= right) {
            while (left <= right && arr[left] <= pivot) left++;
            while (left <= right && arr[right] >= pivot) right--;
//            System.out.println(pivot);
//            System.out.println("before swap:left->" + left + "right->" + right);
            if (left < right) swap(arr, left, right);
//            print(arr);
//            System.out.println();
        }
        swap(arr, left, rightBound);
        return left;
    }


    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

计数排序

package cn.org.wyxxt.sort.counting;

import java.util.Arrays;

public class Counting {

    public static void main(String[] args) {
        int[] arr = {2, 4, 2, 3, 7, 1, 1, 0, 0, 5, 6, 9, 8, 5, 7, 4, 0, 9, 1, 3, 7, 0, 6, 4, 6, 9, 8, 8, 7};
        int[] result = sort(arr);
        System.out.println(Arrays.toString(result));
    }

    public static int[] sort(int[] arr) {
        int[] result = new int[arr.length];
        int[] count = new int[10];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }
        System.out.println(Arrays.toString(count));

        /**
         * 不稳定排序 对象
         for (int i=0,j=0;i<count.length;i++) {
         while(count[i]-- > 0) result[j++] = i;
         }
         */

        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i - 1];
        }
        System.out.println(Arrays.toString(count));

        for (int i = arr.length - 1; i >= 0; i--) {
            result[--count[arr[i]]] = arr[i];
        }
        return result;
    }
}

基数排序

package cn.org.wyxxt.sort.radix;

import java.util.Arrays;

public class Radix {
    public static void main(String[] args) {
        int[] arr = {421, 240, 115, 532, 305, 430, 124};
        int[] result = sort(arr);
        System.out.println(Arrays.toString(result));
    }

    public static int[] sort(int[] arr) {
        int[] result = new int[arr.length];
        int[] count = new int[10];

        //基数排序，分个位十位百位。每一位排序都是计数排序
        for (int i = 0; i < 3; i++) {
            //个位排序
            int division = (int) Math.pow(10, i);
            for (int j = 0; j < arr.length; j++) {
                int num = arr[j] / division % 10;
                count[num]++;
            }
            for (int m = 1; m < count.length; m++) {
                count[m] = count[m] + count[m - 1];
            }
            System.out.println(Arrays.toString(count));
            for (int n = arr.length - 1; n >= 0; n--) {
                int num = arr[n] / division % 10;
                result[--count[num]] = arr[n];
            }
            System.arraycopy(result, 0, arr, 0, arr.length);
            Arrays.fill(count, 0);
        }
        return result;
    }

}

堆排序*