序言

相信大家一定有听说过排序算法，在笔面试时也经常会有关于排序的问题，今天我们一起学习回顾常见常用的排序算法吧。

下面我们先看张图：这张图介绍了各个排序的时间复杂度和空间复杂度，大家一定要牢固掌握。

对数器

在介绍这些算法之前，我们可以先引入一个对数器的概念，对数器的作用就是为了验证我们的排序算法结果是否正确。

实现原理：产生很多随机数，通过正确的排序算法对其进行排序，然后用我们自己的算法进行排序，校验两次排序结果是否相同来验证算法是否正确，同时为了确保算法的正确性，我们可以对其进行多次循环。即便如此也不能百分百保证算法是正确的。

代码如下：

class Logarithm {
    public int[] getArray() {
        int[] nums = new int[10000];
        Random random = new Random();
        for (int i = 0; i < nums.length; i++) {
            nums[i] = random.nextInt(10000);
        }
        return nums;
    }

    public boolean correct() {
        for (int k = 0; k < 10; k++) {
            int[] nums = this.getArray();
            int[] result = Arrays.copyOf(nums, nums.length);
            Arrays.sort(nums);
            Sort.mySort(result);
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != result[i]) {
                    return false;
                }
            }
        }
        return true;
    }
}

选择排序

选择排序是排序算法中较为简单的排序了

核心思想：每次循环都把最小值放到前面，共进行n-1次循环即可排序完毕

代码如下：

     public static void mySort(int[] a) {
        int length = a.length;
        for (int i = 0; i < length - 1; i++) {
            int point = i;
            for (int j = i + 1; j < length; j++) {
                if (a[j] < a[point]) {
                    point = j;
                }
            }
            if (point != i) {
                int temp = a[point];
                a[point] = a[i];
                a[i] = temp;
            }
        }
    }

冒泡排序

冒泡排序也是一种很经典的排序方式了，我学会的第一个排序算法就是它

核心思想：两两比较交换位置，每次循环都可以将最大值放到数组尾部，共进行n-1次循环即可排序完毕

代码如下：

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

插入排序

插入排序也是比较重要的一种排序了

核心思想：可以把数据看成一个队列，初始队列长度为1，然后每次循环将一个数给按从小到大的顺序插入到队列中即可

    public static void mySort(int[] a) {
        int length = a.length;
        for (int i = 1; i < length; i++) {
            if (a[i] < a[i - 1]) {
                for (int j = 0; j < i; j++) {
                    if (a[i] < a[j]) {
                        int num = a[i];
                        System.arraycopy(a, j, a, j + 1, i - j);
                        a[j] = num;
                    }
                }
            }
        }
    }

希尔排序

希尔排序算是加强版的插入排序了

核心思想：每次循环指定一个步长，索引为步长倍数的元素做排序，直至步长为1则排序完毕

代码如下：

public static void mySort(int[] a) {
        int h = 1;
        int length = a.length;
        while (h < length / 3) {
            h = h * 3 + 1;
        }
        for (int i = h; i > 0; i = (i - 1) / 3) {
            int stride = i;
            int start = stride - 1;
            for (int j = start + stride; j < length; j += stride) {
                if (a[j] < a[j - stride]) {
                    for (int l = start; l < j; l += stride) {
                        if (a[j] < a[l]) {
                            int num = a[j];
                            for (int n = j; n > l; n -= stride) {
                                a[n] = a[n - stride];
                            }
                            a[l] = num;
                        }
                    }
                }
            }
        }
    }

归并排序

归并排序还是比较常见的一种排序了，JAVA的Arrays.sort底层对引用类型排序时使用的就是归并排序

核心思想：分支+递归的套路，将一个大问题拆分成小问题，再对小问题进行合并

代码如下：

 public static void mySort(int[] a) {
        merge(a, 0, a.length - 1);
    }

    private static void merge(int[] a, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            merge(a, left, mid);
            merge(a, mid + 1, right);
            mergeSort(a, left, mid, right);
        }
    }

    private static void mergeSort(int[] a, int left, int mid, int right) {
        int[] news = new int[a.length];
        int point1 = left;
        int point2 = mid + 1;
        int index = left;
        while (point1 <= mid && point2 <= right) {
            if (a[point1] < a[point2]) {
                news[index++] = a[point1++];
            } else {
                news[index++] = a[point2++];
            }
        }
        while (point1 <= mid) {
            news[index++] = a[point1++];
        }
        while (point2 <= right) {
            news[index++] = a[point2++];
        }
        for (int i = left; i <= right; i++) {
            a[i] = news[i];
        }
    }

快速排序

快排也是比较常见的，在JAVA的Arrays.sort底层对基本类型排序时使用的就是快排（双轴快排）

核心思想：快排的思想也是递归，每次选择一个哨兵，把比哨兵小的放到它的左边，大的放到右边，然后递归再对它的左右两边排序。

代码如下：

    public static void mySort(int[] a) {
        qucikSort(a, 0, a.length - 1);
    }

    private static void qucikSort(int[] a, int left, int right) {
        if (left < right) {
            int point = a[left];
            int left1 = left;
            int right1 = right;
            while (left1 != right1) {
                while (right1 > left1 && a[right1] >= point) {
                    right1--;
                }
                a[left1] = a[right1];
                while (left1 < right1 && a[left1] <= point) {
                    left1++;
                }
                a[right1] = a[left1];
            }
            a[right1] = point;
            qucikSort(a, left, left1 - 1);
            qucikSort(a, left1 + 1, right);
        }
    }

计数排序

计数排序也可以算是桶排序的一种，它与常规的排序不同，不需要对元素进行比较排序

核心思想：求出数组元素中的边界值，创建一个新的桶数组，在桶数组中记录每个元素出现的次数，之后按顺序进行赋值（适用于量大范围小的数据）

代码如下：

public static void mySort(int[] a) {
        int[] ints = get(a);
        int min = ints[0];
        int max = ints[1];
        int[] buckets = new int[max - min + 1];
        for (int i = 0; i < a.length; i++) {
            buckets[a[i] - min]++;
        }
        int index = 0;
        for (int i = 0; i < buckets.length; i++) {
            int bucket = buckets[i];
            while (bucket != 0) {
                a[index++] = i + min;
                bucket--;
            }
        }
    }

    public static int[] get(int[] a) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < min) {
                min = a[i];
            }
            if (a[i] > max) {
                max = a[i];
            }
        }
        return new int[]{min, max};
    }

基数排序

基数排序也是桶排序的一种

核心思想：从最低位开始比较排序，直至最高位，最高位排序完毕后获取到最终结果

代码如下：

public static void mySort(int[] a) {
        int max = get(a);
        for (int i = 1; i < max; i *= 10) {
            int[][] buckets = new int[a.length][10];
            for (int k = 0; k < buckets.length; k++) {
                Arrays.fill(buckets[k], -1);
            }
            for (int j = 0; j < a.length; j++) {
                int num = (a[j] / i) % 10;
                buckets[j][num] = a[j];
            }
            int index = 0;
            for (int n = 0; n < 10; n++) {
                for (int m = 0; m < buckets.length; m++) {
                    if (buckets[m][n] != -1) {
                        a[index++] = buckets[m][n];
                    }
                }
            }
        }
    }

    public static int get(int[] a) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        return max;
    }