选择排序

选择排序是一种简单直观的排序算法，其核心思想是：遍历数组，从未排序的序列中找到最小元素，将其放到已排序序列的末尾。

时间复杂度：O(n^2)

稳定性 ：不稳定

/* * @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)

稳定性：稳定

实现：

/* @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)

稳定性：稳定

实现：

/* @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; } } } }