算法——排序

引言

本文整理了常见的排序算法，方便以后查阅。算法相关的文章均收录于<算法系列文章>。

排序算法

package bbm.sort;

/**
 * 排序接口
 *
 * @author bbm
 */
public interface Sorter {
    /**
     * Sort
     *
     * @param nums source data
     * @return sorted data
     */
    int[] sort(int[] nums);

    /**
     * print data
     *
     * @param nums data
     */
    default void print(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

桶排序

package bbm.sort;

import java.util.LinkedList;

/**
 * 前提：输入数据时均匀的独立的
 * 桶排的思想是根据数据的取值范围，将它们按照从小到大的顺序分到不同的桶中，在同一个桶内的数据再进行排序
 *
 * 平均时间复杂度: O(n + k)
 * 最差时间复杂度: O(n^2)
 * 时间复杂度: O(n + k) 能优化到 O(n)
 *
 * @author bbm
 */
public class BucketSorter implements Sorter {
    @Override
    public int[] sort(int[] nums) {
        LinkedList<Integer>[] buckets = new LinkedList[100000];
        for (int i = 0; i < nums.length; i++) {
            int bucket = nums[i] + 50000;
            if (buckets[bucket] == null) {
                buckets[bucket] = new LinkedList<>();
            }
            buckets[bucket].add(nums[i]);
        }
        int index = 0;
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] != null) {
                buckets[i].sort(Integer::compareTo);
                for (int data : buckets[i]) {
                    nums[index++] = data;
                }
            }
        }
        return nums;
    }
}

计数排序

package bbm.sort;

/**
 * 计数排序不需要进行数组数据的大小比较，在使用该排序方法时，我们需要知道数组 nums 的数据范围，本例中我们假设-50000 <= nums[i] <= 50000
 * 然后我们需要创建一个保存临时数据的数组 counts，保证对任意下标 x 都有 nums[x] = i, counts[i] = <nums 中小于 i 的元素的个数>
 * 然后，我们扫描待排序的数组，根据该数 i 在 counts 数组中的记录，可以得到 nums 中小于 i 的元素个数，也就得到 i 所处的正确位置
 *
 * 时间复杂度: O(n + k)
 * 空间复杂度: O(n + k) 能优化到 O(k)
 *
 * 我觉得在 counts 中没必要记录小于 i 的元素个数，只需要记录等于 i 的元素个数就够了，这时候我们只需要从左到右遍历 counts
 * 每当 number = counts[index] > 0 时，只需要将 number 个 index 推入 result 数组即可，理论上它和计数排序效率差不多
 * 具体参考 {@link CountingSorter#countingSort(int, int[])}
 *
 * @author bbm
 */
public class CountingSorter implements Sorter {

    @Override
    public int[] sort(int[] nums) {
        if (nums == null) {
            return null;
        }
        if (nums.length == 1) {
            return nums;
        }
        int[] counts = new int[100000];
        for (int data : nums) {
            counts[data + 50000] += 1;
        }
        return countingSort(nums, counts);
    }

    private int[] countingSort(int[] nums, int[] counts) {
        int[] result = new int[nums.length];
        for (int i = 1; i < counts.length; i++) {
            counts[i] = counts[i - 1] + counts[i];
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            result[counts[nums[i] + 50000] - 1] = nums[i];
            counts[nums[i] + 50000] -= 1;
        }
        return result;
    }

    private int[] countingSort(int size, int[] counts) {
        int[] result = new int[size];
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] > 0) {
                for (int j = 0; j < counts[i]; j++) {
                    result[index++] = i - 50000;
                }
            }
        }
        return result;
    }
}

堆排序

package bbm.sort;

/**
 * 堆排的思想是先将数组想象成一个完全二叉树，根节点是 index=0，它的两个子节点是 index=1 和 index=2, 如下图所示
 *      0
*      /\
 *    1  2
 *   /\  /\
 *  3 4 5 6
 * 在此基础上，我们将构建最大堆，所谓最大堆的特性是：每个节点都大于它的两个子节点，也就是说根节点是最大的数
 * 建立最大堆的思路是从 length / 2 号节点开始从下往上的检查各个节点是否大于其子节点，如果发现不满足，则交换节点的数据
 * 当遍历到根节点时，就完成了最大堆的建立
 * 基于最大堆的特性，我们知道根节点一定是最大的节点，所以我们将根节点和数组最后一个节点交换，然后将最后一个节点排除
 * 并从根节点出发重新修复剩余节点，让其满足最大堆的性质，重复上述过程直到数组被排除到只剩下一个节点时，整个数据就是有序的了
 *
 * 时间复杂度: O(n*log(n))
 * 时间复杂度: O(1)
 *
 * @author bbm
 */
public class HeapSorter implements Sorter {

    @Override
    public int[] sort(int[] nums) {
        if (nums == null) {
            return null;
        }
        if (nums.length == 1) {
            return nums;
        }
        buildMaxHeap(nums);
        heapSort(nums);
        return nums;
    }

    private void heapSort(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            maxHeap(nums, i, 0);
        }
    }

    private void buildMaxHeap(int[] nums) {
        for (int i = nums.length / 2; i >= 0; i--) {
            maxHeap(nums, nums.length, i);
        }
    }

    private void maxHeap(int[] nums, int size, int index) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int largest;
        if (left < size && nums[left] > nums[index]) {
            largest = left;
        } else {
            largest = index;
        }
        if (right < size && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != index) {
            int temp = nums[index];
            nums[index] = nums[largest];
            nums[largest] = temp;
            maxHeap(nums, size, largest);
        }
    }

}

插入排序

package bbm.sort;

/**
 * 插入排序将数组分为左侧和右侧，认为左侧是排好序的数组（起初左侧数组只包含一个元素，即下标 0 元素），右侧是待处理的数组
 * 然后从下标 1 开始处理右侧数组，将其依次与左侧数组中的每个元素进行比较，从而将其插入到合适的位置
 *
 * 时间复杂度: O(n^2)
 * 空间复杂度: O(1)
 *
 * @author bbm
 */
public class InsertSorter implements Sorter {

    @Override
    public int[] sort(int[] nums) {
        if (nums == null) {
            return new int[0];
        }
        if (nums.length < 2) {
            return nums;
        }
        // print(nums);
        for (int i = 1; i < nums.length; i++) {
            int tmp = nums[i];
            for (int j = i - 1; j >= 0; j--) {
                if (tmp < nums[j]) {
                    nums[j + 1] = nums[j];
                    nums[j] = tmp;
                }
            }
            // print(nums);
        }
        return nums;
    }
}

归并排序

package bbm.sort;

/**
 * 利用分治思想，将数组平均地划分为 2 段，然后对这两段递归地再向下划分，直到每段的长度都为 1 时（长度为 1 意味着已经有序），开始进行合并
 * 合并过程就是不断地从要合并的两段（有序）数组中找最小的数，然后放入一个新的排好序的数组中
 *
 * 时间复杂度: O(n*log(n))
 * 空间复杂度: O(n)
 *
 * @author bbm
 */
public class MergeSorter implements Sorter {
    @Override
    public int[] sort(int[] nums) {
        if (nums == null) {
            return null;
        }
        if (nums.length < 2) {
            return nums;
        }
        return sort(nums, 0, nums.length);
    }

    private int[] sort(int[] nums, int p, int r) {
        if (p < r) {
            if (r - p >= 2) {
                // 当前待处理的数组长度大于 2，进行递归拆分
                int q = (p + r) / 2;
                sort(nums, p, q);
                sort(nums, q, r);
                merge(nums, p, q, r);
            } else {
                // 当前待处理的数组长度等于 2，直接进行合并
                if (nums[p] > nums[r - 1]) {
                    int tmp = nums[r - 1];
                    nums[r - 1] = nums[p];
                    nums[p] = tmp;
                }
            }
        }
        return nums;
    }

    private void merge(int[] nums, int p, int q, int r) {
        // 复制左右两个数组，复制完成后，nums 的 [p, r) 段就作为合并之后的 result 数组
        int[] leftArray = subArray(nums, p, q);
        int[] rightArray = subArray(nums, q, r);
        int leftIndex = 0;
        int rightIndex = 0;
        for (int i = p; i < r; i++) {
            if (leftArray.length <= leftIndex) {
                // 左数组已经为空，将右数组的数据按序添加到 result 中
                nums[i] = rightArray[rightIndex];
                rightIndex++;
            } else if (rightArray.length <= rightIndex) {
                // 右数组已经为空，将左数组的数据按序添加到 result 中
                nums[i] = leftArray[leftIndex];
                leftIndex++;
            } else if (leftArray[leftIndex] < rightArray[rightIndex]) {
                // 左数组当前处理的数较小，将这个较小的数据添加到 result 中
                nums[i] = leftArray[leftIndex];
                leftIndex++;
            } else {
                // 右数组当前处理的数较小，将这个较小的数据添加到 result 中
                nums[i] = rightArray[rightIndex];
                rightIndex++;
            }
        }
    }

    private int[] subArray(int[] nums, int p, int q) {
        int[] result = new int[q - p];
        for (int i = 0; p < q; i++) {
            result[i] = nums[p];
            p++;
        }
        return result;
    }
}

快速排序

package bbm.sort;

/**
 * 快排使用了分治的思想，它每次选取要处理的数组中最厚的一个元素作为主元素，然后遍历整个数组，利用下标来将数组划分成左右两个部分
 * 左部都是比主元素小的数据，右部都是比主元素大的数据，当处理完除主元素外的其他所有元素时，左部的末尾就是主元素在排好序的数组中应该处于的位置
 * 也就是说每一轮上述处理过程，都将为一个主元素找到合适的位置，这个位置就是排序完成之后该元素该在的位置，很明显我们需要把主元素放到这个位置上来
 * 然后递归的处理主元素左右两部分数组，直到左右数组的大小都为 1 为止
 * 总结成一句话就是：每轮迭代都会为一个元素找到正确的位置
 *
 * 很显然，如果数组本来是逆序的，当我们选最后一个元素作为主元素时，划分出来的左部数组为空，右部数组为 size - 1，这样的话快排会退化成 O(n^2)
 * 为了解决这个问题，我们可以引入随机化的过程，不是总选取最后一个节点作为主元素，而是随机选择一个元素，这样比较平衡
 * 详见 {@link QuickSorter#randomPartition(int[], int, int)}
 * 不过我在 LeetCode 上跑测试集发现不进行随机化反而更快，可能他们的已经足够随机化了，我们再进行随机化反而增加了消耗
 *
 * 平均时间复杂度: O(n*log(n))
 * 最差时间复杂度: O(n^2)
 * 时间复杂度: O(1)
 *
 * @author bbm
 */
public class QuickSorter implements Sorter {

    @Override
    public int[] sort(int[] nums) {
        if (nums == null) {
            return null;
        }
        if (nums.length == 1) {
            return nums;
        }
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int p, int r) {
        if (p < r) {
            int q = partition(nums, p, r);
            quickSort(nums, p, q - 1);
            quickSort(nums, q + 1, r);
        }
    }

    private int randomPartition(int[] nums, int p, int r) {
        int i = (int) (Math.random() * (r - p)) + p;
        int temp = nums[i];
        nums[i] = nums[r];
        nums[r] = temp;
        return partition(nums, p, r);
    }

    private static int partition(int[] nums, int p, int r) {
        int pivot = nums[r];
        int leftEnd = p - 1;
        for (int rightEnd = p; rightEnd < r; rightEnd++) {
            if (nums[rightEnd] < pivot) {
                leftEnd++;
                int temp = nums[leftEnd];
                nums[leftEnd] = nums[rightEnd];
                nums[rightEnd] = temp;
            }
        }
        leftEnd++;
        int temp = nums[leftEnd];
        nums[leftEnd] = nums[r];
        nums[r] = temp;
        return leftEnd;
    }
}

基数排序

package bbm.sort;

/**
 * 基数排序的思想是将数据按照 10 进制划分为多个位（这里我们假定最大数据的位数是 d = 5），然后从低位开始按照位大小进行排序
 * 因为在数学中, 数位越高,数位值对数的大小的影响就越大, 所以如果我们用从高位到低位排序的话，会影响高位已经排好的大小关系
 * 而从低位向高位排序的话，低位已经排好的顺序会被一直保持住，考虑 47 43 54 这三个数，按照个位排序后是 43 54 47，然后按 10 位排序时，
 * 43 和 47 的顺序保持 43 47 54，而如果我们从高到低位排序时，就会变成 47 43 54，接下来我们要按个位为他们排序，就不得不将它们分成不同的组
 * 因为如果分在同一组的话，按个位数排序的话会变成 43 54 47，其中 54 和 47 的大小关系被破坏
 *
 * 时间复杂度: O(n*k)
 * 空间复杂度: O(n*k) 能优化到 O(n+k)
 *
 * @author bbm
 */
public class RadixSorter implements Sorter {
    @Override
    public int[] sort(int[] nums) {
        int[][] sort = new int[20][nums.length];
        for (int i = 1; i < 6; i++) {
            int[] numbers = new int[20];
            int mod = (int) (Math.pow(10, i));
            int div = (int) (Math.pow(10, i - 1));
            for (int num : nums) {
                int digit = num % mod / div;
                sort[digit + 10][numbers[digit + 10]] = num;
                numbers[digit + 10] += 1;
            }
            int index = 0;
            for (int k = 0; k < 20; k++) {
                for (int l = 0; l < numbers[k]; l++) {
                    nums[index] = sort[k][l];
                    index++;
                }
            }
        }
        return nums;
    }
}

测试代码

package bbm.sort;

import java.util.Arrays;
import java.util.Random;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * @author bbm
 */
public class SorterTest {

    @Test
    public void testSort() {
        Sorter sorter = new BucketSorter();
        doTest(sorter);
        sorter = new CountingSorter();
        doTest(sorter);
        sorter = new HeapSorter();
        doTest(sorter);
        sorter = new InsertSorter();
        doTest(sorter);
        sorter = new MergeSorter();
        doTest(sorter);
        sorter = new QuickSorter();
        doTest(sorter);
        sorter = new RadixSorter();
        doTest(sorter);
    }

    private void doTest(Sorter sorter) {
        int dataSize = 10000;
        long time1 = 0;
        long time2 = 0;
        // 这里跑了很多次是为了减弱 JIT 的影响
        for (int x = 0; x < 100; x++) {
            int[] data = new int[dataSize];
            int[] data2 = new int[dataSize];
            Random rand = new Random(System.currentTimeMillis());
            for (int i = 0; i < dataSize; i++) {
                data[i] = rand.nextInt(dataSize);
                data2[i] = data[i];
            }
            long start = System.currentTimeMillis();
            Arrays.sort(data);
            time1 += System.currentTimeMillis() - start;
            start = System.currentTimeMillis();
            int[] result = sorter.sort(data2);
            time2 += System.currentTimeMillis() - start;
            for (int i = 0; i < dataSize; i++) {
                assertEquals(data[i], result[i]);
            }
        }
        System.out.println(sorter.getClass().getSimpleName() + ": jdk speeds: " + time1 + " ms, my algorithm speeds " + time2 + " ms");
    }
}

参考内容

[1] 《算法导论》
[2] 排序算法汇总