冒泡排序 (Bubble Sort)
从头到尾依次比较相邻元素，若顺序错误就交换位置,将较大（或较小）元素“冒泡”到序列末端
最佳时间复杂度:O(n)每一个数一对比就对了
平均时间复杂度:O(n^2)每一个数都要和其余数对比
最差时间复杂度:O(n^2)
空间复杂度:O(1)，原地排序
void bubble_sort(int arr[], int n) {
/* 外层循环控制趟数 (共 n-1 趟) */
for (int i = 0; i < n - 1; ++i) {
int swapped = 0; /* 标记本趟是否发生交换，用于提前结束 */
/* 内层循环：将本趟最大的元素“冒泡”到末尾 */
for (int j = 0; j < n - 1 - i; ++j) {
if (arr[j] > arr[j + 1]) {
/* 交换相邻元素 */
int tmp;
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
swapped = 1;
}
}
/* 若本趟没有发生交换，说明数组已有序，可提前结束 */
if (!swapped) break;
}
}插入排序 (Insertion Sort)
先把序列的第一个元素视为已排序区，其余元素视为未排序区.从未排序部分取出一个数,放到已排序部分的正确位置
最佳时间复杂度:O(n)每一个数一对比就对了
平均时间复杂度:O(n^2)每一个数都要和其余数对比
最差时间复杂度:O(n^2)
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; ++i) { // 从第二个元素开始逐个插入
int key = arr[i]; // 待插入的元素
int j = i - 1;
/* 将比 key 大的元素向后移动，为 key 腾出位置 */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key; // 把 key 插入到正确的位置
}
}选择排序 (Selection Sort)
找到最小或最大的数,放到开头或结尾
最佳时间复杂度:O(n^2)每一个数都要和其余数对比
平均时间复杂度:O(n^2)
最差时间复杂度:O(n^2)
void selection_sort(int a[], int n)
{
for (int i = 0; i < n - 1; ++i)
{
/* 假设 a[i] 就是当前最小值的位置 */
int min_idx = i;
/* 在 [i+1, n-1] 区间中找真正的最小值索引 */
for (int j = i + 1; j < n; ++j)
if (a[j] < a[min_idx])
min_idx = j;
/* 若找到更小值，则把它换到“已排序区”末尾 */
if (min_idx != i)
{
int tmp = a[i];
a[i] = a[min_idx];
a[min_idx] = tmp;
}
}
}快速排序 (Quick Sort)
随便找一个数,将比它小的挪到左边,大的挪到右边,然后对两边递归使用快速排序直到没有可以排的为止.
最佳时间复杂度:O(n logn)每一个数调用递归且规模显著减小
平均时间复杂度:O(n logn)
最差时间复杂度:O(n^2)
void quicksort(int a[], int left, int right)
{
int i = left, j = right;
int pivot = a[(left + right) / 2]; /* 选取中间元素作为基准值,当然这里可以随便选 */
/* 一趟划分：把 <=pivot 的元素放左边，>=pivot 的元素放右边 */
while (i <= j)
{
while (a[i] < pivot) i++; /* 找到左侧第一个 ≥ pivot 的位置 */
while (a[j] > pivot) j--; /* 找到右侧第一个 ≤ pivot 的位置 */
if (i <= j) /* 若左右哨兵未交叉，则交换 */
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++; /* 继续向内收缩 */
j--;
}
}
/* 递归处理左右子区间 */
if (left < j) quicksort(a, left, j);
if (i < right) quicksort(a, i, right);
}或者直接使用qsort()
void qsort(void *base, size_t nmemb,
size_t size,
int (*compar)(const void *, const void *));归并排序 (Merge Sort)
分解:将现有元素递归一分为二直到为单个元素(默认有序)
合并:递归合并所有元素
时间复杂度:O(n logn)每一个数调用递归且规模显著减小
三路快速排序 (Turnary Quick Sort)
选择枢纽(pivot),然后递归小于和大于部分,适用于有大量重复值
平均时间复杂度:O(n log n)
最坏时间复杂度:O(n²)
堆排序 (Heap Sort)
建堆(大顶堆（升序所用）或小顶堆（降序所用）),将堆顶（当前最大或最小值）与末尾元素交换,堆区缩小 1，随后对新堆顶执行下沉恢复堆性质,当堆大小减到 1 时，数组已按升序排列
时间复杂度:O(n log n)