经典排序部分算法实现(C语言)

表格描述

中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
选择排序 Selection n2 n2 n2 1 不稳
冒泡排序 Bubble n2 n2 n 1 稳
插入排序 Insertion n2 n2 n 1 稳
堆排序 Heap nlog2n nlog2n nlog2n 1 不稳
希尔排序 Shell n1.3 n2 n 1 不稳
归并排序 Merge nlog2n nlog2n nlog2n n 稳
快速排序 Quick nlog2n n2 nlog2n nlog2n 不稳
桶排序 Bucket n + k n2 n n + k 稳
计数排序 Counting n + k n + k n + k n + k 稳
基数排序 Radix n * k n * k n * k n + k 稳

代码部分实现

选择排序

选择排序就是找到最大 / 最小的元素放在最后, 然后一个一个堆在数组一端最终完成排序, 代码如下

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
#include <stdio.h> 

void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int find_max_index(int arr[], int n) {
    int max_pos = 0;
    int max = arr[0];
    
    for (int i = 0; i < n; i++) {
        if (arr[i] > max) {
			max = arr[i];
            max_pos = i;
        }
    }
    return max_pos;
}

void selection_sort(int arr, int n) {
    while (n > 1) {
        int max_pos = find_max_index(arr, n);
        swap(arr, max_pos, n - 1);
        n--;
    }
}

int main() {
    int arr[] = {1, 3, 2, 4, 0, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    selection_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d\n", arr[i]);
    }
    return 0;
}

冒泡排序

冒泡排序和选择排序类似, 从第一个元素开始, 每走一趟, 将一个最大 / 最小的元素放在数组的一端, 成为”一趟” 排序, 当完成n - 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
#include <stdio.h>

void swap(int arr[], int i, int j) {
    int temp = arr[i]; 
    arr[i] = arr[j];
    arr[j] = temp;
}

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = i; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j + 1, j);
            }
        }
    }
} 

int main() {
    int arr[] = {1, 3, 2, 4, 0, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d\n", arr[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
#include <stdio.h>

void insert(int arr[], int n) {
    int i = n;
    int key = arr[n];
    while (arr[i - 1] > key && i > 0) {
        arr[i] = arr[i - 1];
        i--;
    }

    arr[i] = key;
}

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        insert(arr, i);
    }
}

int main() {
    int arr[] = {1, 3, 2, 4, 0, 1, 2};
    int n = 7; 
    insertion_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d\n", arr[i]);
    }
    return 0;
}

堆排序

堆排序就是将一个堆(“完全二叉树”), 每次将最小 / 最大的元素与最后一个叶子节点交换, 然后将最后一个叶子节点(最大 / 最小值)其砍断, 放在数组中, 将剩余的元素继续构建成一个堆, 直到堆中的元素个数为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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>

void heapify(int arr[], int i, int n) {
    if (i >= n) {
        return;
    }
    int c1 = 2 * i + 1;
    int c2 = 2 * i + 2;
    
    int max = i;
    
    // for c1 < n means that child must not out of range of this tree
    if (c1 < n && arr[c1] > arr[max]) {
        max = c1;
    }
    
    if (c2 < n && arr[c2] > arr[max]) {
        max = c2;
    }
    
    if (max != i) {
    	swap(arr, max, i);
        // continue to heapify, make it a big tree
        heapify(arr, max, n);
    }
}

void build_tree(int arr[], int n) {
    int last_node = n - 1;
    int parent = (last_node - 1) / 2;
    
    for (int i = parent; i >= 0; i--) {
        heapify(arr, i, n);
    }
}

void heap_sort(int arr[], int n) {
    build_tree(arr, n);
    for (int i = n - 1; i >= 0; i--) {
        swap(arr, 0, i);
        heapify(arr, 0, i);
    }
}

int main() {
    int arr[] = {1, 3, 2, 4, 0, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    heap_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d\n", arr[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
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
#include <stdio.h>

void merge(int arr, int r, int m, int l) {
    int left_size = m - r;
    int right_size = l - m + 1;
    
    int left[left_size];
    int right[right_size];
    
    int i, j, k;
    // fill left and right sub array
    for (i = l; i < m; i++) {
        left[i - l] = arr[i];
    }
    
    for (i = m; i <= r; i++) {
        right[i - m] = arr[i];
    }
    // i is index for left array, and j is for right here
    // k is index of complete array
    while (i < left_size && j < right_size) {
        if (left[i] < right[j]) {
        	arr[k++] = left[i++];    
        }
        else {
            arr[k++] = right[j++];
        }
    }
    
 	// if one of left and right arrays finish
    // and then the other one will fill the back
    while (i < left_size) {
        arr[k++] = left[i++];
    }
    
    while (j < right_size) {
        arr[k++] = right[j++];
    }
    
}

void merge_sort(int arr[], int l, int r) {
	// flag for recursion compeleting
    if (l == r){
        return;
    }
    int m = (r + l) / 2;
    merge_sort(arr, l, m);
    merge_sort(arr, m + 1, r);
    merge(arr, l, m, r);
}

int main() {
    int arr[] = {1, 3, 2, 4, 0, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    merge_sort(arr, 0, n);
    for (int i = 0; i < n; i++) {
        printf("%d\n", arr[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
37
38
39
40
41
#include <stdio.h>

void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int partition(int arr[], int low, int high) {
    int i = low - 1;
    int pivot = arr[high];
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quick_sort(arr, low, p - 1);
        quick_sort(arr, p + 1, high);
    }
}

int main() {
    int arr[] = {1, 3, 2, 4, 0, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    quick_sort(arr, 0, n);
    
    for (int i = 0; i < high; i++) {
        printf("%d\n", arr[i]);
    }
    return 0;
}

总结

以上的各种排序算法, 实际上全是通过元素的比较与交换进行. 所以在进行排序的过程就是进行比较的过程

使用c语言的主要目的是, c语言比较简单, 所有的语句都要自己写, 更能使读者方便.

以上使用的全部是最通俗的c语言, 没有使用指针以及引用类型

以下是swap的引用类型写法, 使得swap的函数可读性更强.

1
2
3
4
5
void swap(int &a, int &b) {
	int temp = &a; 
	&a = &b;
	&b = temp;
}

如有错误, 欢迎评论区, 或者联系我进行改正,谢谢