几种简单的排序算法（C语言）

目录

1 简介

2 冒泡排序

2.1 基本思路

2.2 代码实现

3 选择排序

3.1 基本思路

3.2 代码实现

4 插入排序

4.1 基本思路

4.2 代码实现

5 快速排序

5.1 基本思路

5.2 代码实现

6 归并排序

6.1 基本思路

6.2 代码实现

7 基数排序

7.1 基本思路

7.2 代码实现

8 希尔排序

8.1 基本思路

8.2 代码实现

9 堆排序

9.1 基本思路

9.2 代码实现

10 总结

---

1 简介

在编程实践中，排序算法是基础却极其重要的一类算法，广泛应用于数据组织、查找优化和算法竞赛等多个领域。本文将系统地介绍几种常见的排序算法，包括冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序和基数排序，结合 C 语言代码实现，帮助读者深入理解每种排序的原理、适用场景及其性能差异。无论是初学者打基础，还是备战算法面试，本篇内容都具有较高的参考价值。

2 冒泡排序

冒泡排序（Bubble Sort）是一种简单直观的排序算法，通过不断地交换相邻逆序的元素，使较大的元素像气泡一样逐渐“冒”到序列的末尾。尽管它的性能不如高级排序算法，但因其实现简单，常用于算法入门教学或对小规模数据进行排序。

2.1 基本思路

冒泡排序通过双层循环遍历数组，外层控制排序轮数，内层逐个比较相邻元素，如果前一个元素大于后一个，则交换位置。每一轮结束后，当前未排序部分中最大的元素被移到末尾。重复该过程，直到所有元素有序。

冒泡排序

2.2 代码实现

// 冒泡排序
void bubbleSort(int *a, int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}
}

3 选择排序

选择排序（Selection Sort）是一种原地、稳定的排序算法。它通过在未排序区间中反复选择最小（或最大）元素，并将其放到已排序序列的末尾，逐步构建整个有序序列。该算法结构简单、易于实现，但在大数据量下效率较低。

3.1 基本思路

选择排序每一轮从未排序部分中选出最小的元素，将其与当前轮起始位置的元素交换。外层循环控制已排序与未排序区域的分界，内层循环寻找最小值的位置。随着每一轮结束，最小值被“选出”并放入正确的位置，最终实现整体有序。

选择排序

3.2 代码实现

// 选择排序
void sel(int *a, int n) {for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (a[j] < a[minIndex]) {minIndex = j;}}if (minIndex != i) {int temp = a[i];a[i] = a[minIndex];a[minIndex] = temp;}}
}

4 插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，适用于小规模数据排序或基本有序的数据集合。它通过构建有序序列，将待排序元素逐个插入到已排序部分的适当位置，从而实现整体有序。插入排序是一种稳定排序，空间复杂度为 O(1)。

4.1 基本思路

从第二个元素开始，逐个将当前元素与它前面的元素进行比较，如果当前元素更小，就将前面的元素后移，直到找到合适位置后插入该元素。这个过程相当于模拟打扑克牌时整理牌的方式，不断向有序部分“插入”新的元素，直到所有元素排序完成。

插入排序

4.2 代码实现

// 插入排序
void insert(int *a, int n) {for (int i = 1; i < n; i++) {int key = a[i];int j = i - 1;while (j >= 0 && a[j] > key) {a[j + 1] = a[j];j--;}a[j + 1] = key;}
}

5 快速排序

快速排序是一种采用分治法思想的高效排序算法，它通过选取一个基准元素，将待排序序列划分为左右两个子序列，其中左子序列的所有元素都不大于基准，右子序列的所有元素都不小于基准，然后递归地对这两个子序列进行快速排序。由于其在多数情况下表现优异，因此是实际应用中最常用的排序算法之一。

5.1 基本思路

快速排序的核心思路是选择一个基准元素，通过一趟扫描将数组划分为两个部分：左边是小于基准的元素，右边是大于基准的元素，然后对这两个部分分别递归执行同样的操作，最终实现整个数组的有序排列。排序过程中通常采用交换的方式在原数组上进行划分，从而实现原地排序，减少额外空间开销。

快速排序

5.2 代码实现

// 交换函数
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 分区函数
int partition(int *a, int low, int high) {int pivot = a[high]; // 选择最后一个元素作为基准int i = low - 1;      // i 用于追踪小于基准的区间for (int j = low; j < high; j++) {if (a[j] < pivot) {i++;swap(&a[i], &a[j]);}}swap(&a[i + 1], &a[high]);return i + 1; // 返回基准的最终位置
}// 快速排序主函数
void quickSort(int *a, int low, int high) {if (low < high) {int pi = partition(a, low, high); // pi 为基准的最终位置quickSort(a, low, pi - 1);  // 递归排序左子数组quickSort(a, pi + 1, high); // 递归排序右子数组}
}

6 归并排序

归并排序是一种基于分治思想的稳定排序算法，它将一个数组不断二分为更小的子数组，直到每个子数组只包含一个元素，然后再将这些有序子数组两两合并为一个有序数组，最终得到排序结果。归并排序在最坏、平均和最好情况下的时间复杂度都为 O(n log n)，适用于需要稳定排序且数据量较大的场景。

6.1 基本思路

归并排序首先将整个数组划分成两半，递归地对每一半进行归并排序，直到子数组长度为 1。随后，通过一个“合并过程”将两个有序子数组合并成一个新的有序数组。这个合并过程是归并排序的关键步骤，它通过比较两个子数组的元素大小并顺序地放入新数组中，最终形成排序好的数组。

归并排序

6.2 代码实现

// 合并两个有序数组
void merge(int *a, 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] = a[left + i];for (int j = 0; j < n2; j++) R[j] = a[mid + 1 + j];int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) a[k++] = L[i++];else a[k++] = R[j++];}while (i < n1) a[k++] = L[i++];while (j < n2) a[k++] = R[j++];free(L);free(R);
}// 归并排序
void mergeSort(int *a, int left, int right) {if (left < right) {int mid = (left + right) / 2;mergeSort(a, left, mid);mergeSort(a, mid + 1, right);merge(a, left, mid, right);}
}

7 基数排序

基数排序（Radix Sort）是一种非比较型排序算法，适用于对整数或字符串进行排序。它通过按位分组和排序来实现整体排序，通常从最低有效位（LSD）到最高有效位（MSD）逐位排序。基数排序的时间复杂度可达到 O(k·n)，其中 n 是元素个数，k 是最大元素的位数（或长度）。它适合大规模、位数不多的正整数排序。

7.1 基本思路

基数排序将所有元素按“位”进行排序，从最低位到最高位。每一轮排序都使用一个稳定的排序算法（如计数排序）对当前位进行排序。通过多轮“按位排序”后，整个数组就变得有序。因为是逐位稳定排序，所以可以避免破坏已排序好的低位顺序，从而达到全局有序。

基数排序

7.2 代码实现

// 基数排序
void countSort(int *a, int n, int exp) {int output[n];int count[10] = {0};// 统计每个桶中元素个数for (int i = 0; i < n; i++) {int digit = (a[i] / exp) % 10;count[digit]++;}// 累加，确定各桶位置for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 从后向前遍历，稳定排序for (int i = n - 1; i >= 0; i--) {int digit = (a[i] / exp) % 10;output[count[digit] - 1] = a[i];count[digit]--;}// 拷贝结果回原数组for (int i = 0; i < n; i++) {a[i] = output[i];}
}int getMax(int *a, int n) {int max = a[0];for (int i = 1; i < n; i++) {if (a[i] > max)max = a[i];}return max;
}void radixSort(int *a, int n) {int max = getMax(a, n);for (int exp = 1; max / exp > 0; exp *= 10) {countSort(a, n, exp);}
}

8 希尔排序

希尔排序是插入排序的一种优化形式，也被称为“缩小增量排序”。它通过将整个数组按照一定的间隔（gap）分组，对每组分别进行插入排序，从而减少整体移动次数。随着排序的进行，gap 逐渐缩小，最终当 gap = 1 时，整个数组基本接近有序，再进行一次插入排序即可完成排序。希尔排序的效率高于普通插入排序，尤其在处理大量数据时性能更优。

8.1 基本思路

希尔排序通过定义一个初始间隔（如 n/2），将数组分为若干个子序列，对每个子序列进行插入排序。然后不断缩小间隔（通常减半），重复上述过程，直到间隔为 1 时，执行最后一次插入排序。由于前期大间隔排序已经基本理顺了元素位置，最后的插入排序效率很高。这种逐步逼近有序的策略显著提高了整体排序性能。

8.2 代码实现

// 希尔排序
void shell(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;}}
}

9 堆排序

堆排序（Heap Sort）是一种基于堆这种数据结构的比较型排序算法。它将待排序数组构建成一个大根堆（或小根堆），使得堆顶元素为最大值（或最小值），然后将堆顶元素与堆的最后一个元素交换，缩小堆的范围，并重新调整堆结构。通过反复取出堆顶元素，最终形成有序序列。堆排序的时间复杂度为 O(n log n)，不需要额外的空间，适合对大量数据进行原地排序。

9.1 基本思路

堆排序的核心在于两步操作：建堆和调整堆。首先，通过“上滤”或“下滤”方法将整个数组构建成一个最大堆（即每个父节点都大于等于其子节点）；接着重复执行：将堆顶元素与末尾元素交换，然后对前 n-1 个元素重新调整为最大堆。每轮都能将当前未排序部分的最大值“沉”到末尾，最终实现整体排序。

9.2 代码实现

// 交换两个元素
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 调整为最大堆
void heapify(int *a, int n, int i) {int largest = i;          // 假设父节点最大int left = 2 * i + 1;     // 左子节点下标int right = 2 * i + 2;    // 右子节点下标// 如果左子节点比父节点大if (left < n && a[left] > a[largest])largest = left;// 如果右子节点比当前最大值还大if (right < n && a[right] > a[largest])largest = right;// 如果最大值不是当前节点，交换并继续调整if (largest != i) {swap(&a[i], &a[largest]);heapify(a, n, largest);}
}// 堆排序
void heapSort(int *a, int n) {// 建堆（从最后一个非叶子节点开始）for (int i = n / 2 - 1; i >= 0; i--)heapify(a, n, i);// 逐个将最大值移到末尾，缩小堆for (int i = n - 1; i > 0; i--) {swap(&a[0], &a[i]);    // 把堆顶元素放到末尾heapify(a, i, 0);      // 重新对剩余元素调整为最大堆}
}

10 总结

本文系统地介绍了几种经典排序算法，包括冒泡、选择、插入、快速、归并、希尔、堆、基数排序等，结合 C 语言实现，从原理到代码细节进行了深入解析。通过对每种算法的基本思路、适用场景和时间复杂度的比较，读者可以全面了解各类排序算法的优势与局限，为日后编程实践、算法竞赛或技术面试打下坚实基础。这不仅有助于掌握排序的核心思想，也提升了解决实际问题的能力。

本文的可视化均来自于以下网址：VisuAlgo

感兴趣的可以看一下。