选择排序
选择排序是一种简单直观的排序算法，其核心思想是：遍历数组，从未排序的序列中找到最小元素，将其放到已排序序列的末尾。
时间复杂度：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; } } }} |
