上期回顾: 【数据结构|C语言版】栈和队列
个人主页：C_GUIQU
归属专栏：【数据结构（C语言版）学习】
前言
各位小伙伴大家好！上次小编给大家讲解了数据结构中的树、二叉树和堆，接下来我们讲解一下排序算法中的四大排序！
1. 插入排序
1.1 直接插入排序
直接插入排序（Straight Insertion Sort）是一种简单的排序算法，其主要思想是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。该算法通常适用于少量数据的排序，时间复杂度为 (O(n^2))。
以下是直接插入排序的详细步骤：
初始化：
- 将数组的第一个元素视为一个有序序列，剩余的元素视为未排序序列。
从第一个未排序元素开始：
- 选择下一个未排序的元素。
- 将这个元素插入到前面已经排序的序列中的适当位置。
寻找插入位置：
- 从已排序的序列中，从后向前扫描，找到第一个比当前元素小的元素的位置。
- 如果遇到比当前元素大的元素，将该元素向后移动一位。
插入：
- 将当前元素插入到找到的位置。
重复步骤2-4：
- 对剩余的未排序元素重复上述过程，直到所有元素都被排序。
以下是直接插入排序的伪代码：
InsertionSort(A):
for i = 1 to length(A) - 1:
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
通过一个具体的例子来说明：
假设有一个数组 A = [5, 2, 4, 6, 1, 3]
- 初始状态： [5 | 2, 4, 6, 1, 3]
- 插入 2： [2, 5 | 4, 6, 1, 3]
- 插入 4： [2, 4, 5 | 6, 1, 3]
- 插入 6： [2, 4, 5, 6 | 1, 3]
- 插入 1： [1, 2, 4, 5, 6 | 3]
- 插入 3： [1, 2, 3, 4, 5, 6 | ]
最终排序后的数组为 [1, 2, 3, 4, 5, 6]
直接插入排序的特点：
- 稳定性：直接插入排序是稳定的排序算法，两个相等的元素在排序后相对位置不变。
- 时间复杂度：最坏情况下（倒序）时间复杂度为 (O(n^2))，最优情况下（已排序）时间复杂度为 (O(n))。
- 空间复杂度：直接插入排序是原地排序算法，空间复杂度为 (O(1))。
直接插入排序适用于数据量较小或者部分有序的序列，当数据量较大时，性能较差。
1.2 希尔排序
希尔排序（Shell Sort）是插入排序的一种改进版本，它通过将整个待排序的记录序列分割成若干子序列分别进行直接插入排序，以便在整个序列基本有序时，再对全体记录进行一次直接插入排序。这种方法克服了直接插入排序的局限性，使得希尔排序的时间复杂度显著降低。
以下是希尔排序的详细步骤：
选择初始增量：
- 选择一个增量序列，一般选择增量 ( \text{gap} ) 初始值为数组长度的一半，然后逐步缩小增量，直至增量为1。
分组：
- 按照当前增量 ( \text{gap} ) 将数组分成若干子序列。每个子序列分别进行直接插入排序。
排序子序列：
- 对每个子序列使用直接插入排序进行排序。
减小增量：
- 缩小增量 ( \text{gap} )，重复步骤2-4，直到增量为1时，再进行最后一次直接插入排序。
以下是希尔排序的伪代码：
ShellSort(A):
n = length(A)
gap = n // 2
while gap > 0:
for i = gap to n - 1:
temp = A[i]
j = i
while j >= gap and A[j - gap] > temp:
A[j] = A[j - gap]
j = j - gap
A[j] = temp
gap = gap // 2
通过一个具体的例子来说明希尔排序的过程：
假设有一个数组 A = [9, 8, 3, 7, 5, 6, 4, 1]
初始状态：
- 数组长度 n = 8
- 初始增量 gap = 4
第一次分组和排序：
- 分组： [9, 5] [8, 6] [3, 4] [7, 1]
- 排序后： [5, 6, 4, 1, 9, 8, 3, 7]
缩小增量 gap = 2：
- 分组： [5, 4, 9, 3] [6, 1, 8, 7]
- 排序后： [4, 1, 3, 5, 7, 6, 8, 9]
缩小增量 gap = 1：
- 全体直接插入排序：
- 最终排序后： [1, 3, 4, 5, 6, 7, 8, 9]
希尔排序的特点：
- 不稳定性：希尔排序是一个不稳定的排序算法，两个相等的元素在排序后相对位置可能会改变。
- 时间复杂度：希尔排序的时间复杂度取决于增量序列的选择，最坏情况下时间复杂度为 (O(n^2))，但一般情况远优于直接插入排序，通常可以达到 (O(n \log^2 n))。
- 空间复杂度：希尔排序是原地排序算法，空间复杂度为 (O(1))。
希尔排序通过分组和多次插入排序，显著减少了数据移动的次数，适用于中等规模的数据排序。
2. 选择排序
2.1 选择排序
选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
以下是选择排序的详细步骤：
初始状态：
- 将整个数组视为未排序。
选择最小元素：
- 在未排序的序列中找到最小（或最大）的元素，记录其位置。
交换元素：
- 将找到的最小（或最大）元素与未排序序列的第一个元素交换。
缩小范围：
- 将范围缩小，从下一个位置开始，重复步骤2-3，直到排序结束。
以下是选择排序的伪代码：
SelectionSort(A):
n = length(A)
for i = 0 to n - 2:
min_index = i
for j = i + 1 to n - 1:
if A[j] < A[min_index]:
min_index = j
if min_index != i:
swap A[i] and A[min_index]
通过一个具体的例子来说明选择排序的过程：
假设有一个数组 A = [64, 25, 12, 22, 11]
初始状态：
- 未排序序列：[64, 25, 12, 22, 11]
- 已排序序列：[]
第一次选择和交换：
- 找到最小元素 11，交换到第一个位置
- 结果：[11, 25, 12, 22, 64]
- 未排序序列：[25, 12, 22, 64]
- 已排序序列：[11]
第二次选择和交换：
- 找到最小元素 12，交换到第二个位置
- 结果：[11, 12, 25, 22, 64]
- 未排序序列：[25, 22, 64]
- 已排序序列：[11, 12]
第三次选择和交换：
- 找到最小元素 22，交换到第三个位置
- 结果：[11, 12, 22, 25, 64]
- 未排序序列：[25, 64]
- 已排序序列：[11, 12, 22]
第四次选择和交换：
- 找到最小元素 25，交换到第四个位置
- 结果：[11, 12, 22, 25, 64]
- 未排序序列：[64]
- 已排序序列：[11, 12, 22, 25]
最终排序后：
- 结果：[11, 12, 22, 25, 64]
选择排序的特点：
- 不稳定性：选择排序是一个不稳定的排序算法，因为相等元素的相对顺序可能会改变。
- 时间复杂度：选择排序的时间复杂度为 (O(n^2))，无论数组是否有序。
- 空间复杂度：选择排序是原地排序算法，空间复杂度为 (O(1))。
选择排序适用于数据量较小的序列排序，当数据量较大时，性能较差。
2.2 堆排序
在C语言中实现堆排序涉及到构建最大堆以及从最大堆中提取最大元素并重新调整堆的过程。下面是堆排序的完整实现代码：
堆排序的实现步骤
定义堆调整函数
heapify：- 用于维护堆的性质（最大堆）。
构建最大堆：
- 从最后一个非叶子节点开始，向前调整每个节点。
排序过程：
- 交换堆顶元素和最后一个元素，然后调整剩余元素为最大堆。
C语言代码
#include <stdio.h>
// 交换两个元素的宏
#define SWAP(x, y) { int temp = x; x = y; y = temp; }
// 堆调整函数，维护最大堆性质
void heapify(int arr[], int n, int i) {
int largest = i; // 初始化largest为根节点
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;
// 如果largest不是根节点
if (largest != i) {
SWAP(arr[i], arr[largest]); // 交换
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--) {
SWAP(arr[0], arr[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("Unsorted array: \n");
printArray(arr, n);
heapSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
代码说明
宏定义
SWAP：- 用于交换两个整数的值。
heapify函数：- 用于维护最大堆的性质。参数
arr是待调整的数组，n是数组的长度，i是当前节点的索引。 - 它通过比较节点与其子节点的值，将最大值移到根位置，然后递归地调整受影响的子树。
- 用于维护最大堆的性质。参数
heapSort函数：- 先构建最大堆，从最后一个非叶子节点开始向前调整。
- 然后从堆中依次取出最大值（堆顶），将其放到数组末尾，并调整剩余的元素为新的最大堆。
printArray函数：- 用于打印数组内容。
main函数：- 定义待排序的数组并调用
heapSort函数进行排序，然后打印排序后的数组。
- 定义待排序的数组并调用
特点
- 时间复杂度：堆排序的时间复杂度为 (O(n \log n))。
- 空间复杂度：堆排序是原地排序算法，空间复杂度为 (O(1))。
- 不稳定性：堆排序是不稳定的排序算法。
堆排序适用于需要保证较好最坏情况性能的排序场景。
3. 交换排序
3.1 冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素并交换它们的位置，如果它们的顺序错误。遍历列表的工作是重复进行的，直到不需要再交换为止，也就是说列表已经排序完成。
以下是冒泡排序的详细步骤和在C语言中的实现：
冒泡排序的步骤
遍历数组：
- 从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。
重复步骤1：
- 对于每一对相邻元素的比较和交换，重复该过程n-1次（n是数组的长度），每次都会将最大的元素"冒泡"到数组的末尾。
优化：
- 可以在每一轮遍历中加入一个标志变量，如果在某一轮遍历中没有发生交换，说明数组已经排序完成，可以提前退出。
C语言实现代码
#include <stdio.h>
// 冒泡排序函数
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]) {
// 交换相邻元素
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = 1;
}
}
// 如果在某一轮没有发生交换，说明数组已排序完成
if (swapped == 0)
break;
}
}
// 打印数组函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; 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("Unsorted array: \n");
printArray(arr, n);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
代码说明
bubbleSort函数：- 传入一个数组
arr和数组的长度n。 - 外层循环控制遍历次数，内层循环进行相邻元素的比较和交换。
- 使用标志变量
swapped检测在每一轮中是否发生交换，如果没有发生交换，说明数组已经有序，可以提前退出。
- 传入一个数组
printArray函数：- 用于打印数组内容。
main函数：- 定义一个待排序的数组，调用
bubbleSort函数进行排序，然后打印排序后的数组。
- 定义一个待排序的数组，调用
特点
- 稳定性：冒泡排序是稳定的排序算法，因为相等元素的相对顺序不会改变。
- 时间复杂度：最坏情况下和平均情况下时间复杂度为 (O(n^2))，最优情况下（已经有序）时间复杂度为 (O(n))。
- 空间复杂度：冒泡排序是原地排序算法，空间复杂度为 (O(1))。
冒泡排序适用于数据量较小或基本有序的数组，对于较大的数据集，效率较低。
3.2 快速排序
快速排序（Quick Sort）是一种高效的排序算法，基于分治法（Divide and Conquer）。它的主要思想是选择一个基准元素（pivot），通过一趟排序将待排序列分成两部分，其中一部分的所有元素都比基准元素小，另一部分的所有元素都比基准元素大，然后递归地对这两部分进行快速排序。以下是快速排序的详细步骤和在C语言中的实现：
快速排序的步骤
选择基准元素：
- 可以选择数组的第一个元素、最后一个元素、中间元素或者随机选择一个元素作为基准。
分区操作：
- 通过一趟排序将数组分成两部分，使得基准元素左边的元素都小于基准元素，右边的元素都大于基准元素。
递归排序：
- 对基准元素左边和右边的子数组递归地进行快速排序。
C语言实现代码
#include <stdio.h>
// 交换两个元素的宏
#define SWAP(x, y) { int temp = x; x = y; y = temp; }
// 分区函数
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // i是较小元素的索引
for (int j = low; j < high; j++) {
// 如果当前元素小于或等于基准
if (arr[j] <= pivot) {
i++; // 增加较小元素的索引
SWAP(arr[i], arr[j]); // 交换
}
}
SWAP(arr[i + 1], arr[high]); // 交换基准和i+1位置的元素
return (i + 1); // 返回基准的索引
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi是分区索引，arr[pi]是基准元素
int pi = partition(arr, low, high);
// 递归地排序基准元素的左右两部分
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 打印数组函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; 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("Unsorted array: \n");
printArray(arr, n);
quickSort(arr, 0, n-1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
代码说明
宏定义
SWAP：- 用于交换两个整数的值。
partition函数：- 选择数组的最后一个元素作为基准元素
pivot。 - 初始化较小元素的索引
i为low - 1。 - 遍历数组，将小于或等于
pivot的元素移到数组的左侧，大于pivot的元素移到右侧。 - 最后交换基准元素和
i+1位置的元素，并返回i+1作为分区索引。
- 选择数组的最后一个元素作为基准元素
quickSort函数：- 递归地对数组的左半部分和右半部分进行快速排序。
printArray函数：- 用于打印数组内容。
main函数：- 定义一个待排序的数组，调用
quickSort函数进行排序，然后打印排序后的数组。
- 定义一个待排序的数组，调用
特点
- 不稳定性：快速排序是不稳定的排序算法，因为相等元素的相对顺序可能会改变。
- 时间复杂度：平均时间复杂度为 (O(n \log n))，最坏情况下时间复杂度为 (O(n^2))（当每次选择的基准元素是最小或最大的元素）。
- 空间复杂度：快速排序的空间复杂度为 (O(\log n))，用于递归栈。
快速排序适用于大多数情况下的排序任务，尤其适合大规模数据的排序，因为其平均时间复杂度较低。
4. 归并排序
归并排序（Merge Sort）是一种经典的排序算法，其基本思想是将两个或两个以上的有序表组合成一个新的有序表。在C语言中实现归并排序，通常采用递归的方式。下面我会详细讲解C语言中归并排序的实现步骤和代码。
归并排序的步骤：
- 分解：将待排序的列表分解成若干个长度为1的子列表，然后两两合并，得到若干个有序的子列表。
- 合并：将相邻的有序子列表合并成一个新的有序列表，直到最后合并成一个有序的列表。
C语言实现：
#include <stdio.h>
#include <stdlib.h>
// 归并所需的辅助数组
int *temp;
// 归并函数，将两个有序数组合并成一个有序数组
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1; // 左子数组的长度
int n2 = r - m; // 右子数组的长度
// 将数组复制到辅助数组中
for (i = 0; i < n1; i++)
temp[l + i] = arr[l + i];
for (j = 0; j < n2; j++)
temp[m + 1 + j] = arr[m + 1 + j];
// 合并临时数组回到原数组中
i = 0; // 初始索引第一个子数组
j = 0; // 初始索引第二个子数组
k = l; // 初始索引合并的子数组
while (i < n1 && j < n2) {
if (temp[l + i] <= temp[m + 1 + j]) {
arr[k] = temp[l + i];
i++;
} else {
arr[k] = temp[m + 1 + j];
j++;
}
k++;
}
// 复制剩余的元素到数组（如果有的话）
while (i < n1) {
arr[k] = temp[l + i];
i++;
k++;
}
while (j < n2) {
arr[k] = temp[m + 1 + j];
j++;
k++;
}
}
// 主函数，用于递归地排序数组
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// 找到中间点
int m = l + (r - l) / 2;
// 分别对前半部分和后半部分进行排序
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// 合并两部分
merge(arr, l, m, r);
}
}
// 辅助函数，用于打印数组
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// 主函数
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
// 动态分配临时数组
temp = (int *)malloc(arr_size * sizeof(int));
printf("给定的数组：\n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("排序后的数组：\n");
printArray(arr, arr_size);
// 释放临时数组
free(temp);
return 0;
}
代码解释：
mergeSort()函数是递归函数，用于不断地将数组对半分，直到每个子数组的长度为1。merge()函数负责将两个有序数组合并成一个有序数组。temp是一个辅助数组，用于在合并过程中存储数据，避免直接在原数组上操作可能导致的元素丢失。main()函数中初始化了待排序的数组，并调用了mergeSort()进行排序，最后打印排序后的数组。
归并排序的性能：
- 时间复杂度：(O(n \log n))，无论是最好、最坏还是平均情况，归并排序的时间复杂度都是 (O(n \log n))。
- 空间复杂度：(O(n))，因为需要一个额外的数组来存储临时数据。
- 稳定性：归并排序是稳定的排序算法，即相等的元素在排序后会保持其原有的顺序。
归并排序在处理大数据集时表现良好，是效率高且稳定的排序算法。
以上就是小编对四大排序的讲解。
如果觉得小编讲的还可以，还请一键三连。互三必回！
持续更新中~！
