慢速排序

十大经典排序算法

我们前面讲过快速排序，这里我们来看下慢速排序（Slow sort），他是基于合并排序的分而治之及递回的思想，并故意设计使排序过程非常缓慢。简单来讲，该算法递归地从序列的前后两部分中各自选出最大的元素然后将这两个元素中较大的移至末尾，接着在慢速排序剩下的部分。步骤如下：

• 以慢速排序法排序前半部的元素。
• 以慢速排序法排序后半部的元素。
• 比较前半部分和后半部分排序结果的最后一个元素，选择两者中的最大值放到序列的末尾。
• 除了最后一个元素不参与排序以外，继续对剩下的元素进行慢速排序。

// 慢速排序
private void slowSort(int[] nums) {
    helper(nums, 0, nums.length - 1);
}

/**
 * @param nums
 * @param start 闭区间，待排序序列的左边界
 * @param end   闭区间，待排序序列的右边界
 */
private void helper(int[] nums, int start, int end) {
    if (start >= end)// 只有一个元素不需要排序，直接返回。
        return;
    int mid = (start + end) >>> 1;
    // 把待排序数组分成两部分，分别递归计算
    helper(nums, start, mid);
    helper(nums, mid + 1, end);
    // 比较前后两部分的最后一个元素，判断是否需要交换。
    if (nums[mid] > nums[end])
        swap(nums, end, mid);
    // 除最后一个不参与以外，继续递归剩下的。
    helper(nums, start, end - 1);
}

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

相关链接