acwing基础课ch1-排序问题

Shen 收录于算法基础课

2021-08-24 约 2168 字预计阅读 5 分钟

排序

复杂度分析

快速排序

基于分治思想

主要步骤

确定分界点x，随机(一般为左端点)
调整范围，左半边小于等于x，右半边大于等于x（双指针）。
1. 如果忘记了双指针方法，可以暴力开数组求解。
递归处理左右区间。

复杂度分析

最坏时间复杂度发生在数组有序的时候，数组有序时，每次划分的区间都是左边界，时间复杂度时$O(n^2)$
最好时间复杂度：切分点在数组中间，$C_n = 2C_{n/2} + n$,$T:O(nlogn)$
平均时间复杂度：切分点的期望是在数组中间，因此平均复杂度就是最好的时间复杂度。
空间复杂度：$O(logn)$递归栈调用，最差为$O(n)$

Acwing785. 快速排序

快速选择切分，递归进行左右半边的区间排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int a[N];

int Quick_Select(int a[], int l, int r){
    if(l >= r) {
        return l; 
    }
    swap(a[l], a[l+r>>1]);
    int x = a[l] ,i = l, j = r+1;
    // 如果超出了数据范围break即可
    while(i < j){
        // i最差为r
        while(i < r && a[++i] < x);
        // j最差为l
        while(j > l && a[--j] > x);
        if(i < j)   swap(a[i], a[j]);
    }
    swap(a[l], a[j]);
    return j;
}


void Quick_Sort(int a[], int l, int r){
    if(l >= r)  return;
    int j = Quick_Select(a, l, r);
    // cout << l << ' ' << r << ' ' << j << endl;
    Quick_Sort(a, l, j-1);
    Quick_Sort(a, j+1, r);
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n; i++){
        scanf("%d", &a[i]);
    }
    Quick_Sort(a, 0, n-1);
    for(int i = 0;i < n; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

高级短代码做法

一直选取做边界会超时
选择中值或者随机取值则不会超时。
while循环结束后$q[l…j]<=x, q[j+1…r]>=x$
j的取值范围为$l, r-1$，所以不会一直不划分边界
只能取大于或者小于号是因为交换原来的数字进行了限位，不会产生数组溢出的问题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int a[N];

void Quick_Sort(int a[], int l, int r){
    if(l >= r)  return;
    // 注意这里i,j都与开始值差一位
    int x = a[l], i = l - 1, j = r + 1;
    // 循环结束后,a[l...j] <= x, a[j+1...r] >= x
    while(i < j){
        // 这里不能用等号，是因为交换让目标值做限位的作用
        while(a[++i] < x);
        while(a[--j] > x);
        if(i < j)   swap(a[i], a[j]);
    }
    cout <<l << ' '<< r << ' ' << j << ' ' << endl;
    // j取值范围时[l, r-1]不存在0和n区间无限循环
    // j最小值大于等于l
    Quick_Sort(a, l, j);
    Quick_Sort(a, j+1, r);
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n; i++){
        scanf("%d", &a[i]);
    }
    Quick_Sort(a, 0, n-1);
    for(int i = 0;i < n; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

快慢指针版本，数据量较大时候，由于多次交换，会超时。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int a[N];

void Quick_Sort(int a[], int l, int r){
    // 快慢指针版本
    if(l >= r)  return;
    swap(a[l], a[l + r >> 1]);
    int x = a[l], i = l;
    for(int j = l+1; j <= r; j++){
        if(a[j] <= x){
            swap(a[j], a[++i]);
        }
    }
    swap(a[i], a[l]);
    Quick_Sort(a, l, i-1);
    Quick_Sort(a, i+1, r);
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n; i++){
        scanf("%d", &a[i]);
    }
    Quick_Sort(a, 0, n-1);
    for(int i = 0;i < n; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

786. 第k个小的数

排序

$T:O(nlogn), S:O(logn)$

大顶堆

$T:O(nlogk),S:O(k)$，结果有序

快速选择

平均复杂度：$T:O(n),S:O(logn)$
最坏复杂度：$T:O(n^2),S:O(n)$
时间复杂度计算方法：https://blog.csdn.net/rainchxy/article/details/78957851

快慢指针的快速选择切分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


#include <iostream>
#include <algorithm>
#include <stdlib.h>

using namespace std;

const int N = 1e5+10;
int a[N];

int Quick_Select(int a[], int l, int r, int k){
    if(l >= r)  return a[l];
    
    // 添加随机性
    int rand_idx = rand() % (r - l + 1) + l;
    swap(a[rand_idx], a[l]);
    
    int x = a[l], i = l, j = r + 1;
    while(i < j){
        // i 最差为 r
        while(i < r && a[++i] < x);
        // j 最差为 l
        while(j > l && a[--j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    swap(a[l], a[j]);
    
    if(j - l + 1 == k)  return a[j];
    else if(j - l + 1 > k)  return Quick_Select(a, l, j - 1, k);
    else return Quick_Select(a, j + 1, r, k - (j - l + 1));
}

int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    int l = 0, r = n - 1;
    
    cout << Quick_Select(a, l, r, k) << endl;

    return 0;
    
}

高级基于快速排序的快速选择。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int a[N];

int Quick_Sort(int a[], int l, int r, int k){
    if(l >= r)  return a[l];
    int x = a[l], i = l - 1, j = r + 1;
    while(i < j){
        while(a[++i] < x);
        while(a[--j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    if(j - l + 1 >= k)  Quick_Sort(a, l, j, k);
    else    Quick_Sort(a, j+1, r, k - (j - l + 1));
}

int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    cout << Quick_Sort(a, 0, n-1, k);
    return 0;
    
}

归并排序

本质：将两个排序好的队列进行合并的过程。

步骤

确定分界点。
递归划分区间。
双执政归并合并两个有序序列。

复杂度分析

$T:O(nlogn)$
$S:O(n)$，辅助数组进行赋值操作

787. 归并排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int a[N];
int temp[N];

void merge(int a[], int l, int mid, int r){
    int i = l, j = mid+1, cur = 0;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]){
            temp[cur++] = a[i++];
        }else{
            temp[cur++] = a[j++];
        }
    }
    while(i <= mid)    temp[cur++] = a[i++];
    while(j <= r)   temp[cur++] = a[j++];
    for(int i = l, j = 0; j < cur; i++, j++){
        a[i] = temp[j];
    }
}

void merge_sort(int a[], int l, int r){
    if(l >= r)  return;
    int mid = l + r >> 1;
    
    merge_sort(a, l, mid);
    merge_sort(a, mid+1, r);
    
    merge(a, l, mid, r);
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    
    merge_sort(a, 0, n-1);
    
    for(int i = 0; i < n; i++){
        printf("%d ", a[i]);
    }
}

788. 逆序对的数量

归并思想

i 前面的数均小于j
$T:O(nlogn)$
$S:O(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5+10;
int a[N];
int temp[N];

LL merge_reverse_num(int a[], int l, int r){
    if(l >= r)  return 0;
    int mid = l + r >> 1;
    LL res = merge_reverse_num(a, l, mid) + merge_reverse_num(a, mid+1, r);
    int i = l, j = mid + 1, cur = 0;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]){
            temp[cur++] = a[i++];
        }else{
            // a[i] > a[j] -> + mid - i + 1
            res += mid - i + 1;
            temp[cur++] = a[j++];
        }
    }
    while(i <= mid) temp[cur++] = a[i++];
    while(j <= r)   temp[cur++] = a[j++];
    for(int i = l, j = 0; j < cur; i++, j++){
        a[i] = temp[j];
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    printf("%ld", merge_reverse_num(a, 0, n-1));
    return 0;
}

暴力(LTE)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5+10;
int a[N];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    LL res = 0;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(a[i] > a[j]) res += 1;
        }
    }
    printf("%ld", res);
    return 0;
    
}

目录

acwing基础课ch1-排序问题

排序

分类

复杂度分析

快速排序

主要步骤

复杂度分析

Acwing785. 快速排序

快速选择切分，递归进行左右半边的区间排序

高级短代码做法

快慢指针版本，数据量较大时候，由于多次交换，会超时。

786. 第k个小的数

排序

大顶堆

快速选择

快慢指针的快速选择切分

高级基于快速排序的快速选择。

归并排序

步骤

复杂度分析

787. 归并排序

788. 逆序对的数量

归并思想

暴力(LTE)