快速排序

Posted by 磊落 on May 11, 2020

快速排序

特点

  • 不稳定排序算法

  • 平均复杂度O(nlog2(n)), 最坏时间复杂度O(n^2)

快排思想–分支思想（不稳定算法）

  1. 确定分界点：区间左端点，区间右端点，区间中点，随机选点。 （四选一）

  2. 调整区间： 让小于等于分界点的值在分界点的左边，让大于等于分界点的值在分界点右边

  3. 递归处理左右两段

  4. 具体实现采用双指针方法，指针 i 指向左端， 指针 j 指向右端，每次判断i指针是否小于分界点，j指针是否大于分界点。 当i指针值大于x停止移动，当j指针小于x停止移动，交换i，j指针所指的值，当i==j停止，递归左右区间。

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    
    int x = q[(l + r) / 2]; //   int x = q[l + r >> 1]; 如何一组数字是升序，则选择 int x = q[l] 会编程o(n ^ 2)
    int i = l - 1;
    int j = r + 1;
    while (i < j)
    {
        do i ++; while (q[i] < x);
        do j --; while (q[j] > x);
        
        if (i < j) swap(q[i], q[j]);
    }
    
    printf("%d %d\n", i , j);
    
    // i 是有可能大于 j 的(i >= j)，所以分界只能取 [l, j], [j+1, r]; 或者 [l, i-1], [i, r]
    // 注意取j时，q[l + r >> 1] 取 i 时， q[l + r + 1 >> 1], 两个模板背住一个就行。取 j 的背住
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
    
    
}

int main()
{
    int n;
    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]);
    
    return 0;
    
    
}
FEATURED TAGS