经典算法 - 排序算法

Liang

2020-02-16

经典算法

353

准备工作

分类科普

排序算法常见八种：

冒泡
插入
选择
归并
快速
堆排
希尔
基数

而一般最常用的还包括另外两种：

计数
桶排

其中：

时间复杂度为 O(n^2) 的是冒泡、插入、选择、希尔
时间复杂度为 O(nlogn) 的是 快速、归并、堆排
时间复杂度为 O(n) 的是基数、计数、桶排

接下来需要重点掌握加黑的六种排序，了解其思想与实现代码

工具类

在那之前先写一些测试对比的通用方法：

拷贝数组、打印数组、交换方法

public class SortUtil {

    public static void swap(int[] nums, int left, int right) {
        int t = nums[left];
        nums[left] = nums[right];
        nums[right] = t;
    }

    public static void printArr(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static int[] arrDeepClone(int[] nums) {
        int[] newNums = new int[nums.length];
        for (int i = 0; i < newNums.length; i++) {
            newNums[i] = nums[i];
        }
        return newNums;
    }

}

测试方法在一个主类里面测试

public class Main {
    public static void main(String[] args) {
        int[] nums = {9, 11, 5, 1, 14, 7, 4, 15, 2, 3, 13, 8, 6, 12, 10};
        SortUtil.printArr(nums);
        // 测试代码...
    }
}

完整测试代码：

public class Main {
    public static void main(String[] args) {
        int[] nums = {9, 11, 5, 1, 14, 7, 4, 15, 2, 3, 13, 8, 6, 12, 10};
        SortUtil.printArr(nums);
        SortUtil.printArr(Bubble.bubble(nums));
        SortUtil.printArr(Selection.selection(nums));
        SortUtil.printArr(Insertion.insertion(nums));
        SortUtil.printArr(Quick.quick(nums));
        SortUtil.printArr(Merge.merge(nums));
        SortUtil.printArr(Heap.heap(nums));
    }
}

结果：

9 11 5 1 14 7 4 15 2 3 13 8 6 12 10 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

一、冒泡排序

1.1 思想

基于两两之间比较，每一轮选出最大的，把它 “上浮” 到最后一个元素，也就是说有 n 个数，就要比较 n - 1 轮！

1.2 代码

public class Bubble {

    public static int[] bubble(int[] nums) {
        int[] newNums = SortUtil.arrDeepClone(nums);
        for (int i = 0; i < newNums.length; i++) {
            for (int j = 0; j < newNums.length - 1 - i; j++) {
                if (newNums[j] > newNums[j + 1]) {
                    SortUtil.swap(newNums, j, j + 1);
                }
            }
        }
        return newNums;
    }

}

二、选择排序

2.1 思想

选择也是基于两两之间的比较，每一轮都会在剩余的数下选出一个最大的，然后把最大的归位到数组最后一个位置！

2.2 代码

public class Selection {
    public static int[] selection(int[] nums) {
        int[] newNums = SortUtil.arrDeepClone(nums);
        for (int i = 0; i < newNums.length; i++) {
            // 记录最大的下标，每次从第一个开始
            int maxIndex = 0;
            for (int j = 0; j < newNums.length - i; j++) {
                if (newNums[j] > newNums[maxIndex]) {
                    maxIndex = j;
                }
            }
            SortUtil.swap(newNums, maxIndex, newNums.length - i - 1);
        }
        return newNums;
    }
}

三、插入排序

3.1 思想

无序数组中，第一个数肯定可以看作有序的了，然后第二个数与第一个比较，小的话就交换，这样，前两个数使之有序，第三个数与第二个数、第一个数有关... 第四个数以此类推，插入排序就是这样，每一轮将后面没访问的数插入到前面已经有序的序列中，最终使之有序

虽然说是插入，但其实是基于交换实现的，但硬要插入也可也，就是把找出插入的位置，然后把数往后面挪动，再把数插入

3.2 代码

public class Insertion {
    public static int[] insertion(int[] nums) {
        int[] newNums = SortUtil.arrDeepClone(nums);
        for (int i = 0; i < newNums.length; i++) {
            // 每一轮 for j 之后，0 ~ i 都是有序的！
            for (int j = i; j > 0; j--) {
                if (newNums[j] < newNums[j - 1]) {
                    SortUtil.swap(newNums, j, j - 1);
                }
            }
        }
        return newNums;
    }
}

四、快速排序

4.1 思想

一个无序数组排序成有序数组，其实就是每个数回到了有序序列中的相应的位置，而快速排序是基于分治，它是一个个地把数归位到相应的位置的，它的规则，也就是判断依据，就是：

如果一个数，它左边所有的数都 <= 它，它右边所有的数都 >= 它，那么它就已经归为到即将有序的序列它应在的位置了

那么如何归位每一个数，过程如何？

每次判断，会先选出一个数轴，叫做 pivot，比如，可以每次把当前要判断的区间第一个数选为 pivot
然后在这个区间中，找出符合上述规则的位置，把 pivot 归位到该位置，其实也就是交换
等这个 pivot 归位了，那么下一次只要对 pivot 的左侧和右侧排序即刻，也就是可以用分治来做！

4.2 代码

如果选择最左边的数作为 pivot，那么要从右往左开始检查；如果是选择最右的数作为 pivot，那么要从左往右开始检查

如果不这么做，可能发生数据的溢出问题！

public class Quick {
    public static int[] quick(int[] nums) {
        int[] newNums = SortUtil.arrDeepClone(nums);
        quickSort(newNums, 0, newNums.length - 1);
        return newNums;
    }

    public static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    public static int partition(int[] nums, int left, int right) {
        int l = left;
        int r = right;
        // 当前轮的 pivot，选择最左的数
        int temp = nums[left];

        while (l < r) {
            
            while (nums[r] >= temp && l < r) {
                r--;
            }

            while (nums[l] <= temp && l < r) {
                l++;
            }

            if (l < r) {
                SortUtil.swap(nums, l, r);
            }
        }

        nums[left] = nums[l];
        nums[l] = temp;
        return l;
    }
}

五、归并排序

5.1 思想

归并的思想也挺神奇，有很多种排序，二路、四路、八路、十六路等等的归并排序，主要是考虑磁盘 IO 和数据量两个因素来分割数据，但实际都差不多，这里就以二路归并为例子解析

归并排序，也是用到了分治的思想，一直把数组的区间一直分下去，跟快速不一样的是，它不是针对某个数进行归位，而是将所有的小区间排序，然后依次归并小区间，最后整体的区间就都有序了

5.2 代码

归并还是跪了，想法大概实现了。但细节是关于 help 的下标，可以看到 sort() 二路的两个小区间是：[left, mid] 和 [mid + 1, right] ，一开始写的参数循环不是 <= ，因此出错

public class Merge {

    public static int[] merge(int[] nums) {
        int[] newNums = SortUtil.arrDeepClone(nums);
        mergeSort(newNums, 0, newNums.length - 1);
        return newNums;
    }

    public static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        sort(nums, left, mid, right);
    }

    public static void sort(int[] nums, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int p1 = left;
        int p2 = mid + 1;
        int p3 = 0;
        while (p1 <= mid && p2 <= right) {
            help[p3++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
        }
        while (p1 <= mid) {
            help[p3++] = nums[p1++];
        }
        while (p2 <= right) {
            help[p3++] = nums[p2++];
        }
        for (int i = left; i <= right; i++) {
            nums[i] = help[i - left];
        }
    }

}

六、堆排序

6.1 思想

堆排序的思想也很神奇，是将数组抽象成二叉树的树状结构，把每一个数组都看作是一颗完全二叉树，比如数组下标 0 的左右孩子，就是 1 和 2，以此类推

然后把这些数调整为使得在这个抽象的树中，对于每个节点，左右孩子都比它小，并且左孩子小于或等于右孩子，那么这棵树中，根节点肯定就是最大的，这个过程最开始是从最后两个叶子节点的父节点开始的，这就是，上浮

再把它移动到最后一个叶子节点，也就是数组最后一个位置，那么一个节点就归位完成，然后现在这棵树会发现其他子树都是堆的结构，但根节所在那三个节点的子树是不符合的！这时只要将那个不符合所在节点的子树调整为堆就可以了，这就是，下沉

上浮和下沉都是需要通过调整子树来做，这就是调整为堆的过程，也就是把当前节点所在的子树调整为堆，这就是，调堆

6.2 代码

堆排久久没刷还是跪了，最难的还是堆排，满满的细节！上浮和下沉基本思路都有，主要还是调堆的细节！

思考到下沉的时候，每次调整都是 0 号下标，直接写 2*0 ，那么执行 i + 1，不就总是和它的左孩子比较，进行调堆？但或许这样也没什么问题。。。

还有一个细节是循环 len !=0 ，因为这最后一次交换完还会调堆，因此一定会出现 len = 0 的情况，不加上会死循环

public class Heap {

    public static int[] heap(int[] nums) {
        int[] newNums = SortUtil.arrDeepClone(nums);
        heapSort(newNums);
        return newNums;
    }

    private static void heapSort(int[] nums) {
        swim(nums, nums.length - 1);
        sink(nums, nums.length - 1);
    }

    private static void swim(int[] nums, int len) {
        for (int i = len / 2; i >= 0; i--) {
            adjustHeap(nums, i, len);
        }
    }

    private static void sink(int[] nums, int len) {
        for (int i = 0; i < len; i++) {
            SortUtil.swap(nums, 0, len - i);
            adjustHeap(nums, 0, len - i - 1);
        }
    }

    private static void adjustHeap(int[] nums, int k, int len) {
        // 基于 "覆盖" 的交换
        int swapNum = nums[k];
        for (int i = 2 * k; i <= len && len != 0; i *= 2) {
            if (i < len && nums[i] < nums[i + 1]) {
                i++;
            }
            if (swapNum > nums[i]) {
                break;
            } else {
                // 覆盖当前节点，并指向孩子
                nums[k] = nums[i];
                k = i;
            }
        }
        // 初始值覆盖到最后一个孩子节点
        nums[k] = swapNum;
    }

}