《算法导论》学习笔记

排序算法

Posted by Felix Zhang on 2020-05-15
Words 575 and Reading Time 3 Minutes
Viewed Times

算法导论专题：排序

方法一：插入排序

方法二：归并排序

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
50
51
52
53
#include <iostream>
#include <vector>
using namespace std;

#define INFTY 100000000
//创建两个新数组进行归并
void merge(vector<int>& A, int i, int f){
    int mid = (i + f)/2;
    vector<int> R, L;
    for (int j = i; j <= mid; j++){
        L.push_back(A[j]);
    }
    for (int j = mid + 1; j <= f; j++){
        R.push_back(A[j]);
    }
    L.push_back(INFTY);
    R.push_back(INFTY);
    int a = 0, b = 0;
    for (int j = i; j <= f; ++j){
        if(L[a] <= R[b]){
            A[j] = L[a];
            a++;
        }else{
            A[j] = R[b];
            b++;
        }
    }
}
//归并排序
void mergesort(vector<int>& A, int i, int f){
    if(i < f){
        int mid = (i + f)/2;
        mergesort(A, i, mid);
        mergesort(A, mid+1, f);
        merge(A, i, f);
    }
}
//主函数
int main(){
    vector<int> A;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i){
        int tmp;
        scanf("%d", &tmp);
        A.push_back(tmp);
    }
    mergesort(A, 0, n - 1);
    for (int i = 0; i < n; ++i){
        printf("%d ", A[i]);
    }
    return 0;
}

方法三：随机化快速排序

特点

（1）最坏时间复杂度为$O(n^2)$，期望时间复杂度为$\Theta(n\lg n)$，具体时间依赖于输入数组的特征；

（2）隐藏的常数因子很小，并且可以进行原址排序；

（3）属于非稳定排序方法；

随机化处理方法

选取一个数组，取一个随机数，将最末尾元素与随机数指示的元素交换；

选定末尾元素为主元，遍历数组一遍，分为小于，大于两个部分；

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
#include <iostream>
#include <vector>

int partition(std::vector<int>& A, int i, int f){
    int x = A[f];//取最后一个元素y为基元
    int k = i - 1;
    for (int j = i; j <= f - 1; ++j){
        if(A[j] < x){
            k = k + 1;
            int tmp = A[k];
            A[k] = A[j];
            A[j] = tmp;
        }
    }
    int tmp2 = A[k+1];
    A[k+1] = A[f];
    A[f] = tmp2;
    return k+1;
}

void QuickSort(std::vector<int>& A, int i, int f){
    if(i < f){
        int q = partition(A, i, f);
        QuickSort(A, i, q-1);
        QuickSort(A, q+1, f);
    }
}

int main() {
    std::vector<int> A;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i){
        int input;
        scanf("%d", &input);
        A.push_back(input);
    }
    QuickSort(A, 0, n - 1);
    for (int i = 0; i < n; ++i){
        printf("%d ", A[i]);
    }
    return 0;
}

方法四：桶排序

This is copyright.

FEATURED TAGS
《算法导论》学习笔记
FRIENDS