快速排序简易入门

快速排序

快速排序(Quick Sort)因其 O(N\log_{}N) 的复杂度成为最常见的算法之一,甚至被纳入了 C++ 的标准库作为 std::sort 的一部分与插入排序糅合在一起以实现更优的时间复杂度。

在学习快速排序算法之前,让我们首先回顾最经典的排序算法——冒泡排序:经过 (N-1)! 次比较,以 O(N!) 的复杂度完成排序。由于冒泡排序每次只比对相邻的两个元素,所以排序效率相对比较低。

快速排序的优势在于,应用了分治的思想(有点像二分),通过多次迭代将元素依次归位,最终完成排序。单元操作如下:

  1. 最左端 选取端元素作为基准数
  2. 使用下标 i 从 最右端 开始寻找小于基准数的元素
  3. 使用下标 j 从 最左端 开始寻找大于基准数的元素
  4. 交换满足条件后的 i, j 下标所对应的元素,然后重复过程 2, 3 直至两下标相遇
  5. 将两下标所处元素与基准数交换

经过以上过程后,基准数左侧的元素均小于等于基准数,基准数右侧的元素均大于等于基准数。接着通过迭代的方式,将此时基准数左端区域与右端区域分别进行下一轮排序操作。当区间内只剩下一个元素时,结束当前过程。

注意:
一、快速排序中扫描时 必须从基准数的对面开始

原因:允许交换的前提:
1. 有 arr[r] < arr[L];
2. 有 arr[l] > arr[L]。

如果从左边开始,则在 l 与 r 相遇时可能只满足了 2 但未满足 1,此时基准数 arr[L] 与 arr[l](arr[r])发生交换,导致一个大于基准数的值被放在了最左。

二、基准数归位后就固定了,接下来分治排列 [L, l – 1] 和 [l+1, R] 即可。(此时 r == l)

改进

对于原始的快速排序,由于每次都从固定的一端选取基准数,当遇到有序序列时,可能会导致基准数归位后其余元素都在基准数的某一侧,而另一侧没有元素的情况,最终导致排序性能退化。为了避免这种情况出现,我们需要引入一个随机化操作来打乱有序序列:在当前区间内随机选取一个元素与基准数交换,然后以其作为新的基准数。示例代码如下:

#define INF
#define offline
#include "bits/stdc++.h"
using namespace std;

// int arr[] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
int arr[100010];
int n;
int t;

inline void Swap(int *a, int *b)
{
    t = *a;
    *a = *b;
    *b = t;
}

inline int readint()
{
    char c;
    bool neg = false;
    while((c = getchar()) < '0' || c > '9')
        neg = c == '-';//等价于 neg = (c == '-'),因为 == 的优先级更高
    int a = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        a = a * 10 + c - '0';
    return neg ? -a : a;
}

inline void Out(int n)
{
    if (n < 0)
        putchar('-'), n = -n;
    if (n >= 10)
       Out(n / 10);
    putchar(n % 10 + '0');
}

inline void quicksort(int L, int R)
{
    int l = L;
    int r = R;

    Swap(&arr[L + ((int)rand() % (R - L))], &arr[L]);
    while (l < r)
    {
        if (arr[r] < arr[L])
        {
            while (l < r)
            {
                if (arr[l] > arr[L])
                {
                    Swap(&arr[l], &arr[r]);
                    break;
                }
                else
                    l++;
            }
        }
        r--;
    }
    Swap(&arr[L], &arr[l]);
    if (L < l - 1)
        quicksort(L, l - 1);
    if (R > r + 1)
        quicksort(r + 1, R);
}

int main()
{
    //std::ios_base::sync_with_stdio(false);
    //std::cin.tie(0);
    //srand((unsigned int)(time(NULL)));
    // n = 10;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        arr[i] = readint();

    quicksort(0, n - 1);

    for (int i = 0; i < n - 1; ++i)
    {
        Out(arr[i]);
        putchar(' ');
    }
    Out(arr[n-1]);
    putchar('\n');

    return 0;
}

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据