数据结构：交换排序的实现

概要

交换排序是一类通过比较和交换元素位置来实现排序的算法。其核心思想是在序列中进行两两比较，若元素顺序不符合排序要求，则交换它们的位置。常见的交换排序算法包括冒泡排序和快速排序，它们在不同场景下各有优劣。

整体架构流程

冒泡排序

从数组的第一个元素开始，依次比较相邻的两个元素；
如果前一个元素大于后一个元素（假设为升序排序），则交换这两个元素的位置；
对数组中的每一对相邻元素都执行上述操作，经过一轮比较后，最大的元素会 “浮” 到数组的末尾；
重复上述步骤，每次比较的范围减少一个元素（因为上一轮已经将最大元素排到了末尾），直到整个数组有序。

快速排序

选择一个基准元素（pivot），通常选择数组的第一个元素或中间元素；
重新排列数组，将所有比基准元素小的元素移到基准元素的左边，所有比基准元素大的元素移到基准元素的右边。这个过程称为分区（partition）操作；
递归地对基准元素左边和右边的子数组进行快速排序，直到子数组的长度为 1 或 0（此时子数组已经有序）。

技术名词解释

冒泡排序（Bubble Sort）

一种简单的交换排序算法，通过多次比较相邻元素并交换位置，使较大（或较小）的元素逐渐 “冒泡” 到数组的末尾（或开头）。其时间复杂度在最坏和平均情况下为 O (n²)，空间复杂度为 O (1)，适用于小规模数据的排序。

快速排序（Quick Sort）

高效的交换排序算法，采用分治思想。通过选择基准元素并进行分区操作，将数组分为两部分，分别对两部分递归排序。平均时间复杂度为 O (n log n)，最坏时间复杂度为 O (n²)（当基准元素选择不当，如数组已经有序时），空间复杂度在平均情况下为 O (log n)，适用于大规模数据的排序。

分区（Partition）

快速排序中的关键操作。将数组按照基准元素分为两部分，左边部分的元素都小于基准元素，右边部分的元素都大于基准元素。这个操作确定了基准元素在最终有序数组中的正确位置，并且使得左边和右边的子数组都更接近有序状态，为后续递归排序做好准备。

技术细节

冒泡排序实现细节

#include <stdio.h>void bubbleSort(int arr[], int sz) {int i = 0;int j = 0;int temp = 0; // 第三方存储器int flag = 1; // 用于查看是否不需要排序，1 --- 不需要排序，0 --- 需要排序// 遍历数组多趟for (i = 0; i < sz - 1; i++) {// 每一趟的操作flag = 1; // 每趟都需要重置for (j = 0; j < sz - 1 - i; j++) {if (arr[j] > arr[j + 1]) {flag = 0;temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}// 如果不需要排序，则直接结束函数if (flag) {return;}}
}int main() {int arr[] = { 1, 5, 2, 12, 54, 2, 23 };int sz = sizeof(arr) / sizeof(arr[0]); // 数组大小bubbleSort(arr, sz); // 冒泡排序// 查看排序结果int i = 0;for (i = 0; i < sz; i++) {printf("%d ", arr[i]);}return 0;
}

在这段代码中，外层循环控制排序的轮数，每一轮会将一个最大元素移到数组末尾。内层循环负责在每一轮中进行相邻元素的比较和交换，比较的范围随着轮数增加而逐渐减少（sz - 1 - i）。

同时我还引入了一个flag标志位，用于优化排序过程。在每一轮开始时，将flag置为 1，如果在某一轮的比较中发生了元素交换，就将flag置为 0。如果某一轮结束后flag仍为 1，说明在这一轮中没有元素交换，数组已经有序，此时可以提前结束排序，从而提高排序效率。

快速排序实现细节

#include <stdio.h>// 分区函数：将数组分为两部分，返回基准值的位置
int partition(int arr[], int left, int right) {int pivotKey = arr[left]; // 选择第一个元素作为基准值while (left < right) { // 当左指针小于右指针时循环// 从右向左扫描，找到第一个小于基准值的元素while (left < right && arr[right] >= pivotKey) {right--; // 右指针左移}arr[left] = arr[right]; // 将小于基准值的元素放到左边// 从左向右扫描，找到第一个大于基准值的元素while (left < right && arr[left] <= pivotKey) {left++; // 左指针右移}arr[right] = arr[left]; // 将大于基准值的元素放到右边}arr[left] = pivotKey; // 将基准值放到正确的位置return left; // 返回基准值的位置
}// 快速排序函数
void qSort(int arr[], int left, int right) {// 如果左指针小于右指针，继续排序if (left < right) {int pivotLoc = partition(arr, left, right); // 获取基准值的位置// 递归排序左半部分qSort(arr, left, pivotLoc - 1);// 递归排序右半部分qSort(arr, pivotLoc + 1, right);}
}int main() {int arr[] = { 1, 5, 2, 12, 54, 2, 23 }; // 待排序的数组int sz = sizeof(arr) / sizeof(arr[0]); // 计算数组的大小qSort(arr, 0, sz - 1); // 调用快速排序函数// 输出排序后的数组printf("排序后的数组: ");for (int i = 0; i < sz; i++) {printf("%d ", arr[i]);}printf("\n");return 0; // 程序正常结束
}

在这段代码中，partition 函数负责实现分区操作。首先选择数组的第一个元素 arr[left] 作为基准值 pivotKey。然后通过两个嵌套的 while 循环，从数组的两端向中间扫描。第一个内层 while 循环从右向左扫描，找到第一个小于基准值的元素，将其移动到左边；第二个内层 while 循环从左向右扫描，找到第一个大于基准值的元素，将其移动到右边。

这样不断交换，直到左指针 left 和右指针 right 相遇，此时将基准值 pivotKey 放到正确的位置 arr[left] ，并返回 left，即基准值在数组中的最终位置。

qSort 函数是快速排序的递归实现部分。当 left 小于 right 时，调用 partition 函数获取基准值的位置 pivotLoc，然后递归地对基准值左边的子数组 arr[left...pivotLoc - 1] 和右边的子数组 arr[pivotLoc + 1...right] 进行排序，从而实现整个数组的快速排序。