十大排序之快速排序
汇总在这里 十大排序汇总
快速排序(Quick Sort)
算法介绍:
快速排序(Quick Sort)是一种高效的排序算法,它采用分治的策略来将一个数组分成两个子数组,然后递归地对子数组进行排序,最终将整个数组排序完成。
算法原理:
快速排序的基本思想如下:
- 选择一个基准元素(pivot)作为参考值。
- 将数组中的元素按照与基准元素的大小关系划分为两个部分,使得左边的部分小于等于基准元素,右边的部分大于基准元素。
- 对左右两个部分分别进行递归调用快速排序。
- 递归的终止条件是子数组的长度为1或0,此时数组已经有序。
-
快速排序的关键在于划分操作,通常采用Lomuto分区或Hoare分区两种方式:
-
Lomuto分区:选择最后一个元素作为基准元素,通过交换元素的位置将小于等于基准元素的元素放在它的左边,大于基准元素的元素放在它的右边,最后返回基准元素的索引。
- Hoare分区:选择数组的第一个和最后一个元素作为基准元素的值,然后从数组的两端开始向中间扫描,找到需要交换的元素对,并进行交换,直到两个指针相遇,返回相遇点的索引。
时间复杂度:
快速排序的平均时间复杂度为O(nlogn),其中n是待排序数组的长度。在最坏情况下,快速排序的时间复杂度为O(n^2),但这种情况较少发生。快速排序是一种原地排序算法,不需要额外的辅助空间。
快速排序在实践中被广泛应用,它具有较好的平均性能和较高的效率。然而,快速排序的性能受到基准元素的选择和划分操作的影响,如果选择的基准元素不合适或划分操作不平衡,可能会导致算法的性能下降。因此,对于优化快速排序算法,有很多改进的方法,如随机选择基准元素、三数取中法等。
快速排序有很多中实现方式,接下来我会依次介绍。
hoare法(左右指针法)
快速排序的 Hoare 分区(也称为左右指针法)是一种常用的划分方式,用于将数组分成两个部分。它由英国计算机科学家 Tony Hoare 在 1960 年提出,并被广泛应用于快速排序算法中。
Hoare 分区的基本思想如下:
- 选择数组的第一个元素作为基准元素(pivot)。
- 使用两个指针,一个指向数组的左边(左指针),一个指向数组的右边(右指针)。
- 左指针向右移动,直到找到一个大于等于基准元素的元素。
- 右指针向左移动,直到找到一个小于等于基准元素的元素。
- 如果左指针仍在右指针的左侧,则交换左指针和右指针所指向的元素。
- 重复步骤 3-5,直到左指针大于等于右指针。
- 最后,将基准元素与右指针所指向的元素进行交换,此时右指针所在位置即为基准元素的最终位置。
经过一次 Hoare 分区后,数组被划分为两个部分,左侧的元素小于等于基准元素,右侧的元素大于等于基准元素。然后,对这两个部分分别进行递归调用快速排序,直到完成整个数组的排序。
与 Lomuto 分区相比,Hoare 分区通常具有更高的性能,因为它减少了元素交换的次数。然而,Hoare 分区可能会导致两个指针相遇时,基准元素尚未到达最终位置的情况。因此,在实现 Hoare 分区时需要额外的处理来确保基准元素的最终位置正确。
总结起来,Hoare 分区是一种高效的划分方式,常用于快速排序算法中。它通过左右指针的移动和元素交换,将数组划分为两个部分,并递归地对子数组进行排序。这种划分方式在大多数情况下比 Lomuto 分区更快,但在某些特定情况下可能需要特殊处理。
算法基础课 y总代码使用do…while实现 Hoare,代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N];
// 找到一个合适的x作为判断点
int findMiddle(int a, int b, int c) {
int middle;
if ((a <= b && b <= c) || (c <= b && b <= a)) {
middle = b;
} else if ((b <= a && a <= c) || (c <= a && a <= b)) {
middle = a;
} else {
middle = c;
}
return middle;
}
// 快速排序
void quick_sort(int q[], int l, int r) {
if (l >= r) {
return;
}
int x = findMiddle(q[l], q[(l + r) / 2], q[r]); // 选择合适的x作为基准元素
int i = l - 1, j = r + 1;
while (i < j) {
do i++; while (q[i] < x); // 左指针向右移动,直到找到大于等于x的元素
do j--; while (q[j] > x); // 右指针向左移动,直到找到小于等于x的元素
if (i < j) {
swap(q[i], q[j]); // 交换左指针和右指针所指向的元素
}
}
quick_sort(q, l, j); // 对左侧子数组进行快速排序
quick_sort(q, j + 1, r); // 对右侧子数组进行快速排序
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &q[i]);
}
quick_sort(q, 0, n - 1); // 对数组进行快速排序
for (int i = 0; i < n; i++) {
printf("%d ", q[i]); // 输出排序后的数组
}
}
这个过程会一直持续,直到左右指针相遇。最后,通过递归调用 quick_sort
函数,对基准元素左边的子数组和右边的子数组进行排序。这样,整个数组就会被划分成越来越小的子数组,并且每个子数组都是有序的。
处理边界问题
Q.为什么一定要用j
和 j + 1
作为分界点呢?i
不可以吗?
因为i和j在完成最后一次交换后还会各自向前移动一位,最后i指向的数>x,i左边的数<x,所以,区间(l , j)里的数都>x,如果递归时的区间是(q,l,i),那么就会多出一个“>x”的数,同理,右边也一样。
如果想用i做边界的话,就是quick_sort(q,l,i-1); quick_sort(q,i,r);
除do…while外,Hoare 的实现方式
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int x = q[l + r >> 1], i = l, j = r;
while (true) {
while (q[i] < x) i ++;
while (q[j] > x) j --;
if (i >= j) break;
swap(q[i], q[j]);
i ++;
j --;
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
注意
如果我们取头值作为我们的key值,那么我们一定要让右指针先移动
如果我们取尾值作为我们的key值,那么我们一定要让左指针先移动
挖坑法
快速排序的挖坑法是一种常见的实现方式,它与使用左右指针的方式相比,使用了类似”挖坑”的思想。
下面是使用挖坑法实现的快速排序动画:
下面是使用挖坑法实现的快速排序代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
void quick_sort(int q[], int l, int r)
{
if (l >= r)
{
return;
}
int i = l, j = r;
int x = q[l]; // 选择第一个元素作为基准元素
while (i < j)
{
while (i < j && q[j] >= x)
{
j--;
}
if (i < j)
{
q[i] = q[j]; // 将q[j]填入q[i]的坑中
i++;
}
while (i < j && q[i] <= x)
{
i++;
}
if (i < j)
{
q[j] = q[i]; // 将q[i]填入q[j]的坑中
j--;
}
}
q[i] = x; // 将基准元素放入最后的坑中
quick_sort(q, l, i - 1); // 递归处理左半部分
quick_sort(q, i + 1, r); // 递归处理右半部分
}
int main()
{
int n;
cin >> n;
int q[n];
for (int i = 0; i < n; i++)
{
cin >> q[i];
}
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i++)
{
cout << q[i] << " ";
}
cout << endl;
return 0;
}
在这段代码中,我们选择第一个元素 q[l]
作为基准元素 x
。然后使用两个指针 i
和 j
分别从数组的两端向中间移动,寻找比基准元素小和大的元素。当找到这样的元素时,就将它填入另一个指针所指的位置,形成一个坑。接着,移动另一个指针,继续寻找下一个需要填入坑中的元素。
最后,将基准元素放入最后的坑中,此时数组被分成两部分,左边部分的元素都小于等于基准元素,右边部分的元素都大于等于基准元素。然后递归地对左边部分和右边部分进行快速排序。
通过这种挖坑的方式,可以有效地实现快速排序算法。
前后指针法(双指针法)
定义两指针一前一后,cur指针找比key小的值,和prev指针前一个值进行交换,直至结束。将prev位置值与key位置值进行交换,此时key位置值,左边比key位置值小,右边比key位置值大,在进行分治就可以了。
#include <iostream>
#include <algorithm>
using namespace std;
void quick_sort(int q[], int l, int r)
{
if (l >= r)
return;
int x = l, i = l, j = l + 1;
while (j <= r)
{
// 将小于基准元素的元素交换到左侧
if (q[j] < q[x])
{
i++;
if(i != j) swap(q[i], q[j]);
}
j++;
}
// 将基准元素放置在正确的位置
swap(q[x], q[i]);
// 递归排序基准元素左右两侧的子数组
quick_sort(q, l, i - 1);
quick_sort(q, i + 1, r);
}
int main()
{
int n;
cin >> n;
int q[n];
// 输入待排序的数组
for (int i = 0; i < n; i++)
{
cin >> q[i];
}
// 调用快速排序算法对数组进行排序
quick_sort(q, 0, n - 1);
// 输出排序后的数组
for (int i = 0; i < n; i++)
{
cout << q[i] << " ";
}
cout << endl;
return 0;
}
快速排序的优化
算法缺陷与优化
- 算法缺陷
1.1 基准值取值
若所取基准值为序列中的最大或最小值,那么每趟划分后,基准值的一侧将会出现没有元素的情况,就相当于每趟只完成了一个元素的排序,那么快速排序的时间复杂度此时将达到O(n^2),效率较低。
1.2 递归超限
算法递归深度会随着元素的增多而加深,若序列元素元素量非常巨大,可能会造成递归超限。 - 优化方法
2.1 三位取中法
我们可以通过选取序列中开始、中间、末尾三个位置中元素大小居中的元素作为基准值,此方法可以大大降低基准值取到序列内最大或最小元素的概率。
注:为了不改变代码的逻辑实现,若取得的基准值的位置不是基准值默认位置,可先提前将基准值交换到所取基准值的默认位置处。
2.2 设置阈值
我们可以发现,随着划分次数的增加,子序列内的元素个数会不断减少,而且元素数量较少时,各类排序算法的效率差距其实是可以忽略不记的,而比较适合元素个数比较少的排序就是直接插入排序,所以我们可以在递归的过程中设计一个阈值,当子序列中元素个数不超过阈值时,递归不再进行,而是直接对当前子序列进行直接插入排序,然后返回。
当然,这种方法只能进行一定程度的缓解,并不能完全解决递归超限的问题。
所以,我们可以提前估算一下递归的深度N,再在递归深度上设置一个阈值count,若N小于count直接进行快速排序;若N大于count,先通过快速排序递归count次,然后再对每个分组中进行其他排序(比如:堆排序)。
这样即不会对算法效率造成太大影响,也避免了递归超限的问题。
2.3 循环实现
使用循环的方式实现快速排序,我们会发现直接转循环并不容易实现,结合递归调用的特性,后调用的先结束退出,先调用的后结束,符合栈后进先出的特点,所有可以利用栈来循环实现快速排序。
每次对序列进行分割后,利用栈依次压入左右子序列的右边界和左边界,这样下一次循环就会依次拿到一个子序列的左右边界,然后再对此序列进行分割,循环进行上述操作,直到栈为空即完成序列排序。(可加上优化方法,为子序列元素个数加上阈值)
快速排序代码优化会专门出一个题解,这里就不再过多赘述。