当前位置: 代码迷 >> 综合 >> 0x01. 基本算法 — 快速排序
  详细解决方案

0x01. 基本算法 — 快速排序

热度:91   发布时间:2023-11-26 19:48:43.0

算法分析:

  • 时间复杂度: n l o g n nlog_n nlogn?
  • 思想:快速排序是一种基于分治的思想。
  • 实现步骤:给定一个待排列的数组q[N],其中L为左端点,R为右端点。
    1. 确定分界点并定义i,j指针:可选q[l]或者q[r]或者q[mid]或者任意值作为分界点。
    2. 调整区间:调整区间的目的是为了让分界点的左边的值都小于等于分界点,让分界点右边的值都大于等于分界点。
    3.递归处理左右两段:分别递归处理左右两个区间即可。

code:

#include<cstdio>
#include<iostream>
using namespace std;const int N = 100010;int n;
int q[N];void quick_sort(int q[], int l, int r)
{
    //递归边界if(l >= r) return;//1.取分界点,建议取中间值。int mid = q[l + r >> 1], i = l - 1, j = r + 1;//2.调整区间while(i < j){
    do i ++; while(q[i] < mid);//i最后一定会停在一个大于等于mid的值上do j --; while(q[j] > mid);//j最后一定会停在一个小于等于mid的值上if(i < j) swap(q[i], q[j]);}//3.递归处理左右边界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]);return 0;
}

总结:

  • 1.定义的i,j指针:
    1.1 i指针:找到一个大于等于分界值的位置就停下来。
    1.2 j指针:找到一个小于等于分界值的位置就停下来。

  • 2.平均意义下是 O ( n l o g n ) O(nlogn) O(nlogn) 的,这里的详细证明可以参考《算法导论》。如果每次划分的两个区间里都有一个长度是1,那么就会递归 n 层,每层的计算量都是 O(n),所以总时间复杂度就是 O ( n 2 ) O(n^2) O(n2) 的。

  • 因此建议不要以q[l]或者q[r]作为分界值。否则很退化为 O ( n 2 ) O(n^2) O(n2)导致超时。

  • 3.建议写法如下:

  • 3.1 分界点取 ( l + r ) / 2 (l + r) / 2 (l+r)/2

  • 3.2 递归左右区间时,用 j j j来划分区间。

习题:

P1177 【模板】快速排序