目录
引言
排序算法是计算机科学的基石，也是C语言初学者的必经之路。本文将深入解析十大基础排序算法的核心思想，并提供可直接运行的C语言代码实现。通过时间复杂度对比和应用场景分析，帮助读者构建完整的排序知识体系。
算法全景概览
基础算法三部曲：冒泡、插入、选择
高效排序三剑客：快速、归并、堆
特殊场景利器：希尔、计数、桶、基数
算法详解与实现
1. 冒泡排序（Bubble Sort）
核心原理：通过相邻元素交换"浮起"最大值
优化技巧：添加flag标记提前终止
void bubbleSort(int arr[], int n)
{
for (int i = 0; i < n-1; i++)
{
int swapped = 0;
for (int j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]); //就是交换函数
swapped = 1;
}
}
if (!swapped) break;
}
}2. 插入排序（Insertion Sort）
核心原理：构建有序序列，逐个插入元素
最佳场景：近乎有序的短数据
void insertionSort(int arr[], int n)
{
for (int i = 1; i < n; i++)
{
int t = a[i];
int j = i - 1;
while ((j >= 0) && (a[j] > t))
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = t;
}
}3. 选择排序（Selection Sort）
核心原理：每次选择最小元素放置到位
显著特点：交换次数恒为O(n)
void selectionSort(int arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
int t = i;
for (int j = i + 1; j < n; j++)
{
if (a[j] > a[t])
{
t = j;
}
}
if (t != i)
{
int temp = a[i];
a[i] = a[t];
a[t] = temp;
}
}
}4. 快速排序（Quick Sort）
核心原理：分治策略+基准值分区
关键优化：三数取中法选择基准
int a[101], n;
void quicksort(int left, int right)
{
int i, j, temp;
if (left > right)
{
return;
}
temp = a[left];
i = left;
j = right;
while (i != j)
{
while (a[j] >= temp && i < j)
{
j--;
}
while (a[i] <= temp && i < j)
{
i++;
}
if (i < j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
a[left] = a[i];
a[i] = temp;
quicksort(left, i - 1);
quicksort(i + 1, right);
}5. 堆排序（Heap Sort）
核心原理：构建大顶堆实现选择排序
空间优势：原地排序O(1)空间
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/*维护堆的性质
a 存储堆的数组
n 数组长度
i 待维护结点的下标
*/
void heapify(int a[], int n, int i)
{
int largest = i;
int lson = i * 2 + 1;
int rson = i * 2 + 2;
if (lson < n && a[largest] < a[lson])
{
largest = lson;
}
if (rson < n && a[largest] < a[rson])
{
largest = rson;
}
if (largest != i)
{
swap(&a[largest], &a[i]);
heapify(a, n, largest);
}
}
void heap_sort(int a[], int n)
{
//建堆
int i;
for (i = n / 2 - 1; i >= 0; i--)
{
heapify(a, n, i);
}
//排序
for (int j = n - 1; j > 0; j--)
{
swap(&a[j],&a[0]);
heapify(a, j, 0);
}
}6. 归并排序（Merge Sort）
核心原理：分治+有序数组合并
稳定特性：保持相等元素原始顺序
void merge(int a[], int tempa[], int left, int mid, int right)
{
//标记左半区第一个未排序的元素
int l_pos = left;
//标记右半区第一个未排序的元素
int r_pos = mid + 1;
//临时数组元素的下标
int pos = left;
//合并
while (l_pos <= mid && r_pos <= right)
{
if (a[l_pos] < a[r_pos])
{
tempa[pos++] = a[l_pos++];
}
else
{
tempa[pos++] = a[r_pos++];
}
}
//合并左半区剩余的元素
while (l_pos <= mid)
{
tempa[pos++] = a[l_pos++];
}
//合并右半区剩余的元素
while (r_pos <= right)
{
tempa[pos++] = a[r_pos++];
}
//把临时数组中的元素复制到原来的数组
while (left <= right)
{
a[left] = tempa[left];
left++;
}
}
void msort(int a[], int tempa[], int left, int right)
{
//如果只有一个元素，那么就不需要继续划分
//只有一个元素的区域，本身就是有序的，只需要呗归并即可
if (left < right)
{
//找中间点
int mid = (left + right) / 2;
//递归划分左半区
msort(a, tempa, left, mid);
//递归划分右半区
msort(a, tempa, mid + 1, right);
//合并
merge(a, tempa, left, mid, right);
}
}
//归并排序入口
void merge_sort(int a[], int n)
{
//分配一个数组
int* tempa = (int*)malloc(n * sizeof(int));
if (tempa)//数组分配成功
{
msort(a, tempa, 0, n - 1);
free(tempa);
}
else
{
printf("error:分配失败");
}
}7. 希尔排序（Shell Sort）
核心原理：分组插入排序+逐步缩小间隔
优势场景：中等规模数据
void shellsort(int a[], int n)
{
for (int gap = n / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < n; i++)
{
int temp = a[i];
int j;
for (j = i; j >= gap && a[j - gap] > temp; j -= gap)
{
a[j] = a[j - gap];
}
a[j] = temp;
}
}
}8. 计数排序（Counting Sort）
核心原理：统计元素频次实现排序
限制条件：整数且范围较小
void counting_sort(int a[], int len)
{
if (len < 1) return;
//寻找最大元素
int max = a[0];
for (int i = 1; i < len; i++)
{
if (a[i] > max)
{
max = a[i];
}
}
//分配一个长度为max+1的数组存储计数，并初始化为0
int* count = (int*)malloc(sizeof(int) * (max + 1));
memset(count, 0, sizeof(int) * (max + 1));
//计数
for (int i = 0; i < len; i++)
{
count[a[i]]++;
}
//统计计数的累计值
for (int i = 1; i < max + 1; i++)
{
count[i] += count[i - 1];
}
//创建一个临时数组保存结果
int* output = (int*)malloc(sizeof(int) * len);
//将元素放在正确的位置上
for (int i = 0; i < len; i++)
{
output[count[a[i]] - 1] = a[i];
count[a[i]]--;
}
//将结果复制回原数组
for (int i = 0; i < len; i++)
{
a[i] = output[i];
}
free(count);
free(output);
}9. 桶排序（Bucket Sort）
核心原理：数据分桶+各桶单独排序
最佳实践：均匀分布的数据集
void bucket_sort(int a[], int len)
{
int max = a[0];
int i, j;
//找到最大元素申请桶数组
for (i = 1; i < len; i++)
{
if (a[i] > max)
{
max = a[i];
}
}
int* temp = (int*)malloc(sizeof(int) * (max + 1));
memset(temp, 0, sizeof(int) * (max + 1));
//遍历原始数组，原始数组的数据作为桶数组的下标，然后加一表示数据
for (i = 0; i < len; i++)
{
temp[a[i]]++;
}
//遍历桶数组，有数据的把下标打印出来
for (i = 0, j = 0; i < max + 1; i++)
{
while (temp[i])
{
a[j] = i;
j++;
temp[i]--;
}
}
}
10. 基数排序（Radix Sort）
核心原理：按位排序（LSD/MSD）
特殊要求：等长数据元素
int getMax(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max) max = arr[i];
return max;
}
void countSortForRadix(int arr[], int n, int exp)
{
int output[n];
int count[10] = {0};
for (int i = 0; i < n; i++)
count[(arr[i]/exp)%10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i-1];
for (int i = n-1; i >= 0; i--)
{
output[count[(arr[i]/exp)%10]-1] = arr[i];
count[(arr[i]/exp)%10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSort(int arr[], int n)
{
int max = getMax(arr, n);
for (int exp = 1; max/exp > 0; exp *= 10)
countSortForRadix(arr, n, exp);
} 综合对比表：
选型策略指南：
小数据量（n ≤ 1000）
优先选择插入排序（性能接近O(n)）
需要稳定时用冒泡排序
通用场景
快速排序（综合最优）
归并排序（需要稳定性时）
内存敏感场景
堆排序（原地排序）
希尔排序（改进版插入）
特殊数据特征
整数小范围：计数排序
多位数特征：基数排序
均匀分布：桶排序
最佳实践建议：
掌握至少三种O(n²)算法理解排序本质
熟练手写快速排序和归并排序
特殊排序算法需明确数据特征再使用