【算法】八大排序算法

这篇文章是对数据结构中 八大经典排序算法 的详解，包括其原理、实现过程、时间复杂度、空间复杂度及其适用场景。最后两种排序不常见，但仍收录了进来保持文章结构的完整性。

排序(Sort)是将无序的记录序列（或称文件）调整成有序的序列。升序 或 降序 —> 一般都是对数据进行升序排列（从小到大排序）。

对文件（File）进行排序有重要的意义。如果文件按key有序，可对其折半查找，使查找效率提高；在数据库（Data Base）和知识库（Knowledge Base）等系统中，一般要建立若干索引文件，就牵涉到排序问题；在一些计算机的应用系统中，要按不同的数据段作出若干统计，也涉及到排序。排序效率的高低，直接影响到计算机的工作效率。

稳定排序和非稳定排序

设文件 f=（R1……Ri……Rj……Rn）中记录 Ri、Rj（i≠j，i、j=1……n）的 key 相等，即 Ki=Kj 。若在排序前 Ri 领先于Rj，排序后 Ri 仍领先于 Rj，则称这种排序是稳定的，其含义是它没有破坏原本已有序的次序。反之，若排序后Ri与Rj的次序有可能颠倒，则这种排序是非稳定的，即它有可能破坏了原本已有序记录的次序。

说人话就是：假设有6个数据：5 2 6 2 8 1 —> 具有重复数据；经过排序后得到： 1 2 2 5 6 8，稳定排序和不稳定排序之间讲究的就是在相同的数据中，相同数据是否转换了位置。

1> 1 2 2 5 6 8
------①②--------> 两个 2（重复数据） 没有发生位置改变，称为稳定排序。
2> 1 2 2 5 6 8
------②①--------> 两个 2（重复数据） 发生了位置改变，称为不稳定排序。

排序的稳定性没办法解决，看具体的算法性能决定排序的稳定性。这二者之间只有性能差异，并不会影响到数据和操作的变化。

内排序和外排序

内排序：发生在内存中的排序方式（我们现在用的大部分排序方式都是内排序）；
外排序：发生在其他硬件或（存储器）之间的排序 —> 通信排序。

若待排文件 f 在计算机的内存储器中，且排序过程也在内存中进行，称这种排序为内排序。内排序速度快，但由于内存容量一般很小，文件的长度（记录个数）n受到一定限制。若排序中的文件存入外存储器，排序过程借助于内外存数据交换（或归并）来完成，则称这种排序为外排序。我们重点讨论内排序的一些方法、算法以及时间复杂度的分析。

算法数据可视化参考该网站：https://visualgo.net/zh。

截止目前，各种内排序方法可归纳为以下五类：

（1）插入排序
（2）交换排序
（3）选择排序
（4）归并排序
（5）基数排序

也可以按照比较类排序和非比较类排序来进行分类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
  

算法复杂度分析

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的交换排序算法，按顺序比较相邻的两个元素，将较大的元素逐渐“冒泡”到数组的末尾。相信冒泡排序是大家最熟知、面试中常考题、也是最经典的一种排序方式。

算法原理

1. 对数组从头到尾遍历。
2. 每次比较相邻的两个元素，如果前者大于后者，则交换它们。
3. 每轮遍历后，最大的元素会“冒泡”到数组的末尾。
4. 重复此过程，直到数组完全有序。

时间复杂度

• 最好情况：O(n)（数组本身有序，使用标志优化）
• 最坏情况：O(n²)（数组逆序）
• 平均情况：O(n²)

空间复杂度

• O(1)（原地排序）

冒泡排序演示

代码实现（C语言）

void bubbleSort(int arr[], int n) {int i, j, temp;for (i = 0; i < n - 1; i++) {int swapped = 0;  // 标志位，检测是否发生交换for (j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = 1;}}if (!swapped) break;  // 如果没有发生交换，提前退出}
}

2. 选择排序（Selection Sort）

选择排序是一种简单的排序算法，通过选择最小（或最大）的元素并将其放到正确位置。

算法原理

1. 在未排序部分中找到最小元素。
2. 将该最小元素与未排序部分的第一个元素交换。
3. 重复上述步骤，直到所有元素有序。

时间复杂度

• 最好情况：O(n²)
• 最坏情况：O(n²)
• 平均情况：O(n²)

空间复杂度

• O(1)（原地排序）

选择排序演示

代码实现（C语言）

void selectionSort(int arr[], int n) {int i, j, minIndex, temp;for (i = 0; i < n - 1; i++) {minIndex = i;for (j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}if (minIndex != i) {temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}
}

选择排序是表现最稳定的排序算法之一，因为无论什么数据进去都是 O(n2) 的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法。

3. 插入排序（Insertion Sort）

插入排序通过逐步构建有序序列，将每个元素插入到有序序列的正确位置。

算法原理

1. 从第二个元素开始，视其为待插入元素。
2. 从已排序部分的末尾向前遍历，找到其插入位置。
3. 插入元素后，已排序部分长度加 1。
4. 重复上述步骤，直到所有元素有序。

时间复杂度

• 最好情况：O(n)（数组本身有序）
• 最坏情况：O(n²)（数组逆序）
• 平均情况：O(n²)

空间复杂度

• O(1)（原地排序）

插入排序演示

代码实现（C语言）

void insertionSort(int arr[], int n) {int i, j, key;for (i = 1; i < n; i++) {key = arr[i];j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

4. 希尔排序（Shell Sort）

希尔排序是插入排序的改进版，通过分组和缩小增量进行排序。

算法原理

1. 将数组分成若干组，按间隔 gap 分组。
2. 对每组元素进行插入排序。
3. 缩小间隔 gap，重复分组和排序。
4. 最后，当 gap = 1 时，完成整个排序。

时间复杂度

• 最好情况：O(n log n)
• 最坏情况：O(n²)
• 平均情况：O(n log n)

空间复杂度

• O(1)

希尔排序演示

代码实现（C语言）

void shellSort(int arr[], int n) {int gap, i, j, temp;for (gap = n / 2; gap > 0; gap /= 2) {for (i = gap; i < n; i++) {temp = arr[i];for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

5. 快速排序（Quick Sort）

快速排序是一种基于分治的高效排序算法。

算法原理

1. 选择一个基准值（通常是第一个元素）。
2. 将数组分为两部分：小于基准值的放左边，大于基准值的放右边。
3. 对两部分递归排序。
4. 递归结束后，数组有序。

时间复杂度

• 最好情况：O(n log n)
• 最坏情况：O(n²)（划分极不平衡）
• 平均情况：O(n log n)

空间复杂度

• O(log n)（递归栈空间）

快速排序演示

代码实现（C语言）

void quick_sort(int *a,int left,int right)
{if(left>=right){return;}int i=left;int j=right;int key=a[i];while(i<j){while(key<a[j] && i<j){j--;}a[i]=a[j];while(key>a[i] && i<j){i++;}a[j]=a[i];}a[i]=key;display(a);quick_sort(a,left,i-1);quick_sort(a,i+1,right);
}

6. 归并排序（Merge Sort）

归并排序是基于分治的稳定排序算法。

算法原理

1. 将数组递归分成两部分，直到每部分只有一个元素。
2. 合并两个有序部分，形成一个有序数组。
3. 重复上述步骤，最终完成排序。

时间复杂度

• 最好/最坏/平均情况：O(n log n)

空间复杂度

• O(n)（合并时需要额外数组）

归并排序演示

代码实现（C语言）

void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int L[n1], R[n2];for (int i = 0; i < n1; i++) L[i] = arr[left + i];for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) arr[k++] = L[i++];else arr[k++] = R[j++];}while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}void mergeSort(int arr[], int left, int right) {if (left >= right) return;int mid = left + (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);
}

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

7. 堆排序（Heap Sort）

堆排序基于堆数据结构，是一种选择排序。

算法原理

1. 构建最大堆（堆顶为最大元素）。
2. 将堆顶元素与堆尾元素交换，缩小堆范围。
3. 调整堆，重复上述步骤，完成排序。

时间复杂度

• 最好/最坏/平均情况：O(n log n)

空间复杂度

• O(1)

堆排序演示

代码实现（C语言）

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) {for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);for (int i = n - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}
}

8. 基数排序（Radix Sort）

基数排序是一种非比较排序算法，适合对整数或字符串进行排序。其核心思想是按位排序，从最低位到最高位，逐位进行排序（通常使用计数排序作为子过程）。

算法原理

1. 按位排序：
   • 从个位开始，对每一位进行排序，直到最高位。
   • 每一位的排序需要保持稳定性（如使用计数排序实现）。
2. 关键步骤：
   • 找到数组中的最大值，确定排序的位数 d。
   • 对每一位（从最低位到最高位）依次排序。
   • 使用计数排序对当前位排序，确保排序稳定。

时间复杂度

• 对每一位执行一次计数排序，时间复杂度为 O(n + k)。
• 总共需要执行 d 次，时间复杂度为 O(d × (n + k))。
  • d 是最大元素的位数。
  • k 是基数（通常为 10）。

空间复杂度

• 需要额外的计数数组和输出数组，空间复杂度为 O(n + k)。

基数排序演示

代码实现（C语言）

#include <stdio.h>
#include <stdlib.h>// 获取数组中的最大值
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 countingSort(int arr[], int n, int exp) {int output[n];   // 输出数组int count[10] = {0};  // 计数数组，用于存储每一位数字的出现次数// 统计当前位数字的出现次数for (int i = 0; i < n; i++) {int digit = (arr[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 = (arr[i] / exp) % 10;  // 提取当前位的数字output[count[digit] - 1] = arr[i];count[digit]--;}// 将排序后的结果复制回原数组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) {countingSort(arr, n, exp);}
}// 打印数组
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("Original array:\n");printArray(arr, n);radixSort(arr, n);printf("Sorted array:\n");printArray(arr, n);return 0;
}
// (1) 获取最大值函数
//     getMax 找到最大值，用于确定排序的位数（d）。
//     时间复杂度：O(n)。
// (2) 计数排序函数
//     countingSort 按当前位（exp）对数组排序：
//       提取当前位的数字：(arr[i] / exp) % 10。
//       使用计数数组统计出现次数，完成稳定排序。
// (3) 基数排序主函数
//     对每一位（个位、十位、百位……）依次调用 countingSort。
//     外层循环次数为最大元素的位数 d。
// (4) 输出数组
//     使用 printArray 打印数组，方便调试和验证。

运行结果：
输入数组：

170, 45, 75, 90, 802, 24, 2, 66

排序过程（按位）：

1. 按个位排序：

170, 90, 802, 2, 24, 45, 66, 75

2. 按十位排序：

802, 2, 24, 45, 66, 75, 170, 90

3. 按百位排序：

2, 24, 45, 66, 75, 90, 170, 802

最终输出结果：

2, 24, 45, 66, 75, 90, 170, 802

基数排序基于分别排序，分别收集，所以是稳定的。基数排序是一种快速、稳定的排序算法，适合对整数或字符串进行排序。通过按位排序，避免了直接比较元素大小，在特定场景下（如大量非负整数排序），基数排序的效率优于比较排序算法（如快速排序）。

9. 计数排序（Counting Sort）

计数排序是一种非比较排序算法，适用于整数或离散范围较小的数据。通过统计每个元素出现的次数，并利用这些计数信息将数据排序。

算法原理

1. 找出数组中的最大值和最小值，确定计数数组的大小。
2. 创建一个计数数组 count，统计每个数字出现的次数。
3. 对计数数组进行累加操作，计算每个元素的位置。
4. 根据计数数组，将原数组中的元素放到正确的位置上，并生成输出数组。

时间复杂度

• O(n + k)（n 为数组长度，k 为数据范围）。

空间复杂度

• O(k)。

计数排序演示

代码实现（C语言）

#include <stdio.h>
#include <stdlib.h>// 计数排序
void countingSort(int arr[], int n) {// 找到数组中的最大值和最小值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];}int range = max - min + 1;  // 数据范围int* count = (int*)calloc(range, sizeof(int));  // 创建计数数组并初始化为 0int* output = (int*)malloc(n * sizeof(int));    // 创建输出数组// 统计每个元素的出现次数for (int i = 0; i < n; i++) {count[arr[i] - min]++;}// 计算计数数组的累加值for (int i = 1; i < range; i++) {count[i] += count[i - 1];}// 根据计数数组将元素放入正确位置，生成输出数组for (int i = n - 1; i >= 0; i--) {output[count[arr[i] - min] - 1] = arr[i];count[arr[i] - min]--;}// 将排序后的数组拷贝回原数组for (int i = 0; i < n; i++) {arr[i] = output[i];}// 释放动态分配的内存free(count);free(output);
}int main() {int arr[] = {4, 2, 2, 8, 3, 3, 1};int n = sizeof(arr) / sizeof(arr[0]);printf("Original array: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");countingSort(arr, n);printf("Sorted array: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

运行结果

# 输入数组：
{4, 2, 2, 8, 3, 3, 1}
# 输出数组：
{1, 2, 2, 3, 3, 4, 8}

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

计数排序适用于整数或范围较小的数据，具有高效的时间复杂度，但空间使用较大。

10. 桶排序（Bucket Sort）

桶排序是一种基于分布的排序算法，将输入数据分配到若干个桶（区间）中，然后对每个桶内的数据进行单独排序，最后将桶内的元素合并得到结果。

算法原理

1. 确定桶的数量和每个桶的范围。
2. 创建若干个桶，将元素分配到对应的桶中。
3. 对每个桶内的元素进行排序（可以使用其他排序算法，如插入排序、快速排序等）。
4. 将所有桶内的元素按序合并。

时间复杂度

• O(n + k)（k 为桶的数量）。

空间复杂度

• O(n + k)。

桶排序演示


代码实现（C语言）

#include <stdio.h>
#include <stdlib.h>// 桶排序中的插入排序
void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}// 桶排序
void bucketSort(float arr[], int n) {// 创建 n 个桶，每个桶是一个动态数组int bucketCount = n;float** buckets = (float**)malloc(bucketCount * sizeof(float*));int* bucketSizes = (int*)calloc(bucketCount, sizeof(int));  // 存储每个桶的大小for (int i = 0; i < bucketCount; i++) {buckets[i] = (float*)malloc(n * sizeof(float));  // 每个桶最大容量为 n}// 将元素分配到对应的桶中for (int i = 0; i < n; i++) {int bucketIndex = (int)(arr[i] * bucketCount);  // 根据值计算桶索引buckets[bucketIndex][bucketSizes[bucketIndex]++] = arr[i];}// 对每个桶内的数据进行排序for (int i = 0; i < bucketCount; i++) {insertionSort(buckets[i], bucketSizes[i]);}// 合并所有桶中的数据int index = 0;for (int i = 0; i < bucketCount; i++) {for (int j = 0; j < bucketSizes[i]; j++) {arr[index++] = buckets[i][j];}free(buckets[i]);  // 释放桶内存}free(buckets);free(bucketSizes);
}int main() {float arr[] = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51};int n = sizeof(arr) / sizeof(arr[0]);printf("Original array: ");for (int i = 0; i < n; i++) {printf("%.2f ", arr[i]);}printf("\n");bucketSort(arr, n);printf("Sorted array: ");for (int i = 0; i < n; i++) {printf("%.2f ", arr[i]);}printf("\n");return 0;
}

运行结果：

# 输入数组：
{0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51}
# 输出数组：
{0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52}

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

桶排序适用于浮点数或连续数据，通过分桶和排序实现高效排序，尤其在数据分布均匀时表现优异。

想要了解更多算法动画演示和代码逻辑在这个网站中可以查阅： https://visualgo.net/en

以上。仅供学习与分享交流，请勿用于商业用途！转载需提前说明。

我是一个十分热爱技术的程序员，希望这篇文章能够对您有帮助，也希望认识更多热爱程序开发的小伙伴。
感谢！