常用排序算法模板

发表于 | 更新于 | 分类于 | 阅读次数：

冒泡排序

1
2
3
4
5
6
7
8
9
void bubbleSort(int arr[]) {
    init(arr);
    for (int i = 0; i < len-1; i++)
        for (int j = 0; j < len-1-i; j++)
            if (arr[j] > arr[j+1])
                swap(arr, j, j+1);
    printf("Bubble Sort:\t");
    print(arr);
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
void selectionSort(int arr[]) {
    init(arr);
    for (int i=0; i<len-1; i++) {
        int mmin = i;
        for (int j=i+1; j<len; j++)
            if (arr[j] < arr[mmin])
                mmin = j;
        swap(arr, i, mmin);
    }
    printf("Selection Sort:\t");
    print(arr);
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertionSort(int arr[]) {
    init(arr);
    for (int i=1; i<len; i++) {
        int toInsert = arr[i];
        int index = i - 1;
        int j = i - 1;
        for (; j >= 0 && arr[j] > toInsert; j--)
            arr[j+1] = arr[j];
        arr[j+1] = toInsert;
    }
    printf("Insertion Sort:\t");
    print(arr);
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void shellSort(int arr[]) {
    init(arr);
    for (int gap = len/2; gap > 0; gap /= 2) {
        for (int i=gap; i < len; i++) {
            int toInsert = arr[i];
            int j = i - gap;
            for (; j >= 0 && arr[j] > toInsert; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = toInsert;
        }
    }
    printf("Shell Sort:\t");
    print(arr);
}

归并排序

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
void merge(int arr[], int tmp[], int l, int r) {
    int m = (l + r) >> 1;
    int i = l;
    int j = m + 1;
    for (int k = l; k <= r; k++) {
        if (i > m)
            tmp[k] = arr[j++];
        else if (j > r)
            tmp[k] = arr[i++];
        else if (arr[i] > arr[j])
            tmp[k] = arr[j++];
        else
            tmp[k] = arr[i++];
    }
}

void mergeSort(int arr[], int tmp[], int l, int r) {
    if (l >= r) return;
    int m = (l + r) >> 1;
    mergeSort(arr, tmp, l, m);
    mergeSort(arr, tmp, m+1, r);
    merge(arr, tmp, l, r);
    for (int i=l; i<=r; i++)
        arr[i] = tmp[i];
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int partition(int arr[], int l, int r) {
    srand(time(0));
    int pivot = (rand() % (r - l + 1)) + l;
    swap(arr, l, pivot);
    int last = l + 1;
    for (int i = last; i <= r; i++)
        if (arr[i] < arr[l])
            swap(arr, i, last++);
    swap(arr, l, last - 1);
    return last - 1;
}

void quickSort(int arr[], int l, int r) {
    if (l >= r) return;
    int pivotIndex = partition(arr, l, r);
    quickSort(arr, l, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, r);
}

堆排序

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
void heapify(int arr[], int cur, int n) {
    int l = cur * 2 + 1;
    int r = cur * 2 + 2;
    int smallest = cur;
    if (l < n && arr[l] > arr[smallest])
        smallest = l;
    if (r < n && arr[r] > arr[smallest])
        smallest = r;
    if (smallest != cur) {
        swap(arr, cur, smallest);
        heapify(arr, smallest, n);
    }
}

void buildHeap(int arr[]) {
    for (int i = len; i>=0; i--)
        heapify(arr, i, len);
}

void heapSort(int arr[]) {
    init(arr);
    buildHeap(arr);
    for (int i = len-1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, 0, i);
    }
    printf("Heap Sort:\t");
    print(arr);
}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void countSort(int arr[]) {
    init(arr);
    const int k = 9;
    int bucket[k + 1]; // k is the largest value in the array
    for (int i=0; i<=k; i++)
        bucket[i] = 0;
    for (int i=0; i<len; i++)
        bucket[arr[i]]++;
    int lastSorted = -1;
    for (int i=0; i<=k; i++)
        while (bucket[i] > 0) {
            arr[++lastSorted] = i;
            bucket[i]--;
        }
    printf("Count Sort:\t");
    print(arr);
}

调用和时间、空间复杂度

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
const int len = 10;
const int origin[len] = {7, 6, 3, 3, 1, 4, 9, 8, 2, 5};

void init(int arr[]) {
    for (int i = 0; i < len; i++)
        arr[i] = origin[i];
}

void print(int arr[]) {
    for (int i = 0; i < len-1; i++)
        printf("%d ", arr[i]);
    printf("%d\n", arr[len-1]);
}

void swap(int arr[], int i, int j) {
    if (i == j) return;
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

int main() {
    int arr[len];
    init(arr);
    printf("Original Array:\t");
    print(arr);

    // 1
    // 最佳情况：T(n) = O(n)   最差情况：T(n) = O(n2)   平均情况：T(n) = O(n2)
    // 空间复杂度：O(1) 稳定
    bubbleSort(arr);

    // 2
    // 最佳情况：T(n) = O(n2)  最差情况：T(n) = O(n2)  平均情况：T(n) = O(n2)
    // 空间复杂度：O(1) 不稳定
    selectionSort(arr);

    // 3
    // 最佳情况：T(n) = O(n)   最坏情况：T(n) = O(n2)   平均情况：T(n) = O(n2)
    // 空间复杂度：O(1) 稳定
    insertionSort(arr);

    // 4
    // 最佳情况：T(n) = O(nlog2 n)  最坏情况：T(n) = O(nlog2 n)  平均情况：T(n) =O(nlog n)　
    // 空间复杂度：O(1) 不稳定
    shellSort(arr);

    // 5
    // 最佳情况：T(n) = O(n)  最差情况：T(n) = O(nlogn)  平均情况：T(n) = O(nlogn)
    // 空间复杂度：O(n) 稳定
    int tmp[10];
    init(arr);
    mergeSort(arr, tmp, 0, len-1);
    printf("Merge Sort:\t");
    print(arr);

    // 6
    // 最佳情况：T(n) = O(nlogn)   最差情况：T(n) = O(n2)   平均情况：T(n) = O(nlogn)
    // 空间复杂度：O(logn) 不稳定
    init(arr);
    quickSort(arr, 0, len-1);
    printf("Quick Sort:\t");
    print(arr);

    // 7
    // 最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
    // 空间复杂度：O(1) 不稳定
    heapSort(arr);

    // 8
    // 最佳情况：T(n) = O(n+k)  最差情况：T(n) = O(n+k)  平均情况：T(n) = O(n+k)
    // 空间复杂度：O(k) 稳定
    countSort(arr);
    
    // 9
    // 最佳情况：T(n) = O(n * k)   最差情况：T(n) = O(n * k)   平均情况：T(n) = O(n * k)
    // 空间复杂度：O(n + k) 稳定
    // radixSort(arr);

    // 10
    // 最佳情况：T(n) = O(n+k)   最差情况：T(n) = O(n+k)   平均情况：T(n) = O(n2）
    // 空间复杂度：O(n + k) 稳定
    // Bucket Sort
    
    return 0;
}