【每日算法Day 82】一文回顾11种排序算法

作为基础中的基础，各种排序算法的思想我们应该熟稔于心，更应该熟练比较它们的复杂度、稳定性和适用场景等特点。

基于比较的O(n^2)排序

1. 冒泡排序

冒泡排序的核心思想是，迭代对数组中相邻的数进行两两比较，并在需要时进行交换，直到一次迭代过程中发现没有数被交换过为止。不需要额外的空间，时间复杂度方面最坏情况是数组完全是逆序的O(n^2)，最好情况是数组已经排序O(n)，平均时间复杂度为O(n^2)。

public void bubbleSort(int[] array){
    while(true){
        boolean swapped = false;
        for(int i = 1; i < array.length; i++){
            if(array[i - 1] > array[i]){
                swapped = true;
                swap(array, i-1, i);
            }
        }
        if(!swapped)
            break;
    }
}

2. 选择排序

选择排序的核心思想是，每次选择当前待处理的区间中最小的值和区间的首位进行交换，然后缩小待处理的区间继续这一过程，直到待处理区间长度缩减为1。排序过程需要O(1)的空间，时间复杂度总为O(n^2)。

public void selectSort(int[] array){
    int start = 0;
    while(start < array.length - 1){
        int minIndex = start, min = array[start];
        for(int i = start + 1;i < array.length; i++){
            if(array[i] < min){
                min = array[i];
                minIndex = i;
            }
        }
        swap(array, start, minIndex);
        start++;
    }
}

3. 插入排序

插入排序的核心思想是，每次从数组中移除一个数并将器插入到已经排序的序列的正确位置，直到所有输入都已经插入。和冒泡排序一样，不需要额外的空间，时间复杂度方面最坏情况是数组完全是逆序的O(n^2)，最好情况是数组已经排序O(n)，平均时间复杂度为O(n^2)。

public void insertSort(int[] array){
    for(int i = 1; i < array.length; i++){
        for(int j = i; j > 0 && array[j] < array[j - 1]; j--){
            swap(array, j, j - 1);
        }
    }
}

4. 希尔排序

希尔排序的核心思想是，每次比较和交换数组中每个距离为gap的元素；每轮比较后减小gap再进行比较交换直至gap为1，此时希尔排序与插入排序相同，但是前面的轮已经极大减少了需要交换的元素个数。

希尔排序空间复杂度为O(1)，最好情况下时间复杂度约为O(n^1.3)，最坏时间复杂度为O(n^2)，平均时间复杂度在O(nlogn)~O(n^2)之间。希尔排序是所有时间复杂度为O(n^2)的算法中最快的，对中等规模的序列非常有效。

public void shellSort(int[] array){
    int n = array.length;
    for(int gap = n / 2; gap > 0; gap /= 2){
        for(int i = gap; i < n; i++){
            for(int j = i; j - gap >= 0 && array[j - gap] > array[j]; j -= gap){
                swap(array, j - gap, j);
            }
        }
    }
}

基于比较的O(nlogn)排序

5. 归并排序

归并排序的核心思想是，将数组递归地划分为两个子数组，直到划分地子数组长度为1为止，最后再将这些子数组递归合并。归并排序在合并的过程中需要O(n)的临时空间来合并两个有序的数组。时间复杂度为O(nlogn)。

public void mergeSort(int[] array){
    mSort(array,0, array.length - 1);
}

private void mSort(int[] array, int left, int right){
    if(left == right) return;
    int mid = left + ((right - left) >> 1);
    mSort(array, left, mid);
    mSort(array, mid + 1, right);

    //下面就是在已知两个已经排序的部分的左右边界的情况下进行合并
    int[] temp = new int[right - left + 1];
    int leftPointer = left, rightPointer = mid + 1, index = 0;
    while(leftPointer <= mid && rightPointer <= right){
        if(array[leftPointer] > array[rightPointer])
            temp[index++] = array[rightPointer++];
        else
            temp[index++] = array[leftPointer++];
    }
    while(leftPointer <= mid)
        temp[index++] = array[leftPointer++];
    while(rightPointer <= right)
        temp[index++] = array[rightPointer++];
    System.arraycopy(temp, 0, array, left, right - left + 1);
}

6. 快速排序

快速排序的核心思想是，选取一个枢轴pivot，通过不断交换把数组分为小于等于枢轴的部分和大于枢轴的部分，再对剩余的两部分递归进行该操作。快速排序不需要额外的O(n)空间，但是不稳定的。最坏情况：如果数组被枢轴分为了大小严重不等的两部分（例如数组已经是正序或逆序的，枢轴的选取策略为选取数组的第一个或最后一个元素）时间复杂度就会变为O(n^2)；最好情况是每次数组都被数组分为了大小相等的两部分，时间复杂度为O(nlogn)；平均时间复杂度为O(nlogn)。

public void quickSort(int[] array){
    qSort(array, 0, array.length - 1);
}

private void qSort(int[] array, int left, int right){
    if(left >= right) return;
    int pivot = array[right], firstLargerIndex = left;
    for (int i = left; i < right; i++) {
        if (array[i] < pivot)
            swap(array, i, firstLargerIndex++);
    }
    swap(array, firstLargerIndex, right);
    qSort(array, left, firstLargerIndex - 1);
    qSort(array, firstLargerIndex + 1, right);
}

7. 二分插入排序

JDK中Arrays.sort()方法底层对于小规模的数组，使用了一种名为binarySort()的方法（准确来说叫binary insertion sort）。刚开始我看到其中也有名为pivot的变量以为是快排，后来发现更像是插入排序的二分优化版本。对于更一般的大数组，其底层使用的是DualPivotQuickSort，在很多其他快排算法的最差情况下依然能获得较好的性能。

在插入排序中，假定从start~index-1的所有元素是有序的，那么面对第index个位置上的元素x，在它左边的元素比它大时，我们会两两比较和交换它们直到其左边元素小于等于x。在二分插入算法中，先用pivot变量保存x，再用二分查找直接找到x要插入的位置i，最后把i~index-1的元素拷贝至i+1~index上，再把pivot赋值给第i个位置。这时就完成了插入排序，index++，开始下一轮处理。

public void binarySort(int[] array){
    for(int i = 1; i < array.length; i++){
        int pivot = array[i];
        int left = 0, right = i - 1;
        if(pivot > array[right]) continue;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(array[mid] > pivot)
                right = mid - 1;
            else if(array[mid] <= pivot)
                left = mid + 1;
        }
        //这里JDK还根据i-left的长度作了优化，长度为1和2时不调用该函数直接交换值
        System.arraycopy(array, left, array, left + 1, i - left);
        array[left] = pivot;
    }
}

该方法适用于对规模不大的数组进行排序，只需要进行O(nlogn)次比较，但在最坏情况下可能要进行O(n^2)次数据移动。如果数组开始的一部分已经排序那么该算法会更快。

8. 堆排序

堆排序在前面的特殊数据结构中提到过，一般我们需要O(n)的空间构建堆，当然可以用传入的数组构建堆。但是堆以数组的形式存储时，不能保证数组元素从左向右是有序的。通过上浮、下沉这两个关键操作能在O(logn)时间内维护单个元素在堆内的正确位置上，插入和删除元素时都会调用上浮或下沉操作，保证数组中第一个元素始终是数组中最大或最小的时间平均为O(nlogn)。

public void heapSort(int[] array) {
    int n = array.length;
    //建堆
    for (int i = n / 2; i >= 0; i--) {
        sink(array, i, n);
    }

    for (int i = n - 1; i > 0; i--) {
        //交换堆顶的最大值到数组尾部
        swap(array, i, 0);
        //对剩余的n-1大小的堆的堆顶进行下沉操作以维护堆的性质
        sink(array, 0, i);
    }
}

private void sink(int[] array, int i, int n) {
    while (i * 2 + 2 < n) {
        int leftChild = i * 2 + 1, rightChild = i * 2 + 2;
        int maxChild = Math.max(array[leftChild], array[rightChild]);
        if (maxChild > array[i]) {
            if (maxChild == array[leftChild]) {
                swap(array, leftChild, i);
                i = leftChild;
            } else {
                swap(array, rightChild, i);
                i = rightChild;
            }
        } else {
            break;
        }
    }
}

非基于比较的排序算法

非基于比较的排序一般都是对元素作某种假设限制的线性排序。

9. 计数排序

计数排序要求元素必须是有确定范围的整数，当一共有n个元素，元素中最大值减最小值为k时，计数排序的时间复杂度为O(n+k)，用于计数的数组C大小为k+1。所以在数据范围差很大时计数排序就不适用。其步骤为：

• 找出待排序的数组中最大和最小的元素
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

public void countSort(int[] array){
    //找区间边界
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for(int num : array){
        min = Math.min(min, num);
        max = Math.max(max, num);
    }

    //计数
    int k = max - min;
    int[] count = new int[k + 1];
    for(int num : array){
        count[num - min]++;
    }

    //反向填充
    int index = 0;
    for(int i = 0; i < k + 1; i++){
        while(count[i]-- > 0)
            array[index++] = i + min;
    }
}

10. 桶排序

桶排序是计数排序的升级版本，它利用了函数的映射关系，高效与否在于使用的映射函数。所以在空间充足的情况下尽量增加桶的数量（听起来是不是像哈希数组扩容减少哈希碰撞？），同时映射函数要将输入的N数据均匀地分配到K个桶中。之后，再选择使用一种排序算法对每个桶中的元素进行排序。

示例：

输入：array[]为存储了200个0~99之间的数的数组
算法描述：
1.创建10个桶，第i个桶存储10*i~10*i+9的数
    ArrayList<Integer>[] buckets = new ArrayList[10];
    for (int i = 0; i < 10; i++) {
        buckets[i]=new ArrayList<>();
    }
2.用取模的方式放入桶中
3.对每个桶选择一种排序算法进行排序。

11. 基数排序

基数排序是一种非比较型整数排序算法（不能直接排序负数，需要加上偏移），其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序也使用了桶的概念，不过固定只有10个桶0~9（十进制的基数radix就是10），并且桶中不需要专门排序。假设要排序的数中最大数字一共有k位十进制位，那么要进行k轮。第i轮中，按照从低到高第i位的数字x，把整数放入第x个桶中；接下来从第0个桶到第9个桶依次按照桶中元素的插入顺序（先进先出，是不是听起来像队列，其实不用队列手动控制动态数组也行，ArrayDeque底层就是数组，用起来方便一些）反向填充回原数组中；继续下一轮的处理。

如果数组有n个元素，最大数字一共有k位十进制位，那么基数排序的时间复杂度为O(n*k)，空间复杂度为O(n)。

public void radixSort(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int num : array)
        max = Math.max(max, num);

    Queue<Integer>[] buckets = new Queue[10];
    for (int i = 0; i < 10; i++) {
        buckets[i] = new ArrayDeque<>();
    }

    int divider = 1;
    //一共有max的位数即k轮
    while (max != 0) {
        max /= 10;
        for (int num : array) {
            buckets[(num / divider) % 10].offer(num);
        }

        //反向填充回array，O(n)的操作
        int index = 0;
        for (Queue<Integer> bucket : buckets) {
            while (!bucket.isEmpty()) {
                array[index++] = bucket.poll();
            }
        }
        divider *= 10;
    }
}