HelloWorld
登录

时间复杂度为 O(nlogn) 的排序算法 | 京东物流技术团队

京东云开发者

2023-11-27

886 0 0

归并排序

归并排序遵循分治的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后合并这些子问题的解来建立原问题的解，归并排序的步骤如下：

  • 划分：分解待排序的 n 个元素的序列成各具 n/2 个元素的两个子序列，将长数组的排序问题转换为短数组的排序问题，当待排序的序列长度为 1 时，递归划分结束

  • 合并：合并两个已排序的子序列得出已排序的最终结果

归并排序的代码实现如下：

1    private void sort(int[] nums, int left, int right) {
2        if (left >= right) {
3            return;
4        }
5
6        // 划分
7        int mid = left + right >> 1;
8        sort(nums, left, mid);
9        sort(nums, mid + 1, right);
10        // 合并
11        merge(nums, left, mid, right);
12    }
13
14    private void merge(int[] nums, int left, int mid, int right) {
15        // 辅助数组
16        int[] temp = Arrays.copyOfRange(nums, left, right + 1);
17
18        int leftBegin = 0, leftEnd = mid - left;
19        int rightBegin = leftEnd + 1, rightEnd = right - left;
20        for (int i = left; i <= right; i++) {
21            if (leftBegin > leftEnd) {
22                nums[i] = temp[rightBegin++];
23            } else if (rightBegin > rightEnd || temp[leftBegin] < temp[rightBegin]) {
24                nums[i] = temp[leftBegin++];
25            } else {
26                nums[i] = temp[rightBegin++];
27            }
28        }
29    }
30
31

归并排序最吸引人的性质是它能保证将长度为 n 的数组排序所需的时间和 nlogn 成正比；它的主要缺点是所需的额外空间和 n 成正比。

算法特性：

  • 空间复杂度：借助辅助数组实现合并，使用 O(n) 的额外空间；递归深度为 logn，使用 O(logn) 大小的栈帧空间。忽略低阶部分，所以空间复杂度为 O(n)

  • 非原地排序

  • 稳定排序

  • 非自适应排序

以上代码是归并排序常见的实现，下面我们来一起看看归并排序的优化策略：

将多次创建小数组的开销转换为只创建一次大数组

在上文实现中，我们在每次合并两个有序数组时，即使是很小的数组，我们都会创建一个新的 temp[] 数组，这部分耗时是归并排序运行时间的主要部分。更好的解决方案是将 temp[] 数组定义成 sort() 方法的局部变量，并将它作为参数传递给 merge() 方法，实现如下：

1    private void sort(int[] nums, int left, int right, int[] temp) {
2        if (left >= right) {
3            return;
4        }
5
6        // 划分
7        int mid = left + right >> 1;
8        sort(nums, left, mid, temp);
9        sort(nums, mid + 1, right, temp);
10        // 合并
11        merge(nums, left, mid, right, temp);
12    }
13
14    private void merge(int[] nums, int left, int mid, int right, int[] temp) {
15        System.arraycopy(nums, left, temp, left, right - left + 1);
16        int l = left, r = mid + 1;
17        for (int i = left; i <= right; i++) {
18            if (l > mid) {
19                nums[i] = temp[r++];
20            } else if (r > right || temp[l] < temp[r]) {
21                nums[i] = temp[l++];
22            } else {
23                nums[i] = temp[r++];
24            }
25        }
26    }
27
28

当数组有序时，跳过 merge() 方法

我们可以在执行合并前添加判断条件：如果nums[mid] <= nums[mid + 1]时我们认为数组已经是有序的了，那么我们就跳过 merge() 方法。它不影响排序的递归调用，但是对任意有序的子数组算法的运行时间就变成线性的了，代码实现如下：

1    private void sort(int[] nums, int left, int right, int[] temp) {
2        if (left >= right) {
3            return;
4        }
5
6        // 划分
7        int mid = left + right >> 1;
8        sort(nums, left, mid, temp);
9        sort(nums, mid + 1, right, temp);
10        // 合并
11        if (nums[mid] > nums[mid + 1]) {
12            merge(nums, left, mid, right, temp);
13        }
14    }
15
16    private void merge(int[] nums, int left, int mid, int right, int[] temp) {
17        System.arraycopy(nums, left, temp, left, right - left + 1);
18        int l = left, r = mid + 1;
19        for (int i = left; i <= right; i++) {
20            if (l > mid) {
21                nums[i] = temp[r++];
22            } else if (r > right || temp[l] < temp[r]) {
23                nums[i] = temp[l++];
24            } else {
25                nums[i] = temp[r++];
26            }
27        }
28    }
29
30

对小规模子数组使用插入排序

对小规模数组进行排序会使递归调用过于频繁，而使用插入排序处理小规模子数组一般可以将归并排序的运行时间缩短 10% ~ 15%，代码实现如下：

1    /**
2     * M 取值在 5 ~ 15 之间大多数情况下都能令人满意
3     */
4    private final int M = 9;
5
6    private void sort(int[] nums, int left, int right) {
7        if (left + M >= right) {
8            // 插入排序
9            insertSort(nums);
10            return;
11        }
12
13        // 划分
14        int mid = left + right >> 1;
15        sort(nums, left, mid);
16        sort(nums, mid + 1, right);
17        // 合并
18        merge(nums, left, mid, right);
19    }
20
21    /**
22     * 插入排序
23     */
24    private void insertSort(int[] nums) {
25        for (int i = 1; i < nums.length; i++) {
26            int base = nums[i];
27
28            int j = i - 1;
29            while (j >= 0 && nums[j] > base) {
30                nums[j + 1] = nums[j--];
31            }
32            nums[j + 1] = base;
33        }
34    }
35
36    private void merge(int[] nums, int left, int mid, int right) {
37        // 辅助数组
38        int[] temp = Arrays.copyOfRange(nums, left, right + 1);
39
40        int leftBegin = 0, leftEnd = mid - left;
41        int rightBegin = leftEnd + 1, rightEnd = right - left;
42        for (int i = left; i <= right; i++) {
43            if (leftBegin > leftEnd) {
44                nums[i] = temp[rightBegin++];
45            } else if (rightBegin > rightEnd || temp[leftBegin] < temp[rightBegin]) {
46                nums[i] = temp[leftBegin++];
47            } else {
48                nums[i] = temp[rightBegin++];
49            }
50        }
51    }
52
53

快速排序

快速排序也遵循分治的思想，它与归并排序不同的是，快速排序是原地排序，而且快速排序会先排序当前数组，再对子数组进行排序，它的算法步骤如下：

  • 哨兵划分：选取数组中最左端元素为基准数，将小于基准数的元素放在基准数左边，将大于基准数的元素放在基准数右边

  • 排序子数组：将哨兵划分的索引作为划分左右子数组的分界，分别对左右子数组进行哨兵划分和排序

快速排序的代码实现如下：

1    private void sort(int[] nums, int left, int right) {
2        if (left >= right) {
3            return;
4        }
5
6        // 哨兵划分
7        int partition = partition(nums, left, right);
8
9        // 分别排序两个子数组
10        sort(nums, left, partition - 1);
11        sort(nums, partition + 1, right);
12    }
13
14    /**
15     * 哨兵划分
16     */
17    private int partition(int[] nums, int left, int right) {
18        // 以 nums[left] 作为基准数，并记录基准数索引
19        int originIndex = left;
20        int base = nums[left];
21
22        while (left < right) {
23            // 从右向左找小于基准数的元素
24            while (left < right && nums[right] >= base) {
25                right--;
26            }
27            // 从左向右找大于基准数的元素
28            while (left < right && nums[left] <= base) {
29                left++;
30            }
31            swap(nums, left, right);
32        }
33        // 将基准数交换到两子数组的分界线
34        swap(nums, originIndex, left);
35
36        return left;
37    }
38
39    private void swap(int[] nums, int left, int right) {
40        int temp = nums[left];
41        nums[left] = nums[right];
42        nums[right] = temp;
43    }
44
45

算法特性：

  • 时间复杂度：平均时间复杂度为 O(nlogn)，最差时间复杂度为 O(n2)

  • 空间复杂度：最差情况下，递归深度为 n，所以空间复杂度为 O(n)

  • 原地排序

  • 非稳定排序

  • 自适应排序

归并排序的时间复杂度一直是 O(nlogn)，而快速排序在最坏的情况下时间复杂度为 O(n2)，为什么归并排序没有快速排序应用广泛呢？

答：因为归并排序是非原地排序，在合并阶段需要借助非常量级的额外空间

快速排序有很多优点，但是在哨兵划分不平衡的情况下，算法的效率会比较低效。下面是对快速排序排序优化的一些方法：

切换到插入排序

对于小数组，快速排序比插入排序慢，快速排序的 sort() 方法在长度为 1 的子数组中也会调用一次，所以，在排序小数组时切换到插入排序排序的效率会更高，如下：

1    /**
2     * M 取值在 5 ~ 15 之间大多数情况下都能令人满意
3     */
4    private final int M = 9;
5
6    public void sort(int[] nums, int left, int right) {
7        // 小数组采用插入排序
8        if (left + M >= right) {
9            insertSort(nums);
10            return;
11        }
12
13        int partition = partition(nums, left, right);
14        sort(nums, left, partition - 1);
15        sort(nums, partition + 1, right);
16    }
17
18    /**
19     * 插入排序
20     */
21    private void insertSort(int[] nums) {
22        for (int i = 1; i < nums.length; i++) {
23            int base = nums[i];
24
25            int j = i - 1;
26            while (j >= 0 && nums[j] > base) {
27                nums[j + 1] = nums[j--];
28            }
29            nums[j + 1] = base;
30        }
31    }
32
33    private int partition(int[] nums, int left, int right) {
34        int originIndex = left;
35        int base = nums[left];
36
37        while (left < right) {
38            while (left < right && nums[right] >= base) {
39                right--;
40            }
41            while (left < right && nums[left] <= base) {
42                left++;
43            }
44            swap(nums, left, right);
45        }
46        swap(nums, left, originIndex);
47
48        return left;
49    }
50
51    private void swap(int[] nums, int left, int right) {
52        int temp = nums[left];
53        nums[left] = nums[right];
54        nums[right] = temp;
55    }
56
57

基准数优化

如果数组为倒序的情况下，选择最左端元素为基准数，那么每次哨兵划分会导致右数组长度为 0，进而使快速排序的时间复杂度为 O(n2)，为了尽可能避免这种情况，我们可以对基准数的选择进行优化，采用三取样切分的方法：选取数组最左端、中间和最右端这三个值的中位数为基准数，这样选择的基准数大概率不是区间的极值，时间复杂度为 O(n2) 的概率大大降低，代码实现如下：

1    public void sort(int[] nums, int left, int right) {
2        if (left >= right) {
3            return;
4        }
5
6        // 基准数优化
7        betterBase(nums, left, right);
8
9        int partition = partition(nums, left, right);
10
11        sort(nums, left, partition - 1);
12        sort(nums, partition + 1, right);
13    }
14
15    /**
16     * 基准数优化，将 left, mid, right 这几个值中的中位数换到 left 的位置
17     * 注意其中使用了异或运算进行条件判断
18     */
19    private void betterBase(int[] nums, int left, int right) {
20        int mid = left + right >> 1;
21
22        if ((nums[mid] < nums[right]) ^ (nums[mid] < nums[left])) {
23            swap(nums, left, mid);
24        } else if ((nums[right] < nums[left]) ^ (nums[right] < nums[mid])) {
25            swap(nums, left, right);
26        }
27    }
28
29    private int partition(int[] nums, int left, int right) {
30        int originIndex = left;
31        int base = nums[left];
32
33        while (left < right) {
34            while (left < right && nums[right] >= base) {
35                right--;
36            }
37            while (left < right && nums[left] <= base) {
38                left++;
39            }
40            swap(nums, left, right);
41        }
42        swap(nums, originIndex, left);
43
44        return left;
45    }
46
47    private void swap(int[] nums, int left, int right) {
48        int temp = nums[left];
49        nums[left] = nums[right];
50        nums[right] = temp;
51    }
52
53

三向切分

在数组有大量重复元素的情况下，快速排序的递归性会使元素全部重复的子数组经常出现，而对这些数组进行快速排序是没有必要的，我们可以对它进行优化。

一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于基准数的数组，每次将其中“小于”和“大于”的数组进行排序，那么最终也能得到排序的结果，这种策略下我们不会对等于基准数的子数组进行排序，提高了排序算法的效率，它的算法流程如下：

从左到右遍历数组，维护指针 l 使得 [left, l - 1] 中的元素都小于基准数，维护指针 r 使得 [r + 1, right] 中的元素都大于基准数，维护指针 mid 使得 [l, mid - 1] 中的元素都等于基准数，其中 [mid, r] 区间中的元素还未确定大小关系，图示如下：

快速排序-荷兰国旗.jpg

它的代码实现如下：

1    public void sort(int[] nums, int left, int right) {
2        if (left >= right) {
3            return;
4        }
5
6        // 三向切分
7        int l = left, mid = left + 1, r = right;
8        int base = nums[l];
9        while (mid <= r) {
10            if (nums[mid] < base) {
11                swap(nums, l++, mid++);
12            } else if (nums[mid] > base) {
13                swap(nums, mid, r--);
14            } else {
15                mid++;
16            }
17        }
18
19        sort(nums, left, l - 1);
20        sort(nums, r + 1, right);
21    }
22
23    private void swap(int[] nums, int left, int right) {
24        int temp = nums[left];
25        nums[left] = nums[right];
26        nums[right] = temp;
27    }
28
29

这也是经典的荷兰国旗问题，因为这就好像用三种可能的主键值将数组排序一样，这三种主键值对应着荷兰国旗上的三种颜色

巨人的肩膀

作者：京东物流 王奕龙

来源：京东云开发者社区 自猿其说 Tech 转载请注明来源

点赞
收藏

评论区

加载中...

相关推荐

【分治法】解决中位数问题、格雷码问题以及分治法直接折半存在的问题讨论————武汉理工大学算法分析实验1

AlgorithmExperiment算法分析课实验分治法的核心思想是将问题分为若干子问题去，使规模一步步缩小，最终分到一步就能得出结果。要注意每个子问题需要性质相同而且相互不重复。采用分治法完成如下任务：i.中位数问题问题描述设X0:n1和Y0:n–1为两个数组，每个数组中含有n个已排好序的数。找出X和Y

Java面试总结（排序算法）

1.冒泡排序算法描述：两两比较，大的放后面2.选择排序算法描述：在m元数组中找到最小值的位置，然后将最小值的位置和第n(n0,1,2,....m1)位的值对调，排序k次则m元数组中前k(k<m)位的值已经排序好，m元数组中前k位的值不需要再进行排序，此时需要排序的元素只有mk个3.插入排序算

BFPRT线性查找算法

介绍：BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，五位算法作者做了精妙的处理。时间复杂度O(N)算法步骤

PHP快速排序（原地切分）

        快速排序是一种分治的排序算法，采用递归的思想，将数组元素分为两部分，选择切分元素，左右扫描数组，将大于切分元素的数据放在右边，小于切分元素的数据放在左边，直到扫描指针相遇，切分结束，同时递归调用，直到数组有序。      代码如下：<?phpfunctionquick_sort(array&$array,$l

时间复杂度为 O(n^2) 的排序算法

作者：京东保险王奕龙对于小规模数据，我们可以选用时间复杂度为O(n2)的排序算法。因为时间复杂度并不代表实际代码的执行时间，它省去了低阶、系数和常数，仅代表的增长趋势，所以在小规模数据情况下，O(n2)的排序算法可能会比O(nlogn)的排序算法执行效率高

什么是归并排序？

原文链接：什么是归并排序（mergeSort）？主要分成两部分实现，分、合操作：分：把数组分成两半，在递归地对子数组进行"分"操作，直到分成一个个单独的数合：把两个数组合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组归并排序就是采用了