数组排序问题（二）

荷兰国旗问题

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。

我们需要把数组分为三个区域，那么就需要两个指针，less指针和more指针。

less指针的左边表示比num小的区域，
more指针的右边表示比num大的区域，
less指针和more指针之间表示等于num的区域。

我们还需要一个指针current，用来遍历数组。整体思路如下：

当arr[current]比num小，那么把这个数交换到左边区域，并且less指针右移一位。
当arr[current]比num大，那么把这个数交换到右边区域，并且more指针左移一位。
当arr[current]等于num，属于中间区域，不进行交换，current继续遍历数组。
当current等于more时，说明整个数组都已完成遍历。

   public static int[] partition(int[] arr, int left, int right, int num){
        int less = left - 1;
        int more = right + 1;
        int current = left;
        while (current < more){
            if(arr[current] < num){
                swap(arr, ++less, current++);
            }else if(arr[current] > num){
                swap(arr, current, --more);
            }else {
                current++;
            }
        }
        return new int[]{less + 1, more - 1};
    }

    // for test
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

随机快排

随机快排的思路是使用递归的方式复用荷兰国旗问题的算法将数组排序。

先在数组内随机找到一个数num，将这个数与数组的最后一个数交换。
以num为基准将数组分为小于num、等于num、大于num三个区域（荷兰国旗问题）。
这时候我们就已经将num排好序了，左边都是比num小的，右边都是比num大的。
再重复第一步递归左边区域和右边区域，直到数组无法再进行划分，排序完成。

public static void quickSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int left, int right){
        if(left < right){
            swap(arr, left + (int) (Math.random() * (right - left + 1)), right);
            int[] p = partition(arr, left, right);
            quickSort(arr, left, p[0] - 1);
            quickSort(arr, p[1] + 1, right);
        }
    }

    public static int[] partition(int[] arr, int left, int right){
        int less = left - 1;
        int more = right + 1;
        int current = left;
        int num = arr[right];

        while (current < more){
            if(arr[current] < num){
                swap(arr, ++less, current++);
            } else if(arr[current] > num){
                swap(arr, --more, current);
            } else {
                current++;
            }
        }
        return new int[]{less + 1, more - 1};
    }

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

随机快排的时间复杂度O(N*logN)，额外空间复杂度O(logN)

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法。

堆排序需要几个步骤：

建立大根堆，堆顶是数组最大值。
将数组最大值调换到末尾。
将剩余n-1个元素重新构造成一个堆。
反复执行1~3，直到完成排序。

堆是一种完全二叉树的逻辑结构，可以用数组模拟其建立过程。

根节点：arr[i]
左孩子节点：arr[2 * i + 1]
右孩子节点：arr[2 * i + 2]

大根堆是指每个结点的值都大于或等于其左右孩子结点的值。

arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2 * i + 2]

建立好大根堆结构以后，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

public static void heapSort(int[] arr){

        if(arr == null || arr.length == 0){
            return;
        }
        
        //建立大根堆
        for(int i = 0; i < arr.length; i++){
            //每次往堆结构中加入一个数
            heapInsert(arr, i);
        }
        //将最大的数交换到末尾
        int size = arr.length;
        swap(arr, 0, --size);
        
        while (size > 0){
            //整理堆
            heapify(arr, 0, size);
            //继续交换最大的数交换到末尾
            swap(arr, 0, --size);
        }
    }

    //建立大根堆的过程
    public static void heapInsert(int[] arr, int index){
        while (arr[index] > arr[(index - 1) / 2]){
            //arr[(index - 1) / 2] 是 arr[index]的父节点
            //只要父节点比自己小，就交换
            swap(arr, index, (index - 1) / 2);
            //继续指向最小的数，直到排列成大根堆
            index = (index - 1) / 2;    
        }
    }

    public static void heapify(int[] arr, int index, int size) {
        //左孩子节点下标
        int left = index * 2 + 1;
        while (left < size){
            //比较左右两个叶节点,  left + 1 < size表示判断右节点有没有超出比较范围
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            //比较自己和最大子节点，找到最大的一个
            largest = arr[largest] > arr[index] ? largest : index;
            //如果自己是最大的节点，则不再向下比较
            if(largest == index){
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

堆排序的时间复杂度O(N*logN)，额外空间复杂度O(1)

排序算法的稳定性及其汇总

排序算法的稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

稳定算法：冒泡排序、插入排序、归并排序、基数排序
不稳定算法：选择排序、快速排序、希尔排序、堆排序

排序算法汇总

冒泡排序：每一轮相邻位置比较，判断交换与否，找到该轮最大/最小，放到相应位置，执行下一轮。
选择排序：每次找最大、最小放到相应位置。
插入排序：每次判断一个数跟前边所有的值得大小，找到合适位置，插入。
归并排序：分最多的组，两两合并，使组越来越小，每次合并按照目的顺序合并。关键在组的合并函数（为两个组设置标志，移动标志位去判断该让哪一个数进新组）。
快速排序：随机选择某数，按该数分成左右两组。对左右两组再进行以上划分。
堆排序：建堆过程从n/2位置向前每一位进行与左右孩子的比较与交换。将堆顶与最后一个值交换，出最大值。堆调整，从堆顶（此时为不符合的情况）一直往下交换至大于/小于子节点为止，调整结束。
希尔排序：插排改良,插排往前比较一位。希尔而是一个设置步长。步长降低，直到步长为一。
桶排序：计数排序、基数排序。

时间复杂度：

O(N^2)：冒泡排序、选择排序、插入排序
O(N*logN)：归并排序、快速排序（随机）、堆排序、希尔排序
O(N)：桶排序

额外空间复杂度：

O(1)：冒泡排序、选择排序、插入排序、堆排序、希尔排序
O(logN)~O(N)：快速排序
O(N)：归并排序
O(M)：桶排序（桶的数量）

工程中的综合排序算法

数据量小：直接用插入排序，在数据量少的情况下算法时间复杂度的优劣很难体现数来，拼的就是常数项，而插排的常数项非常少。

数据量大：如果数据是基础数据，使用快排；如果数据是自定义类型，为了保持稳定性，用归并排序。无论哪种排序，当分割样本小于一定量时，直接视为小样本，用插排。

比较器的使用

//compare方法中，返回负的时候，认为第一个参数应该排在前面
//compare方法中，返回正的时候，认为第二个参数应该排在前面
//compare方法中，返回0的时候，认为谁放在前面都行
public static class IdAscendingComparator implements java.util.Comparator<Student> {
 
    @Override
    public int compare(Student o1, Student o2) {
        return o1.id - o2.id;
    }
 
}

...

Arrays.sort(students, new IdAscendingComparator());

桶排序、计数排序、基数排序的介绍

桶排序：工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序。

非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以实际中并不经常使用。
时间复杂度O(N)，额外空间复杂度O(N)。
稳定的排序。

补充问题

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能用非基于比较的排序。

思路：

先遍历整个数组arr，找到最小数min和最大数max。
在min和max之间分成arr.length + 1个桶，将数组中的数按照桶的范围分到各个桶中。这样就可以保证整个桶序列的左边和右边都是非空桶，而中间必定至少有一个空桶，而且最大差值必定不产生在同一个桶中。
找到每一个非空桶的最小数和最大数，最小数与邻近的左边非空桶最大值比较，最大值与邻近的右边非空桶比较，找到这些差值的最大值，即为最大差值。

public static int maxGap(int[] arr){

        int len = arr.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        
        //找到最大值和最小值
        for(int i = 0; i < arr.length; i++){
            if(arr[i] < min){
                min = arr[i];
            }
            if(arr[i] > max){
                max = arr[i];
            }
        }
        if(min == max){
            return 0;
        }

        //三个数组分别是是否空桶、桶中最大值、桶中最小值的集合
        boolean[] hasNum = new boolean[len + 1];
        int[] maxs = new int[len + 1];
        int[] mins = new int[len + 1];
        int bid = 0;    //分在哪个桶里

        //将每个数分配到各个桶中，得到桶中最大值和最小值
        for(int i = 0; i < arr.length; i++){
            bid = bucket(arr[i], len, min, max);
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], arr[i]) : arr[i];
            mins[bid] = hasNum[bid] ? Math.min(mins[bid], arr[i]) : arr[i];
            hasNum[bid] = true;
        }

        int res = 0;
        int lastMax = maxs[0];
        //每个桶的最小值和上一个非空桶的最大值比较，得到最大差值
        for(int i = 0; i <= len; i++){
            if(hasNum[i]){
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }
    
    //分在哪个桶里
    public static int bucket(long num, long len, long min, long max) {
        return (int) ((num - min) * len / (max - min));
    }

参考资料：牛客网左程云初级算法教程