排序算法重梳理

0.复杂度和稳定性汇总

版本一

名词解释：

• n：数据规模
• k："桶"的个数
• In-place：占用常数内存，不占用额外内存
• Out-place：占用额外内存
• 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

版本二

​ 其中：

1. k表示计数排序中最大值和最小值之间的差值；
2. l表示桶排序中桶的个数；
3. d表示基数排序中最大值的位数，r表示是多少进制；
4. 希尔排序的时间复杂度很大程度上取决于增量gap sequence的选择，不同的增量会有不同的时间复杂度。文中使用的“gap=length/2”和“gap=gap/2”是一种常用的方式，也被称为希尔增量，但其并不是最优的。其实希尔排序增量的选择与证明一直都是个数学难题，而下图列出的是迄今为止大部分的gap sequence选择的方案：
   

1.逐一代码实现

1.1 冒泡排序

每次循环都比较前后两个元素的大小，如果前者大于后者，则将两者进行交换。这样做会将每次循环中最大的元素替换到末尾，逐渐形成有序集合。将每次循环中的最大(小)元素逐渐由队首转移到队尾的过程形似“冒泡”过程，故因此得名。

一个优化冒泡排序的方法就是 如果在一次循环的过程中没有发生交换，则可以立即退出当前循环，因为此时已经排好序了（也就是时间复杂度最好情况下是$O(n)$的由来）。

import java.util.Arrays;

class Solution {
    // 交换数组元素位置
    public static void swap(int[] array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flag = false;//记录本轮是否发生冒泡
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flag = true;
                }
            }
            if (!flag) { //本轮没有发生冒泡则表示数组已经有序，可以直接break
                break;
            }
        }
    }

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

1.2 选择排序

每次循环都会找出当前循环中最小(大)的元素，然后和此次循环中的队首元素进行交换。

import java.util.Arrays;

class Solution {
    // 交换数组元素位置
    public static void swap(int[] array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                minIndex = array[j]<array[minIndex]?j:minIndex;
            }
            swap(array,i,minIndex);
        }
    }

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

1.3 快速排序

import java.util.Arrays;

class Solution {
    // 交换数组元素位置
    public static void swap(int[] array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    /**
     * @brief 快速排序-partition
     *        大体思想：把比pivot小的换到前面
     */
    public static int partition(int[] array,int left,int right){
        // 取最后一个元素作为中心元素
        int pivot = array[right];

        // 遍历数组中的所有元素，将比中心元素大的放在右边，比中心元素小的放在左边---该步骤有点类似于选择排序
        int i = left;
        for (int j = left; j < right; j++) {
            if (array[j] <= pivot) {
                swap(array,i,j);//比pivot小的，全部换到前面去
                i++;
            }
        }
        //此时，i指向的元素一定大于等于pivot,把privot换回到中间
        swap(array,i,right);

        return i;
    }

    /**
     * @brief 快速排序-递归划分
     */
    public static void quickSort(int[] array){
        int mid = partition(array,0, array.length-1);
        quickSort(array,0,mid-1);
        quickSort(array,mid+1,right);
    }

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

1.4 插入排序

插入排序的精髓在于每次都会在先前排好序的子集合中插入下一个待排序的元素，每次都会判断待排序元素的上一个元素是否大于待排序元素，如果大于，则将元素右移，然后判断再上一个元素与待排序元素...以此类推。直到小于等于比较元素时就是找到了该元素的插入位置。这里的等于条件放在哪里很重要，因为它是决定插入排序稳定与否的关键。

import java.util.Arrays;

class Solution {
    // 交换数组元素位置
    public static void swap(int[] array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int curItem = array[i];//缓存下一个待排序的元素

            // 把有序集合中的所有比curItem大的元素都往后移一位
            int j = i-1;
            while (j>=0&&array[j]>curItem){
                array[j+1] = array[j--];
            }

            // 把待排序元素插入到有序序列中
            array[j+1] = curItem;
        }
    }

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

1.5 希尔排序

希尔排序可以认为是插入排序的改进版本。首先按照初始增量来将数组分成多个组，每个组内部使用插入排序。然后缩小增量来重新分组，组内再次使用插入排序...重复以上步骤，直到增量变为1的时候，这个时候整个数组就是一个分组，进行最后一次完整的插入排序即可结束。

在排序开始时的增量较大，分组也会较多，但是每个分组中的数据较少，所以插入排序会很快。随着每一轮排序的进行，增量和分组数会逐渐变小，每个分组中的数据会逐渐变多。但因为之前已经经过了多轮的分组排序，而此时的数组会趋近于一个有序的状态，所以这个时候的排序也是很快的。而对于数据较多且趋向于无序的数据来说，如果只是使用插入排序的话效率就并不高。所以总体来说，希尔排序的执行效率是要比插入排序高的。

import java.util.Arrays;

class Solution {
    // 交换数组元素位置
    public static void swap(int[] array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    public static void shellSort(int[] array){
        int gap = array.length >>> 1; // 希尔排序的初始增量
        while (gap>0){
            for (int i = 0; i < gap; i++) { //对根据增量划分的组执行插入排序

                // 一次排序一个增量组--插入排序
                for (int j = i+gap; j < array.length; j+=gap) {
                    int curItem = array[j]; // 待排序元素
                    int k = j - gap;
                    while (k>=i&&array[k]>curItem){
                        array[k+gap] = array[k];
                        k-=gap;
                    }
                    array[k+gap] = curItem;
                }

            }

            gap >>>= 1;
        }
    }

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

1.6 堆排序

堆排序的过程是首先构建一个大(小)顶堆，大顶堆首先是一棵完全二叉树，其次它保证堆中任意节点的值总是不大(小)于其父节点的值。

因为大顶堆中的最大元素肯定是根节点，所以每次取出根节点即为当前大顶堆中的最大元素，取出后剩下的节点再重新构建大顶堆，再取出根节点，再重新构建…重复这个过程，直到数据都被取出，最后取出的结果即为排好序的结果。

import java.util.Arrays;

class Solution {
    // 交换数组元素位置
    public static void swap(int[] array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    /**
     * 维护堆的性质
     * @param array 存储堆的数组
     * @param size 堆的大小
     * @param i 待维护节点的下标
     */
    public static void heapify(int[] array,int size,int i ){
        int largest = i;
        int lson = i*2+1;
        int rson = i*2+2;

        if(lson<size&&array[lson]>array[largest])
            largest = lson;
        if(rson<size&&array[rson]>array[largest])
            largest = rson;

        if(largest!=i){
            swap(array,largest,i);
            heapify(array,size,largest);
        }
    }


    public static void heapSort(int[] array,int size){
        // 建堆
        for (int i = size/2-1; i>=0 ; i--) { // 从最后一个元素的父节点开始维护
            heapify(array,size,i);
        }
        
        // 排序
        for (int i = size-1; i >=0 ; i--) {
            swap(array,i,0); // 将堆的最后一个元素和堆顶元素进行交换
            heapify(array,i,0); // 将堆顶元素移出堆，并维护堆顶元素的性质
        }
    }

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

1.7 归并排序

归并排序使用的是分治的思想，首先将数组不断拆分，直到最后拆分成两个元素的子数组，将这两个元素进行排序合并，再向上递归。不断重复这个拆分和合并的递归过程，最后得到的就是排好序的结果。

import java.util.Arrays;

class Solution {
    // 交换数组元素位置
    public static void swap(int[] array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    // 合并
    public static void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; // 临时数组
        int p1 = left;  // 标记左半区第一个未排序的元素
        int p2 = mid + 1; // 标记右半区第一个未排序的元素
        int k = 0; //临时数组元素的下标

        // 合并两个有序数组
        while (p1 <= mid && p2 <= right) {
            if (array[p1] <= array[p2]) {
                temp[k++] = array[p1++];
            } else {
                temp[k++] = array[p2++];
            }
        }
        // 把剩余的数组直接放到temp数组中
        while (p1 <= mid) {
            temp[k++] = array[p1++];
        }
        while (p2 <= right) {
            temp[k++] = array[p2++];
        }

        // 复制回原数组
        for (int i = 0; i < temp.length; i++) {
            array[i + left] = temp[i];
        }
    }


    public static void mergeSort(int[] array,int left,int right){
        //如果只有一个元素，那么就不需要继续划分
        //只有一个元素的区域，本生就是有序的，只需要被归并即可
        if(left<right){
            //找中间点，这里没有选择“(left + right) / 2”的方式，是为了防止数据溢出
            int mid = left + ((right - left) >>> 1);
            // 递归划分左半区
            mergeSort(array, left, mid);
            // 递归划分右半区
            mergeSort(array, mid + 1, right);
            // 对子数组进行合并
            merge(array, left, mid, right);
        }
    }

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

1.8 计数排序

计数排序会创建一个临时的数组，里面存放每个数出现的次数。比如一个待排序的数组是[2,4,1,2,5,3,4,8,7]，那么这个临时数组中记录的数据就是[0,1,2,1,2,1,0,1,1]。那么最后只需要遍历这个临时数组中的计数值就可以了。

import java.util.Arrays;

class Solution {
    // 交换数组元素位置
    public static void swap(int[] array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    public static int[] countingSort(int[] array,int left,int right){
        //记录待排序数组中的最大值
        int max = array[0];
        //记录待排序数组中的最小值
        int min = array[0];
        for (int item : array) {
            if (item > max) max = item;
            if (item < min) min = item;
        }


        //记录每个数出现的次数
        int[] temp = new int[max - min + 1];
        for (int item : array) {
            temp[item - min]++;
        }


        // 将结果复制回原数组
        int index = 0;
        for (int i = 0; i < temp.length; i++) {
            //当输出一个数之后，当前位置的计数就减一，直到减到0为止
            while (temp[i]-- > 0) {
                array[index++] = i + min;
            }
        }

        return array;
    }

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

1.9 桶排序

上面的计数排序在数组最大值和最小值之间的差值是多少，就会生成一个多大的临时数组，也就是生成了一个这么多的桶，而每个桶中就只插入一个数据。如果差值比较大的话，会比较浪费空间。那么我能不能在一个桶中插入多个数据呢？当然可以，而这就是桶排序的思路。桶排序类似于哈希表，通过一定的映射规则将数组中的元素映射到不同的桶中，每个桶内进行内部排序，最后将每个桶按顺序输出就行了。桶排序执行的高效与否和是否是稳定的取决于哈希散列的算法以及内部排序的结果。需要注意的是，这个映射算法并不是常规的映射算法，要求是每个桶中的所有数都要比前一个桶中的所有数都要大，这样最后输出的才是一个排好序的结果。比如说第一个桶中存1-30的数字，第二个桶中存31-60的数字，第三个桶中存61-90的数字...以此类推

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution {
    // 交换数组元素位置
    public static void swap(int[] array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }


    public static int[] bucketSort(int[] array,int left,int right){
        if (array == null || array.length < 2) {
            return array;
        }

        //记录待排序数组中的最大值
        int max = array[0];
        //记录待排序数组中的最小值
        int min = array[0];
        for (int i : array) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        //计算桶的数量（可以自定义实现）
        int bucketNumber = (max - min) / array.length + 1;
        List<Integer>[] buckets = new ArrayList[bucketNumber];
        //计算每个桶存数的范围（可以自定义实现或者不用实现）
        int bucketRange = (max - min + 1) / bucketNumber;

        for (int value : array) {
            //计算应该放到哪个桶中（可以自定义实现）
            int bucketIndex = (value - min) / (bucketRange + 1);
            //延迟初始化
            if (buckets[bucketIndex] == null) {
                buckets[bucketIndex] = new ArrayList<>();
            }
            //放入指定的桶
            buckets[bucketIndex].add(value);
        }
        int index = 0;
        for (List<Integer> bucket : buckets) {
            if (bucket == null) {
                continue;
            }
            
            //对每个桶进行内部排序，我这里使用的是快速排序，也可以使用别的排序算法，当然也可以继续递归去做桶排序
            bucket.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1-o2;
                }
            });
            
            //将不为null的桶中的数据按顺序写回到array数组中
            for (Integer integer : bucket) {
                array[index++] = integer;
            }
        }

        return array;
    }

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

1.10 基数排序

基数排序不是根据一个数的整体来进行排序的，而是将数的每一位上的数字进行排序。比如说第一轮排序，我拿到待排序数组中所有数个位上的数字来进行排序；第二轮排序我拿到待排序数组中所有数十位上的数字来进行排序；第三轮排序我拿到待排序数组中所有数百位上的数字来进行排序...以此类推。每一轮的排序都会累加上一轮所有前几位上排序的结果，最终的结果就会是一个有序的数列。

基数排序一般是对所有非负整数进行排序的，但是也可以有别的手段来去掉这种限制（比如都加一个固定的数或者都乘一个固定的数，排完序后再恢复等等）。基数排序和桶排序很像，桶排序是按数值的区间进行划分，而基数排序是按数的每一位的值进行划分。同时这两个排序都是需要依靠其他排序算法来实现的（如果不算递归调用桶排序本身的话）。基数排序每一轮的内部排序会使用到计数排序来实现，因为每一位上的数字无非就是0-9，是一个小范围的数，所以使用计数排序很合适。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution {
    // 交换数组元素位置
    public static void swap(int[] array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }


    public static void radixSort(int[] array) {
        //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
        int[][] bucket = new int[10][array.length];//很明显，基数排序使用了空间换时间

        //为了记录每个桶中实际存放了多少个数据，定义一个一维数组来记录每次放入数据的个数
        //比如bucketElementCounts[0]=3，意思是bucket[0]存放了3个数据
        int[] bucketElementCounts = new int[10];

        int digitOfElement = 0;//每次取出的元素的位数

        //找到数组中最大数的位数
        int max = 0;
        for (int i = 0; i < array.length; i++) {
            if (max < String.valueOf(array[i]).length()) {
                max = String.valueOf(array[i]).length();
            }
        }

        int index = 0;
        for (int i = 0, n = 1; i < max; i++, n *= 10) {
            //第i+1轮排序（针对每个元素的位进行排序处理）
            for (int j = 0; j < array.length; j++) {
                digitOfElement = array[j] / n % 10;//取出每个元素的位
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = array[j];//放入对应的桶
                bucketElementCounts[digitOfElement]++;
            }
            //按照桶的顺序（一维数组的下标取出数据），放入原来的数组
            index = 0;
            //遍历每一个桶，并将桶中数据放入原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中有数据，我们才放到原数组
                if (bucketElementCounts[k] != 0) {
                    //循环第k个桶，放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        array[index] = bucket[k][l];
                        index++;
                    }
                }
                bucketElementCounts[k] = 0;//置零!!!!!
            }
        }
    }

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

参考资料

1. 排序算法：快速排序【图解+代码】
2. 排序算法：堆排序【图解+代码】
3. [排序算法：希尔排序【图解+代码】]()
4. 排序算法：归并排序【图解+代码】
5. 十种经典排序算法总结
6. 基数排序(Java)