vlambda博客
学习文章列表

                                                                            文 | Alex

图片来源 | Pexels

在计算机科学与数学中，排序算法 (Sorting Algorithm) 是一种能将一串数据按照特定排序方式进行排列的计算方法。有效的排序算法在一些其它常用的算法(如搜索算法)中是十分重要的，理解和掌握排序算法对于我们分析这些常用算法的内部实现会很有帮助。并且排序算法中用到的一些 tricks 也可以为我们在实现其它算法时提供借鉴。

首先，让我们从整体上认识一下这些排序算法，下表中归纳了各个排序算法在时间复杂度，空间复杂度，排序方式以及稳定性等各个方面的指标，这些指标是在进行排序算法选择时的重要理论依据。

图 1.1 sorting algorithm

其中时空复杂度分别指排序算法所消耗的时间（一般为比较的次数）和空间（一般为消耗的内存）与待排序数组长度之间的渐进性函数关系，通常用大 O来表示。对于大多数排序算法而言其时空复杂度是相对确定的，但也有一些排序算法，根据其实现方式的不同，其时空复杂度是在动态变化的，比如希尔排序的时间复杂度会随步长序列的选择而变化，所以在计算复杂度时，要根据代码的实现去动态分析。

排序方式有两种，In-Place 表示可以在原数组的基础上通过位置交换来达到排序的目地，而 Out-Place 则表示在排序时需要借助额外的内存来存储数组元素以达到排序的目的。注意它与空间复杂度不完全等同，比如快速排序的空间复杂度为 O(log n)，但它主要是栈的空间消耗，并没有借助额外的内存来存储数组，仅是在原数组的基础上完成的排序，所以它是一种 In-Place 方式的排序算法。

稳定性是指，如果排序前后，相同 key 值元素的相对位置没有发生变化，则该排序是稳定排序，否则为不稳定排序。

注：表中时空复杂度中的 k 在不同的排序算法中具有不同的含义，详见具体算法的分析。

基本版原理：从左至右依次进行数组元素的两两比较，并将最大的元素冒泡至最右边，此为 1 轮冒泡过程，然后重复该过程 n 次，排序完成，其中 n 为数组长度。

优化版原理：在基本版里，如果数组已经排好序，时间复杂度并不是最优的 O(n)，为了降低其复杂度，优化版记录了数组中最后一次交换的位置，则此位置后的数组已经有序，则每次只需遍历到该位置即可。

publicclass BubbleSort {
    /**
     * 基本版的冒泡排序
     *
     * @param nums
     */
    public void buubleSort(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return;
        for (int i = len - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    /**
     * 优化版的冒泡排序
     *
     * @param nums
     */
    public void bubbleSortOptimize(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return;
        int lastSwapPos = len - 1;// 最后一次交换的位置
        while (lastSwapPos != 0) {// 为 0 时循环终止，排序完成
            int pos = 0;
            for (int i = 0; i < lastSwapPos; i++) {
                if (nums[i] > nums[i + 1]) {
                    swap(nums, i, i + 1);
                    pos = i;// 每发生一次交换，则记录交换的位置
                }
            }
            lastSwapPos = pos;// 更新最后一次交换的位置
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

图 2.2.1 Bubble Sort

原理：从左至右选出数组中的最小的元素，并与最左边未排好序的第一个元素进行交换，此为 1 次选择排序过程，然后重复该过程 n 次，排序完成，其中 n为数组长度。

publicclass SelectionSort {
    /**
     * 选择排序
     *
     * @param nums
     */
    public void selectionSort(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return;
        for (int i = 0; i < len; i++) {
            int index = i; // 最小元素索引
            for (int j = i + 1; j < len; j++) {
                if (nums[j] < nums[index])
                    index = j;
            }
            swap(nums, i, index); // 元素交换
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

图 3.2.1 Selection Sort

原理：遍历数组中的每个元素，对于该元素，其左边的数组元素已经排好序，只需将其插入到左边序列对应的位置即可，亦即从右至左遍历该元素左边的序列，并将该元素与比之大的元素进行位置交换，然后重复该过程 n 次，排序完成，其中 n 为数组长度。

publicclass InsertionSort {
    /**
     * 插入排序
     *
     * @param nums
     */
    public void insertionSort(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return;
        for (int i = 0; i < len; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j - 1])
                    swap(nums, j, j - 1);
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

图 4.2.1 Insertion Sort

原理：希尔排序是插入排序的一种更为高效的改进版本，可以将它理解为一种分组插入排序法。首先根据设定的步长 step，它将待排序的数组分为若干个子序列，然后分别对每个子序列进行插入排序，修改步长，重复上面的操作直至步长为 1，排序完成。其中步长的选择有多种方式，这里使用了较为常用的 Shell 步长生成方式， 即 step=n/(2^i)。

publicclass ShellSort {
    /**
     * 希尔排序
     *
     * @param nums
     */
    public void shellSort(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return;
        for (int step = len / 2; step >= 1; step /= 2) {
            for (int i = step; i < len; i++) {
                int j = i - step, tmp = nums[i];
                while (j >= 0 && nums[j] > tmp) {
                    nums[j + step] = nums[j];
                    j -= step;
                }
                nums[j + step] = tmp;
            }
        }
    }
}

图 5.2.1 Shell Sort

递归版原理：将待排序长度为 n 的数组分为两个长度为 n/2 的子序列，然后对这两个子序列分别进行归并排序，最后将排好序的两个子序列进行合并形成排好序的数组。由于子序列的合并不能在原数组直接进行，所以需要长度为 n 的辅助存储空间在子序列合并时使用。

迭代版原理：根据归并排序的思想，先将原数组分为不可再分的子序列，然后再逐子序列进行合并。所以迭代版归并排序中首先设定一个排序区间长度 block，目的是将原数组分为 n/block 个子序列，每个序列的长度为 block，然后对每两个相邻的长度为 block 的序列进行排序。初始时 block 大小设为 1，在随后的循环的过程中每次增加 1 倍，当 block 大于等于 n/2 时，排序完成。

publicclass MergeSort {
    /**
     * 递归版归并排序
     *
     * @param nums
     * @param start 起始位置
     * @param end   结束位置
     * @param extra 辅助的存储空间
     */
    public void mergeSort(int[] nums, int start, int end, int[] extra) {
        int len = nums.length;
        if (len <= 1 || start >= end)
            return;
        int middle = (start + end) / 2;
        // 子序列 1 从 start-middle
        mergeSort(nums, start, middle, extra);
        // 子序列 2 从 middle+1-end
        mergeSort(nums, middle + 1, end, extra);
        // 子序列 1 和 2 进行合并
        merge(nums, start, middle, end, extra);
    }

    /**
     * 子序列合并操作
     *
     * @param nums
     * @param start-middle 子序列 1
     * @param middle+1-end 子序列 2
     * @param extra
     */
    public void merge(int[] nums, int start, int middle, int end, int[] extra) {
        int left = start, right = middle + 1;
        int index = start;
        // 将两个子序列的元素值进行比较，从小到大拷贝进辅助数组
        while (left <= middle && right <= end) {
            if (nums[left] < nums[right]) {
                extra[index++] = nums[left++];
            } else {
                extra[index++] = nums[right++];
            }
        }
        // 如果两个子序列的任一个还有元素未拷贝，则继续拷贝
        while (left <= middle)
            extra[index++] = nums[left++];
        while (right <= end)
            extra[index++] = nums[right++];
        // 将合并后的元素重新拷贝回原数组
        for (int i = start; i <= end; i++) {
            nums[i] = extra[i];
        }
    }

    /**
     * 迭代版归并排序
     *
     * @param nums
     * @param extra 辅助的存储空间
     */
    public void mergeSortIterator(int[] nums, int[] extra) {
        int len = nums.length;
        if (len <= 1)
            return;
        // 步长 block
        for (int block = 1; block < len; block = block * 2) {
            // 每两个相邻的长度为 block 的序列进行排序
            for (int start = 0; start < len; start = start + block * 2) {
                int left = start, middle = (start + block) < len ? (start + block) : len,
                        end = (start + block * 2) < len ? (start + block * 2) : len;
                int right = middle, index = start;
                while (left < middle && right < end) {
                    if (nums[left] < nums[right]) {
                        extra[index++] = nums[left++];
                    } else {
                        extra[index++] = nums[right++];
                    }
                }
                while (left < middle)
                    extra[index++] = nums[left++];
                while (right < end)
                    extra[index++] = nums[right++];
                for (int i = start; i < end; i++)
                    nums[i] = extra[i];
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

图 6.2.1 Merge Sort

递归版原理：首先，选取一个元素作为基准 pivot，将小于该基准的元素放在其左边，大于该基准的元素放在其右边，该基准位于中间位置，称为分区（partition）操作。然后递归地分别对左右两边的元素进行快速排序。根据所选基准元素位置的不同，源码中分别实现了选取第一个元素、最后一个元素及中间元素作为基准的递归快速排序，原理相通，但实现上略有不同，需要注意。

迭代版原理：与递归版的原理相似，只不过需要借助栈来对待排序序列的起始位置和结束位置进行保存，还需要借助一个 Element 类来标识待排序序列的起始和结束位置。首先入栈全局数组的位置即 0~n-1，然后访问该栈，将出栈序列进行排序，并将新的位置信息入栈，重复此过程，直至栈空，排序完成。

import java.util.LinkedList;

publicclass QuickSort {
    /**
     * 选择第一个元素作为基准的递归快排
     *
     * @param nums
     * @param start 起始位置
     * @param end   结束位置
     */
    public void quickSortStart(int[] nums, int start, int end) {
        int len = nums.length;
        if (len <= 1 || start >= end)
            return;
        int left = start, right = end;
        int pivot = nums[left];
        /*
         * 每次循环先从右至左遍历，找到比基准元素小的第一个元素， 然后从左至右遍历，
         * 找到比基准元素大的第一个元素， 最后交换两个元素的位置，循环终止时 left==right，
         * 且 right 指向最后一个小于该基准元素的位置
         */
        while (left < right) {
            while (left < right && nums[right] >= pivot)
                right--;
            while (left < right && nums[left] <= pivot)
                left++;
            swap(nums, left, right); // when left == right;
        }
        // 交换基准元素与最后一个小于基准的元素的位置
        swap(nums, start, right);
        quickSortStart(nums, start, right - 1);
        quickSortStart(nums, right + 1, end);
    }

    /**
     * 选择最后一个元素作为基准的递归快排
     *
     * @param nums
     * @param start 起始位置
     * @param end   结束位置
     */
    public void quickSortEnd(int[] nums, int start, int end) {
        int len = nums.length;
        if (len <= 1 || start >= end)
            return;
        int left = start, right = end;
        int pivot = nums[end];
        /*
         * 每次循环先从左至右遍历，找到比基准元素大的第一个元素， 然后从右至左遍历，
         * 找到比基准元素小的第一个元素， 最后交换两个元素的位置，循环终止时 left==right，
         * 且 left 指向第一个大于该基准元素的位置
         */
        while (left < right) {
            while (left < right && nums[left] <= pivot)
                left++;
            while (left < right && nums[right] >= pivot)
                right--;
            swap(nums, left, right);
        }
        // 交换基准元素与第一个大于基准的元素的位置
        swap(nums, left, end);
        quickSortEnd(nums, start, left - 1);
        quickSortEnd(nums, left + 1, end);
    }

    /**
     * 选择中间位置元素作为基准的递归快排
     *
     * @param nums
     * @param start 起始位置
     * @param end   结束位置
     */
    public void quickSortMiddle(int[] nums, int start, int end) {
        int len = nums.length;
        if (len <= 1 || start >= end)
            return;
        int left = start, right = end;
        int middle = (left + right) / 2;
        int pivot = nums[middle];
        // 注意与以上两种方法的不同 left <= right 而非 <
        while (left <= right) {
            // nums[left] < pivot 而非 <= , nums[right] > pivot 而非 >=
            while (left <= right && nums[left] < pivot)
                left++;
            while (left <= right && nums[right] > pivot)
                right--;
            // 需要判断因为 left 可能大于 right
            if (left <= right) {
                swap(nums, left, right);
                // 需要有，因为遇到等于 pivot 的元素时会陷入死循环
                left++;
                right--;
            }
        }
        quickSortMiddle(nums, start, right);
        quickSortMiddle(nums, left, end);
    }

    class Element {
        int start, end;

        public Element(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    /**
     * 迭代版快排
     *
     * @param nums
     */
    public void quickSortIterator(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return;
        LinkedList<Element> s = new LinkedList<Element>();
        s.push(new Element(0, len - 1));
        while (!s.isEmpty()) {
            Element e = s.pop();
            int start = e.start, end = e.end;
            int left = start, right = end;
            if (left >= right)
                continue;
            int pivot = nums[left];
            while (left < right) {
                while (left < right && nums[right] >= pivot)
                    right--;
                while (left < right && nums[left] <= pivot)
                    left++;
                swap(nums, left, right);
            }
            swap(nums, start, right);
            s.push(new Element(start, right - 1));
            s.push(new Element(right + 1, end));
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

图 7.2.1 Quick Sort

原理：首先将待排序数组构建为大小为 n 的 最大（小）堆，然后将最大的堆顶元素与数组最后一个元素交换，将最大的元素放在最后一个位置，接下来不断调整最大堆并进行与上面相同的操作，此时堆的大小为 n-1 并依次递减，直至为 0 时，排序完成。

publicclass HeapSort {
    /**
     * 最大堆排序
     *
     * @param nums
     */
    public void heapSortMax(int[] nums) {
        int len = nums.length;
        // 建堆操作
        for (int i = (len - 1) / 2; i >= 0; i--) {
            maxHeap(nums, i, len);
        }
        // 排序操作
        for (int i = 0; i < len; i++) {
            swap(nums, 0, len - i - 1);
            maxHeap(nums, 0, len - i - 1);
        }
    }

    /**
     * 最大堆调整操作
     *
     * @param nums
     * @param parent 父节点
     * @param len    堆的大小
     */
    public void maxHeap(int[] nums, int parent, int len) {
        // 左子节点
        int left = parent * 2 + 1;
        if (left > len - 1)
            return;
        int right = left + 1;
        int max = left;
        if (right <= len - 1 && nums[left] < nums[right])
            max = right;
        if (nums[parent] < nums[max]) {
            swap(nums, parent, max);
            maxHeap(nums, max, len);
        }
    }

    /**
     * 最小堆排序
     *
     * @param nums
     */
    public void heapSortMin(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return;
        // 建堆操作
        for (int i = (len - 1) / 2; i >= 0; i--) {
            minHeap(nums, i, len);
        }
        // 排序操作
        for (int i = 0; i < len; i++) {
            swap(nums, 0, len - 1 - i);
            minHeap(nums, 0, len - 1 - i);
        }
    }

    /**
     * 最小堆调整操作
     *
     * @param nums
     * @param parent 父节点
     * @param len    堆的大小
     */
    public void minHeap(int[] nums, int parent, int len) {
        int left = parent * 2 + 1;
        if (left > len - 1)
            return;
        int right = left + 1;
        int min = left;
        if (right <= len - 1 && nums[right] < nums[left])
            min = right;
        if (nums[parent] > nums[min]) {
            swap(nums, parent, min);
            minHeap(nums, min, len);
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

图 8.2.1 Heap Sort

原理：找出待排序数组中最小和最大的元素，统计每个元素出现的次数并存入数组 count 中，然后累加所有的计数（count 数组中的第一个元素开始，每一项和前一项相加并存入该项），能够得出每个元素在原数组中的最终位置，最后考虑算法的稳定性，反向填充目标数组（倒序遍历原数组），将 nums 中的每个元素放入新数组 extra 中，详见稳定版计数排序。当不考虑稳定性时，可以省略辅助数组 extra，遍历数组 count，按顺序将元素放回原数组，详见优化版计数排序。

publicclass CountingSort {
    /**
     * 稳定版计数排序
     *
     * @param nums
     * @return int[]
     */
    publicint[] countingSort(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return nums;
        int[] extra = newint[len];
        int min = nums[0], max = nums[0];
        for (int i = 1; i < len; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        int k = max - min + 1;
        int[] count = newint[k];
        // 计数
        for (int i = 0; i < len; i++) {
            count[nums[i] - min]++;
        }
        // 计数累加
        for (int i = 1; i < k; i++) {
            count[i] = count[i] + count[i - 1];
        }
        // 考虑到排序的稳定性，所以需要进行反向填充
        for (int i = len - 1; i >= 0; i--) {
            extra[--count[nums[i] - min]] = nums[i];
        }
        return extra;
    }

    /**
     * 优化版计数排序
     *
     * @param nums
     */
    public void countingSortOptimize(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return;
        int min = nums[0], max = nums[0];
        for (int i = 1; i < len; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        int k = max - min + 1;
        int[] count = newint[k];
        // 计数
        for (int i = 0; i < len; i++) {
            count[nums[i] - min]++;
        }
        int index = 0;
        for (int i = 0; i < k; i++) {
            while (count[i] != 0) {
                nums[index++] = i + min;
                count[i]--;
            }
        }
    }
}

图 9.2.1 Counting Sort

原理：先将待排序数组分到有限数量的有序桶里，然后每个桶中的元素再分别进行排序（排序算法可以是其他排序算法也可以是递归的桶排序），最后取出桶中元素放回原数组。具体实现过程如下：设置一定数量的数组作为空桶（可调整），然后将待排序的数组中的元素放到对应的桶中，再对每个非空桶进行排序，最后将非空桶的元素依次放回原数组，排序完成。

import java.util.ArrayList;
import java.util.List;

publicclass BucketSort {
    /**
     * 桶排序
     *
     * @param nums
     */
    public void bucketSort(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return;
        int min = nums[0], max = nums[0];
        for (int i = 0; i < len; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        // 步长
        int step = 2;
        // 桶的个数
        int bucketNum = max / step - min / step + 1;
        List<List<Integer>> buckets = new ArrayList<List<Integer>>();
        // 桶的初始化
        for (int i = 0; i < bucketNum; i++) {
            buckets.add(new ArrayList<Integer>());
        }
        // 将待排序数组元素装桶
        for (int i = 0; i < len; i++) {
            int index = (nums[i] - min) / step;
            buckets.get(index).add(nums[i]);
        }
        // 将桶内元素进行插入排序后重新放回原数组
        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            List<Integer> bucket = buckets.get(i);
            insertionSort(bucket);
            for (int j : bucket) {
                nums[index++] = j;
            }
        }
    }

    /**
     * 桶内元素的插入排序
     *
     * @param bucket
     */
    public void insertionSort(List<Integer> bucket) {
        int size = bucket.size();
        for (int i = 0; i < size; i++) {
            for (int j = i; j > 0; j--) {
                if (bucket.get(j) < bucket.get(j - 1)) {
                    swap(bucket, j, j - 1);
                }
            }
        }
    }

    public void swap(List<Integer> bucket, int i, int j) {
        int tmp = bucket.get(i);
        bucket.set(i, bucket.get(j));
        bucket.set(j, tmp);
    }
}

图 10.2.1 Bucket Sort

原理：将整数按位切割成不同的数字，然后按位数分别进行比较。具体过程如下：先找出待排序数组的最大数字，并计算其位数，即为最终循环排序的次数，然后按照位数从最低位开始进行计数排序，直到最高位，最后数组排序完成。

publicclass RadixSort {
    /**
     * 基数排序（LSD：Least Significant Digital）
     *
     * @param nums
     */
    public void radixSort(int[] nums) {
        int len = nums.length;
        if (len <= 1)
            return;
        int digital = maxDigital(nums, len);
        // 需要循环排序的次数，为最大数的位数
        for (int i = 0; i < digital; i++) {
            int[] count = newint[10];
            // 每次计算的基数
            int radix = (int) Math.pow(10, i);
            // 计数
            for (int j = 0; j < len; j++) {
                count[(nums[j] / radix) % 10]++;
            }
            // 累加
            for (int j = 1; j < 10; j++) {
                count[j] = count[j] + count[j - 1];
            }
            // 反向填充
            int[] tmp = newint[len];
            for (int j = len - 1; j >= 0; j--) {
                tmp[--count[(nums[j] / radix) % 10]] = nums[j];
            }
            // 重新赋值给原数组
            for (int j = 0; j < len; j++) {
                nums[j] = tmp[j];
            }
        }
    }

    /**
     * 求最大数的位数
     *
     * @param nums 待排序数组
     * @param len  数组长度
     * @return 位数
     */
    public int maxDigital(int[] nums, int len) {
        int max = nums[0];
        for (int i = 1; i < len; i++) {
            max = Math.max(max, nums[i]);
        }
        int digital = 1;

        while (max >= 10) {
            max = max / 10;
            digital++;
        }
        return digital;
    }
}

图 11.2.1 Radix Sort