本文会从核心原理、算法逻辑、C 语言实现带注释、复杂度 / 稳定性四个维度讲解排序算法。前置说明稳定性定义排序后原数组中相等元素的相对位置不变 → 稳定反之不稳定。复杂度符号O()表示时间 / 空间复杂度n为数组元素个数k为数值范围 / 基数位数 / 桶数量按需定义。一、排序算法分类比较排序通过比较元素大小决定顺序包括冒泡、选择、插入、希尔、归并、快速、堆排序等。时间复杂度下界为 O(n log n)。非比较排序不通过比较利用元素本身的信息进行排序如计数排序、基数排序、桶排序时间复杂度可达到 O(n)。附加qsort() 库函数二、各排序算法详解1. 冒泡排序Bubble Sort核心原理像气泡上浮一样相邻元素两两比较把较大的元素逐步 “推” 到数组末尾每一轮只确定一个最大元素的位置。算法逻辑遍历数组从第 1 个元素开始依次比较相邻的两个元素如果前一个 后一个交换两者位置把大的元素往后挪每轮遍历后最大的未排序元素会 “冒泡” 到当前未排序区的末尾重复上述步骤直到所有元素有序可优化若某轮无交换直接终止。示例代码带优化#include stdio.h // 冒泡排序升序 void bubbleSort(int arr[], int n) { // 外层循环控制排序轮数最多n-1轮最后一个元素无需比较 for (int i 0; i n - 1; i) { int swapped 0; // 标记本轮是否发生交换优化用 // 内层循环遍历未排序区每轮减少i次比较已排序的i个元素在末尾 for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { // 交换相邻元素 int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; // 标记有交换 } } // 本轮无交换说明数组已完全有序直接退出 if (!swapped) { break; } } } // 辅助函数打印数组 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {64, 34, 25, 12, 22, 11, 90}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); bubbleSort(arr, n); printf(排序后); printArray(arr, n); return 0; }复杂度 稳定性时间复杂度最好O(n)数组已有序优化后仅 1 轮遍历最坏 / 平均O(n²)两层循环。空间复杂度O(1)仅用临时变量原地排序。稳定性稳定相等元素不交换。2. 选择排序Selection Sort核心原理每一轮从未排序区选最小或最大的元素放到已排序区的末尾减少交换次数冒泡每轮可能多次交换选择每轮仅 1 次。算法逻辑把数组分为 “已排序区”初始为空和 “未排序区”初始为整个数组遍历未排序区找到最小元素的下标交换 “未排序区第一个元素” 和 “最小元素”把最小元素加入已排序区重复步骤 2-3直到未排序区为空。示例代码#include stdio.h // 选择排序升序 void selectionSort(int arr[], int n) { // 外层循环控制已排序区的末尾位置i为已排序区最后一个元素的下标 for (int i 0; i n - 1; i) { int minIndex i; // 假设未排序区第一个元素是最小的 // 内层循环遍历未排序区找最小元素的下标 for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; // 更新最小元素下标 } } // 交换把最小元素放到已排序区末尾 int temp arr[i]; arr[i] arr[minIndex]; arr[minIndex] temp; } } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {64, 25, 12, 22, 11}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); selectionSort(arr, n); printf(排序后); printArray(arr, n); return 0; }复杂度 稳定性时间复杂度最好 / 最坏 / 平均都是O(n²)无论数组是否有序都要遍历找最小值。空间复杂度O(1)原地排序。稳定性不稳定例如数组[2, 2, 1]第一轮选 1 和第一个 2 交换两个 2 的相对位置改变。3. 插入排序Insertion Sort核心原理类似 “打牌时整理手牌”把未排序的元素逐个插入到已排序区的正确位置适合近乎有序的小数组。算法逻辑把数组第一个元素视为 “已排序区”从第二个元素开始记为current向前遍历已排序区若已排序区的元素 current则将该元素后移一位找到第一个 ≤current的元素把current插入到它的下一位重复步骤 2-4直到所有元素插入完成。示例代码#include stdio.h // 插入排序升序 void insertionSort(int arr[], int n) { // 外层循环遍历未排序区从第二个元素开始 for (int i 1; i n; i) { int current arr[i]; // 待插入的元素 int j i - 1; // 已排序区的最后一个元素下标 // 内层循环向前找插入位置同时后移比current大的元素 while (j 0 arr[j] current) { arr[j 1] arr[j]; // 元素后移 j--; } arr[j 1] current; // 插入到正确位置 } } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {12, 11, 13, 5, 6}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); insertionSort(arr, n); printf(排序后); printArray(arr, n); return 0; }复杂度 稳定性时间复杂度最好O(n)数组已有序仅需遍历 1 次最坏O(n²)数组逆序每个元素都要移到最前面平均O(n²)。空间复杂度O(1)原地排序。稳定性稳定相等元素不会交换位置。4. 希尔排序Shell Sort核心原理插入排序的 “升级版”先把数组按增量gap分组对每组做插入排序逐步缩小增量直到增量为 1此时退化为普通插入排序但数组已基本有序。算法逻辑初始化增量gap n/2常用增量策略也可自定义按gap分组对每组执行插入排序缩小增量如gap gap/2重复步骤 2当gap 1时完成最后一次插入排序数组有序。示例代码#include stdio.h // 希尔排序升序 void shellSort(int arr[], int n) { // 外层循环控制增量gap逐步缩小到1 for (int gap n / 2; gap 0; gap / 2) { // 内层循环对每个分组执行插入排序 for (int i gap; i n; i) { int current arr[i]; // 待插入的元素 int j; // 遍历当前分组的已排序区找插入位置 for (j i; j gap arr[j - gap] current; j - gap) { arr[j] arr[j - gap]; // 元素后移步长为gap } arr[j] current; // 插入到正确位置 } } } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {12, 34, 54, 2, 3}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); shellSort(arr, n); printf(排序后); printArray(arr, n); return 0; }复杂度 稳定性时间复杂度取决于增量策略常用gap n/2时平均O(n^1.3)最坏O(n²)最优增量如 Knuth 序列可接近O(n log n)。空间复杂度O(1)原地排序。稳定性不稳定分组插入时相等元素可能跨组交换破坏相对位置。5. 归并排序Merge Sort核心原理基于分治思想先把数组 “拆分” 成最小单元单个元素再把相邻的有序单元 “合并” 成更大的有序数组最终合并为完整的有序数组。算法逻辑拆分Divide把数组从中间分成左右两部分递归拆分直到每个子数组只有 1 个元素天然有序合并Merge创建临时数组对比左右两个有序子数组的元素按升序依次放入临时数组最后把临时数组复制回原数组。示例代码#include stdio.h #include stdlib.h // 用于malloc/free // 合并两个有序子数组arr[left..mid] 和 arr[mid1..right] void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; // 左子数组长度 int n2 right - mid; // 右子数组长度 // 动态分配临时数组避免栈溢出适合大数据 int *L (int *)malloc(n1 * sizeof(int)); int *R (int *)malloc(n2 * sizeof(int)); // 复制数据到临时数组 for (int i 0; i n1; i) L[i] arr[left i]; for (int j 0; j n2; j) R[j] arr[mid 1 j]; // 合并临时数组到原数组 int i 0, j 0, k left; // i:左子数组指针j:右子数组指针k:原数组指针 while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; i; } else { arr[k] R[j]; j; } k; } // 复制左子数组剩余元素 while (i n1) { arr[k] L[i]; i; k; } // 复制右子数组剩余元素 while (j n2) { arr[k] R[j]; j; k; } // 释放临时数组 free(L); free(R); } // 归并排序递归函数拆分 合并 void mergeSort(int arr[], int left, int right) { if (left right) { // 递归终止条件子数组长度为1 int mid left (right - left) / 2; // 避免溢出等价于(leftright)/2 mergeSort(arr, left, mid); // 拆分左半部分 mergeSort(arr, mid 1, right); // 拆分右半部分 merge(arr, left, mid, right); // 合并左右部分 } } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {12, 11, 13, 5, 6, 7}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); mergeSort(arr, 0, n - 1); // 递归调用左边界0右边界n-1 printf(排序后); printArray(arr, n); return 0; }复杂度 稳定性时间复杂度最好 / 最坏 / 平均都是O(n log n)拆分层数为log n每层合并操作是O(n)。空间复杂度O(n)需要临时数组存储合并结果递归版额外加O(log n)递归栈空间。稳定性稳定合并时相等元素优先取左子数组的保持相对位置。6. 快速排序Quick Sort核心原理分治思想的经典应用选一个 “基准值pivot”把数组分成 “小于基准” 和 “大于基准” 的两部分再递归排序两部分效率是所有比较排序中最高的。算法逻辑选基准选数组中一个元素作为基准示例选末尾元素也可选中间 / 随机元素优化分区Partition遍历数组把小于基准的元素移到左边大于的移到右边基准放到最终位置递归排序对基准左右的子数组重复步骤 1-2直到子数组长度为 1。示例代码优化版选末尾为基准#include stdio.h // 分区函数返回基准值的最终下标 int partition(int arr[], int low, int high) { int pivot arr[high]; // 选末尾元素为基准 int i (low - 1); // 小于基准区的最后一个元素下标初始为low-1即空 // 遍历[low, high-1]把小于基准的元素移到左边 for (int j low; j high - 1; j) { if (arr[j] pivot) { i; // 扩大小于基准区 // 交换arr[i]和arr[j] int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } // 把基准值放到小于区的下一位即最终位置 int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return (i 1); // 返回基准下标 } // 快速排序递归函数 void quickSort(int arr[], int low, int high) { if (low high) { // 递归终止条件 int pi partition(arr, low, high); // 分区得到基准下标 quickSort(arr, low, pi - 1); // 递归排序左子数组小于基准 quickSort(arr, pi 1, high); // 递归排序右子数组大于基准 } } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {10, 7, 8, 9, 1, 5}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); quickSort(arr, 0, n - 1); printf(排序后); printArray(arr, n); return 0; }复杂度 稳定性时间复杂度最好 / 平均O(n log n)基准选得好分区均匀最坏O(n²)数组已有序基准选末尾分区成 1 和 n-1优化选随机基准 / 三数取中首、中、尾选中间值可避免最坏情况。空间复杂度O(log n)递归栈空间最坏O(n)。稳定性不稳定分区交换时相等元素可能改变相对位置。7. 堆排序Heap Sort核心原理利用二叉堆的特性大顶堆父节点 ≥ 子节点先把数组构建成大顶堆再依次取出堆顶最大值放到数组末尾调整剩余元素为新的大顶堆直到堆为空。算法逻辑构建大顶堆从最后一个非叶子节点开始向上调整每个节点使整个数组满足大顶堆特性堆排序交换堆顶arr [0]和堆尾arr [len-1]把最大值放到数组末尾缩小堆的长度调整剩余元素为大顶堆重复上述步骤直到堆长度为 1。示例代码#include stdio.h // 调整大顶堆确保以i为根的子树是大顶堆 void heapify(int arr[], int n, int i) { int largest i; // 初始化最大值为根节点 int left 2 * i 1; // 左子节点下标 int right 2 * i 2; // 右子节点下标 // 如果左子节点 根节点更新最大值下标 if (left n arr[left] arr[largest]) { largest left; } // 如果右子节点 最大值更新最大值下标 if (right n arr[right] arr[largest]) { largest right; } // 如果最大值不是根节点交换并递归调整受影响的子树 if (largest ! i) { int temp arr[i]; arr[i] arr[largest]; arr[largest] temp; heapify(arr, n, largest); } } // 堆排序升序 void heapSort(int arr[], int n) { // 步骤1构建大顶堆从最后一个非叶子节点开始 for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } // 步骤2逐个取出堆顶元素最大值 for (int i n - 1; i 0; i--) { // 交换堆顶arr[0]和当前堆尾arr[i] int temp arr[0]; arr[0] arr[i]; arr[i] temp; // 调整剩余元素为大顶堆堆长度缩小为i heapify(arr, i, 0); } } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {12, 11, 13, 5, 6, 7}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); heapSort(arr, n); printf(排序后); printArray(arr, n); return 0; }复杂度 稳定性时间复杂度最好 / 最坏 / 平均都是O(n log n)构建堆O(n)每次调整堆O(log n)共 n-1 次调整。空间复杂度O(1)原地排序递归版heapify会有O(log n)栈空间可改迭代版优化。稳定性不稳定交换堆顶和堆尾时相等元素可能改变相对位置。8. 计数排序Counting Sort核心原理非比较排序统计每个元素出现的次数再根据次数把元素放回原数组适合数值范围小的整数如 0~100 的分数。算法逻辑找到数组中的最大值max和最小值min确定计数数组的长度max - min 1创建计数数组count初始化全 0遍历原数组统计每个元素的出现次数遍历计数数组按次数把元素放回原数组升序。示例代码#include stdio.h #include stdlib.h // 用于malloc/free // 计数排序支持负数 void countingSort(int arr[], int n) { if (n 0) return; // 步骤1找数组的最大值和最小值 int max arr[0], min arr[0]; for (int i 1; i n; i) { if (arr[i] max) max arr[i]; if (arr[i] min) min arr[i]; } // 步骤2创建计数数组长度为max - min 1 int range max - min 1; int *count (int *)calloc(range, sizeof(int)); // 初始化为0 // 步骤3统计每个元素的出现次数 for (int i 0; i n; i) { count[arr[i] - min]; // 偏移min处理负数 } // 步骤4把计数数组的结果放回原数组 int index 0; // 原数组的指针 for (int i 0; i range; i) { while (count[i] 0) { arr[index] i min; // 还原偏移 index; count[i]--; } } free(count); // 释放计数数组 } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {4, 2, 2, 8, 3, 3, 1, -1, 0}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); countingSort(arr, n); printf(排序后); printArray(arr, n); return 0; }复杂度 稳定性时间复杂度最好 / 最坏 / 平均都是O(n k)k为数值范围max-min1。空间复杂度O(k)计数数组的空间。稳定性稳定可优化计数数组为前缀和形式从后往前遍历原数组保持相等元素的相对位置。9. 基数排序Radix Sort核心原理非比较排序按数字的 “位” 排序个位→十位→百位…每一位用计数 / 桶排序实现适合整数 / 字符串排序。算法逻辑找到数组中的最大值确定需要排序的位数如最大值是 999需排 3 位从最低位个位开始对每一位执行计数排序或桶排序依次处理更高位直到所有位处理完成数组有序。示例代码按十进制位排序#include stdio.h #include stdlib.h // 获取数字的第digit位digit1个位digit10十位... int getDigit(int num, int digit) { return (num / digit) % 10; } // 按指定位对数组进行计数排序基数排序的子步骤 void countSortByDigit(int arr[], int n, int digit) { int output[n]; // 输出数组 int count[10] {0}; // 0-9的计数数组 // 统计当前位的数字出现次数 for (int i 0; i n; i) { int d getDigit(arr[i], digit); count[d]; } // 转换为前缀和确定每个数字在output中的结束位置 for (int i 1; i 10; i) { count[i] count[i - 1]; } // 从后往前遍历保证稳定性 for (int i n - 1; i 0; i--) { int d getDigit(arr[i], digit); output[count[d] - 1] arr[i]; count[d]--; } // 复制output到原数组 for (int i 0; i n; i) { arr[i] output[i]; } } // 基数排序升序仅支持非负整数可扩展支持负数 void radixSort(int arr[], int n) { if (n 0) return; // 找最大值确定最大位数 int max arr[0]; for (int i 1; i n; i) { if (arr[i] max) max arr[i]; } // 按位排序个位(digit1)→十位(digit10)→百位(digit100)... for (int digit 1; max / digit 0; digit * 10) { countSortByDigit(arr, n, digit); } } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {170, 45, 75, 90, 802, 24, 2, 66}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); radixSort(arr, n); printf(排序后); printArray(arr, n); return 0; }复杂度 稳定性时间复杂度最好 / 最坏 / 平均都是O(d*(n k))d为最大位数k为基数十进制 k10。空间复杂度O(n k)输出数组 计数数组。稳定性稳定按位计数排序时从后往前遍历保持相对位置。10. 桶排序Bucket Sort核心原理非比较排序把数组分到多个 “桶” 中每个桶内用插入排序或其他排序排序最后合并所有桶适合均匀分布的数值如 0~1 的浮点数、1~100 的整数。算法逻辑创建k个桶数量可自定义如按数值范围均分遍历原数组把元素放入对应的桶中对每个非空桶执行插入排序或快速排序按顺序合并所有桶的元素得到有序数组。示例代码处理 0~1 的浮点数#include stdio.h #include stdlib.h #define BUCKET_NUM 10 // 桶的数量 // 桶的节点结构链表存储桶内元素 typedef struct BucketNode { float value; struct BucketNode *next; } BucketNode; // 插入排序桶内排序升序 void insertSort(BucketNode **head) { if (*head NULL || (*head)-next NULL) return; BucketNode *sorted NULL; // 已排序的链表头 BucketNode *curr *head; // 当前待插入节点 while (curr ! NULL) { BucketNode *next curr-next; // 保存下一个节点 // 找插入位置 if (sorted NULL || sorted-value curr-value) { curr-next sorted; sorted curr; } else { BucketNode *temp sorted; while (temp ! NULL temp-next ! NULL temp-next-value curr-value) { temp temp-next; } curr-next temp-next; temp-next curr; } curr next; } *head sorted; } // 桶排序处理0~1的浮点数 void bucketSort(float arr[], int n) { // 步骤1创建空桶数组存储桶的头节点 BucketNode *buckets[BUCKET_NUM] {NULL}; // 步骤2把元素放入对应的桶中 for (int i 0; i n; i) { int bucketIndex (int)(arr[i] * BUCKET_NUM); // 0~9的桶下标 // 创建新节点 BucketNode *newNode (BucketNode *)malloc(sizeof(BucketNode)); newNode-value arr[i]; newNode-next buckets[bucketIndex]; buckets[bucketIndex] newNode; // 头插法 } // 步骤3对每个桶排序并合并到原数组 int index 0; for (int i 0; i BUCKET_NUM; i) { insertSort(buckets[i]); // 桶内插入排序 // 把桶内元素复制回原数组 BucketNode *curr buckets[i]; while (curr ! NULL) { arr[index] curr-value; BucketNode *temp curr; curr curr-next; free(temp); // 释放节点内存 } } } void printArray(float arr[], int n) { for (int i 0; i n; i) { printf(%.2f , arr[i]); } printf(\n); } int main() { float arr[] {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); bucketSort(arr, n); printf(排序后); printArray(arr, n); return 0; }复杂度 稳定性时间复杂度最好 / 平均O(n k)元素均匀分布每个桶元素少排序接近O(1)最坏O(n²)所有元素进同一个桶桶内排序O(n²)。空间复杂度O(n k)桶 元素存储。稳定性稳定桶内用稳定排序如插入排序。11. C 标准库 qsort 函数核心原理C 标准库stdlib.h中的qsort是通用快速排序实现支持任意类型数据排序int、float、结构体等需自定义比较函数。函数原型void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *))参数说明base待排序数组的首地址nitems数组元素个数size每个元素的字节大小如sizeof(int)compar比较函数指针返回值规则负数第一个参数 第二个参数0两个参数相等正数第一个参数 第二个参数。示例代码排序 int / 结构体#include stdio.h #include stdlib.h #include string.h // 示例1排序int数组升序 int compareInt(const void *a, const void *b) { // 转换为int指针取值比较 int num1 *(const int *)a; int num2 *(const int *)b; return num1 - num2; // 升序num2 - num1为降序 } // 示例2排序结构体数组按年龄升序 typedef struct { char name[20]; int age; } Person; int comparePerson(const void *a, const void *b) { Person p1 *(const Person *)a; Person p2 *(const Person *)b; return p1.age - p2.age; } void printIntArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } void printPersonArray(Person p[], int n) { for (int i 0; i n; i) { printf({%s, %d} , p[i].name, p[i].age); } printf(\n); } int main() { // 示例1排序int数组 int intArr[] {5, 2, 9, 1, 5, 6}; int n1 sizeof(intArr) / sizeof(intArr[0]); printf(int数组排序前); printIntArray(intArr, n1); qsort(intArr, n1, sizeof(int), compareInt); printf(int数组排序后); printIntArray(intArr, n1); // 示例2排序结构体数组 Person pArr[] { {Alice, 25}, {Bob, 20}, {Charlie, 30} }; int n2 sizeof(pArr) / sizeof(pArr[0]); printf(\n结构体数组排序前); printPersonArray(pArr, n2); qsort(pArr, n2, sizeof(Person), comparePerson); printf(结构体数组排序后); printPersonArray(pArr, n2); return 0; }复杂度 特点时间复杂度平均O(n log n)最坏O(n²)标准库已优化实际很少出现空间复杂度O(log n)递归栈稳定性不稳定快速排序实现优点通用、简洁无需自己实现排序逻辑适合快速开发。总结1. 排序算法核心对比表表格算法最好时间平均时间最坏时间空间复杂度稳定性适用场景冒泡排序O(n)O(n²)O(n²)O(1)稳定小数据、近乎有序选择排序O(n²)O(n²)O(n²)O(1)不稳定小数据、交换成本高插入排序O(n)O(n²)O(n²)O(1)稳定小数据、近乎有序希尔排序O(n)O(n^1.3)O(n²)O(1)不稳定中小规模数据归并排序O(n logn)O(n logn)O(n logn)O(n)稳定大数据、要求稳定排序快速排序O(n logn)O(n logn)O(n²)O(logn)不稳定通用、大数据效率最高堆排序O(n logn)O(n logn)O(n logn)O(1)不稳定大数据、内存受限计数排序O(nk)O(nk)O(nk)O(k)稳定整数、数值范围小基数排序O(d(nk))O(d(nk))O(d(nk))O(nk)稳定整数、字符串、位数固定桶排序O(nk)O(nk)O(n²)O(nk)稳定均匀分布的数值如浮点数qsortO(n logn)O(n logn)O(n²)O(logn)不稳定通用场景、快速开发2. 核心要点回顾比较排序冒泡 / 选择 / 插入 / 希尔 / 归并 / 快速 / 堆的时间下界是O(n log n)非比较排序计数 / 基数 / 桶可突破该下界但有数据类型限制稳定性需要保持相等元素相对位置时优先选归并 / 计数 / 基数 / 桶排序工程实践优先用 C 标准库qsort通用需手动实现时大数据选快速 / 堆排序小数据选插入排序整数范围小选计数排序。