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