目录
引言
算法全景概览
算法详解与实现
1. 冒泡排序（Bubble Sort）
2. 插入排序（Insertion Sort）
3. 选择排序（Selection Sort）
4. 快速排序（Quick Sort）
5. 堆排序（Heap Sort）
6. 归并排序（Merge Sort）
7. 希尔排序（Shell Sort）
8. 计数排序（Counting Sort）
9. 桶排序（Bucket Sort）
10. 基数排序（Radix Sort）
综合对比表：编辑
选型策略指南：
最佳实践建议：
引言
排序算法是计算机科学的基石，也是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的数组存储计数，并初始化为0int* 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²)算法理解排序本质
-
熟练手写快速排序和归并排序
-
特殊排序算法需明确数据特征再使用