選擇排序
選擇排序是一種簡單直觀的排序算法，其核心思想是：遍歷數組，從未排序的序列中找到最小元素，將其放到已排序序列的末尾。
時間復雜度：O(n^2)
穩定性 ：不穩定
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/** @brief selection sort*/voidselection_sort(int a[], int n){ int i, j, min, tmp; for (i = 0; i < n - 1; ++i) { min = i; for (j = i+1; j < n; ++j) { if (a[j] < a[min]) { min = j; } } if (min != i) { tmp = a[min]; a[min] = a[i]; a[i] = tmp; } }} |
直接插入排序
直接插入排序是一種比較容易理解的排序算法，其核心思想是遍歷數組，將數組中的元素逐個插入到已排序序列中。
時間復雜度：O(n^2)
穩定性：穩定
實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/* @brief insetion sort* insert the new element to the sorted subarray*/voidinsertion_sort(int a[], int n){ int i, j, num; for (i = 1; i < n; ++i) { num = a[i]; for (j = i - 1; j >= 0 && a[j] > num; --j) a[j+1] = a[j]; a[j+1] = num; }} |
冒泡排序
冒泡排序是最基本的排序算法之一，其核心思想是從后向前遍歷數組，比較a[i]和a[i-1]，如果a[i]比a[i-1]小，則將兩者交換。這樣一次遍歷之后，最小的元素位于數組最前，再對除最小元素外的子數組進行遍歷。進行n次（n數組元素個數）遍歷后即排好序。外層循環為n次，內層循環分別為n-1， n-2…1次。
時間復雜度： O(n^2)
穩定性：穩定
實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
/* @brief bubble sort* move the smallest element to the front in every single loop*/voidbubble_sort(int a[], int n){ int i, j, tmp; for (i = 0; i < n; ++i) { for (j = n - 1; j > i; --j) { if (a[j] < a[j-1]) { tmp = a[j]; a[j] = a[j-1]; a[j-1] = tmp; } } }} |
