排序算法——冒泡与快排

一、冒泡排序

1.1 定义

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的序列，依次比较相邻的两个元素，如果它们的顺序错误（如升序时前一个大于后一个）就交换位置。每一轮遍历都会将当前未排序部分的最大（或最小）元素“冒泡”到序列的一端，因此得名“冒泡排序”。

1.2 实现流程

初始化：设定待排序序列长度为 nn，外层循环控制遍历轮数。

相邻比较：从第一个元素开始，依次比较相邻的两个元素。

条件交换：如果前一个元素大于后一个元素（升序排序），则交换它们的位置。

减少范围：每完成一轮遍历，最后一个元素即为当前最大值，下一轮遍历范围减少一位（即已排序部分不再参与比较）。

优化提前结束：设置一个标志位，若某一轮遍历中没有发生任何交换，说明序列已有序，可提前终止排序。

1.3 示例演示

以升序排序序列[5, 1, 4, 2, 8]为例：

1.5 代码实现

// 冒泡排序函数 void BubbleSort(SqList *L) { int i, j; int temp; // 外层循环控制排序的轮数 for (i = 0; i < L->length - 1; i++) { // 内层循环进行相邻元素的比较和交换 for (j = 0; j < L->length - 1 - i; j++) { if (L->r[j].key > L->r[j + 1].key) { // 交换相邻的元素 temp = L->r[j].key; L->r[j].key = L->r[j + 1].key; L->r[j + 1].key = temp; } } } } // 打印排序后的顺序表 void PrintList(SqList *L) { for (int i = 0; i < L->length; i++) { printf("%d ", L->r[i].key); } printf("\n"); } int main() { // 示例数据初始化 SqList L = {{5, 2, 9, 1, 5, 6}, 6}; // 排序前的顺序表 printf("Before sorting: "); PrintList(&L); // 调用冒泡排序 BubbleSort(&L); printf("After sorting: "); PrintList(&L); return 0; }

二、快速排序

2.1 定义

快速排序（Quick Sort）是一种基于分治思想的排序算法。它通过选择一个基准元素（枢轴），将待排序序列划分为两个子序列：左侧子序列的所有元素都小于等于基准，右侧子序列的所有元素都大于等于基准，然后递归地对左右子序列进行同样的操作，最终使整个序列有序。

2.2 核心思想

1. 分治策略：将大问题分解为若干小问题，分别解决后再合并。

2. 原地排序：通过交换元素实现划分，不需要额外数组空间。

3. 递归实现：对划分后的子数组重复执行相同操作，直到子数组长度为1或0。

2.3 实现流程

1. 选择枢轴

通常选择数组的第一个元素、最后一个元素或中间元素作为枢轴（pivot）

示例中假设选择arr[start]作为枢轴

2. 划分操作

设置两个指针i和j，通常i从左侧开始，j从右侧开始

遍历数组，将小于枢轴的元素放到左侧，大于枢轴的元素放到右侧

最终将枢轴放置到正确位置，使得：

左侧所有元素 ≤ 枢轴

右侧所有元素 ≥ 枢轴

3. 递归排序

对枢轴左侧的子数组递归执行快速排序

对枢轴右侧的子数组递归执行快速排序

递归终止条件：子数组长度为 0 或 1（已有序）

2.4 示例演示

以升序排序数组[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]，选择第一个元素6为枢轴：

2.5 代码实现

// 分割函数：选择枢轴并进行分区操作 int partition(SqList *L, int low, int high) { int pivotkey; pivotkey = L->r[low].key; // 选择第一个元素作为枢轴 while (low < high) { // 从右边找到小于枢轴的元素 while (low < high && L->r[high].key >= pivotkey) { high--; } L->r[low] = L->r[high]; // 将小于枢轴的元素放到左边 // 从左边找到大于枢轴的元素 while (low < high && L->r[low].key <= pivotkey) { low++; } L->r[high] = L->r[low]; // 将大于枢轴的元素放到右边 } L->r[low].key = pivotkey; // 将枢轴元素放到正确的位置 return low; // 返回枢轴元素的位置 } // 快速排序函数 void quickSort(SqList *L, int low, int high) { if (low < high) { int pivotIndex = partition(L, low, high); // 获取枢轴位置 quickSort(L, low, pivotIndex - 1); // 对枢轴左边部分递归排序 quickSort(L, pivotIndex + 1, high); // 对枢轴右边部分递归排序 } }

2.6 复杂度比较