【数据结构与算法】快速排序、随机基准值、双路快排、三路快排 |
您所在的位置：网站首页 › 数据结构快速排序怎么排的 › 【数据结构与算法】快速排序、随机基准值、双路快排、三路快排 |
【数据结构与算法】快速排序、随机基准值、双路快排、三路快排
|
在 https://visualgo.net/zh/sorting 的 QUI 标签中可以看到快排序动画演示。 文章目录 快速排序基本思想基础实现优化随机基准值双路快排三路快排 性能测试 快速排序平均时间复杂度：O(nlogn)，最坏情况下 O(n^2) 空间复杂度：O(1) 基本思想分治。 找一个基准元素，以基准元素分解，左边是比基准元素小的，右边是比基准元素大的。 这样就把一个待排序数组分成了左右两部分。 对左、右分别进行上面的步骤。 4 3 5 6 2 1 我们选取 4 作为基准值。 1 3 2 4 5 6 在对 [1 3 2] 和 [5 6] 进行操作。
10k 个随机数 [0, 10k] 排序： 归并排序 : 0.001776 s 快速排序 : 0.001609 s归并排序、快排均属于 O(nlogn) 数量级的算法。 优化 随机基准值上面的这种实现是有问题的，如果待排序数组已经接近有序了，我们选取第一个值作为基准值，将其分成两部分，就会造成一部分特别大。通过下面的测试可以看出： 10k 个接近有序的数 [0, 10k] 排序： 归并排序 : 0.004252 s 快速排序 : 2.7637 s这个时候快排就退化为了 O(n^2) 级别。 随机选一个数做基准值 第一次随机选取一个数，选取到刚好是最小的概率是 1/n； 第二次是 1/(n-1)； … 这样下来，每次都选取到的是一个很小的数字 1/n * 1/(n-1) * 1/(n-2) * ...。是一个很小的概率。 template int __partition(T arr[], int l, int r) { swap(arr[l], arr[rand() % (r-l+1) + l]); T v = arr[l]; // arr[l + 1, j] < v; arr[j + 1, i] > v; int j = l; for (int i = l + 1; i j) break; swap(arr[i++], arr[j--]); } swap(arr[l], arr[j]); return j; }双路快排，100k 个随机数，范围 [0, 5]： 归并排序 : 0.015794 s 快速排序 : 0.026956 s可以看到，双路快排和归并已经在一个数量级了。 三路快排通过上面的随机选基准值、双路快排，已经解决了一部分问题，但现在还不是最优。 100k 个随机数，范围 [0, 5]，虽然双路快排基本平均的分成了两部分进行，但是对于大量的和基准值相同的数，做了很多重复操作。 三路快排就是将待排序数组分成【小于基准值，等于基准值，大于基准值】三部分，下一轮排序只对小于基准值和大于基准值的两个部分进行排序即可，这样就省去了很大一部分操作。 template void __quickSort3Ways(T arr[], int l, int r) { if (l >= r) return ; srand(time(NULL)); swap(arr[l], arr[rand() % (r - l + 1) + l]); T v = arr[l]; // partition int i = l + 1; int lt = l; int gt = r + 1; while (i |
究其原因，发现是选择基准数字的问题。 那么这个基准数字应该如何选择呢？【本文地址】
今日新闻 |
推荐新闻 |