两种交换排序算法--冒泡，快速

目录

1.冒泡排序原理

2.快速排序原理

3.冒泡代码实现

4.快速排序代码实现

---

1.冒泡排序原理

冒泡排序（Bubble Sort）是一种简单的排序算法，基本思想是通过反复交换相邻的元素，直到整个序列有序。它的名字来源于较大的元素像气泡一样“浮”到序列的顶部。

原理：

1. 初始状态：我们从数组的第一个元素开始，比较相邻的两个元素。如果第一个元素大于第二个元素，就交换它们的位置；如果不大，则继续比较下一对元素。

2. 第一轮排序：通过一轮比较后，最大的元素会被“冒泡”到数组的最后面。

3. 继续排序：接着，我们对剩下的未排序部分继续进行类似的比较和交换，直到剩下的部分只有一个元素，意味着数组已经排序完成。

示例：

假设有一个数组 [5, 2, 9, 1, 5, 6]，我们来演示一下冒泡排序的过程。

• 第一次遍历：

  • 比较 5 和 2，交换，得到 [2, 5, 9, 1, 5, 6]
  • 比较 5 和 9，不交换
  • 比较 9 和 1，交换，得到 [2, 5, 1, 9, 5, 6]
  • 比较 9 和 5，交换，得到 [2, 5, 1, 5, 9, 6]
  • 比较 9 和 6，交换，得到 [2, 5, 1, 5, 6, 9]
  • 第一轮结束，最大元素 9 已经“冒泡”到最后。

• 第二轮遍历：

  • 比较 2 和 5，不交换
  • 比较 5 和 1，交换，得到 [2, 1, 5, 5, 6, 9]
  • 比较 5 和 5，不交换
  • 比较 5 和 6，不交换
  • 第二轮结束，最大元素 6 已经排好位置。

以此类推，直到所有元素都排好顺序。

时间复杂度：

• 最好的情况（已经有序）：O(n)
• 最坏的情况（逆序）：O(n²)
• 平均情况：O(n²)

虽然冒泡排序简单易懂，但由于其时间复杂度较高，通常在处理大数据时效率不高。

2.快速排序原理

快速排序（Quick Sort）是一种效率很高的排序算法，采用分治法（Divide and Conquer）的策略。它通过选择一个“基准”元素（pivot），然后将数组分成两部分：一部分比基准小，另一部分比基准大。接着递归地对这两部分分别进行快速排序，最终得到有序数组。

快速排序的基本原理：

1. 选择基准元素：从数组中选择一个元素作为“基准”（pivot）。基准的选择方式可以有多种，比如选择第一个元素、最后一个元素、随机选择等。

2. 分区操作：将数组重新排列，确保基准元素左边的元素都比它小，右边的元素都比它大。此时，基准元素已经排好位置了。

3. 递归排序：对基准元素左边和右边的子数组分别进行快速排序。

4. 终止条件：当子数组的长度为1或0时，递归终止，因为已经有序。

示例：

假设我们有一个数组 [10, 7, 8, 9, 1, 5]，我们来演示一下快速排序的过程。我们选择最后一个元素 5 作为基准。

• 第一轮分区：

  • 从左到右扫描数组，将小于基准元素的放左边，大于基准元素的放右边。最终，数组被分为 [1, 5, 8, 9, 7, 10]，基准 5 排在了正确的位置。
  • 此时，基准元素 5 处于正确位置，左边的部分 [1] 和右边的部分 [8, 9, 7, 10] 需要继续排序。

• 递归对左部分排序：左边部分只有一个元素 [1]，已经有序，不需要做任何操作。

• 递归对右部分排序：右边部分 [8, 9, 7, 10]，选择基准元素 10：

  • 分区后得到 [8, 9, 7, 10]，基准元素 10 排在了正确的位置。
  • 然后继续对 [8, 9, 7] 排序。

• 继续递归分区：

  • 对 [8, 9, 7] 选择基准 7，分区后得到 [7, 9, 8]。
  • 对 [9, 8] 进行排序，最终得到 [7, 8, 9]。

经过递归排序，最终得到有序的数组 [1, 5, 7, 8, 9, 10]。

快速排序的时间复杂度：

• 最优情况：当每次分区操作都能将数组均匀分成两部分时，时间复杂度是 O(n log n)。
• 最坏情况：当数组已经是升序或降序时，每次分区只能将一个元素排到正确位置，时间复杂度为 O(n²)。
• 平均情况：O(n log n)，这是最常见的情况，且快速排序在大多数情况下都非常高效。

空间复杂度：
快速排序的空间复杂度通常为 O(log n)，因为递归的深度最多为 log n（最好的情况下），但它是一个原地排序算法，不需要额外的存储空间。

优缺点：

• 优点：快速排序通常比其他 O(n log n) 排序算法（如归并排序）更高效，特别是对于大规模数据。
• 缺点：最坏情况下时间复杂度较高（O(n²)），但在实际应用中，通过优化基准元素的选择（比如三数取中法）可以有效避免这种情况。

3.冒泡代码实现

#include <stdio.h>
#include <stdlib.h>
#include <time.h>//冒泡排序typedef int ElemType;//顺序表
typedef struct SqList {ElemType* data;//指针，指向一块内存的起始地址int length;//存储动态数组的长度
}SqList;//顺序表初始化
void initSqList(SqList& L, int len) {L.length = len;L.data = (ElemType*)malloc(sizeof(ElemType) * L.length);//分配空间srand(time(NULL));//随机数生成for (int i = 0; i < L.length; i++){L.data[i] = rand() % 100;//随机生成数字存入顺序表，对100取余是为了规范存入的数据是0-99}
}//顺序表打印
void printSqList(SqList L) {for (int i = 0; i < L.length; i++){printf("%3d", L.data[i]);}printf("\n");
}void swap(ElemType& a, ElemType& b) {ElemType temp = a;a = b;b = temp;
}//冒泡排序顺序表中的元素
void bubbleSort(ElemType* arr, int length) {for (int i = 0; i < length - 1; i++) {   //外层循环，控制循环次数，最多n-1次bool flag = false;      // 标记本趟排序是否发生交换for (int j = length - 1; j > i; j--) {  //内层循环，从后往前通过比较冒出本趟最小元素if (arr[j - 1] > arr[j]) {          //小于前一个元素则交换swap(arr[j - 1], arr[j]);flag = true;}}if (flag == false) {   //本趟没有交换，说明有序，结束return;}}
}int main() {SqList L;//定义一个顺序表initSqList(L, 10);//初始化顺序表，分配10个空间printSqList(L);//打印顺序表中的值	bubbleSort(L.data, 10);//将顺序表进行排序printSqList(L);return 0;
}

4.快速排序代码实现

#include <stdio.h>
#include <stdlib.h>
#include <time.h>//快速排序typedef int ElemType;//顺序表
typedef struct SqList {ElemType* data;//指针，指向一块内存的起始地址int length;//存储动态数组的长度
}SqList;//顺序表初始化
void initSqList(SqList& L, int len) {L.length = len;L.data = (ElemType*)malloc(sizeof(ElemType) * L.length);//分配空间srand(time(NULL));//随机数生成for (int i = 0; i < L.length; i++){L.data[i] = rand() % 100;//随机生成数字存入顺序表，对100取余是为了规范存入的数据是0-99}
}//顺序表打印
void printSqList(SqList L) {for (int i = 0; i < L.length; i++){printf("%3d", L.data[i]);}printf("\n");
}void swap(ElemType& a, ElemType& b) {ElemType temp = a;a = b;b = temp;
}// 分割数组
int partition(ElemType* arr, int low, int high) {ElemType pivot = arr[low];         //将当前第一个元素作为枢轴元素，划分数组while (low < high) {               //外层循环，low和high相遇时为枢轴元素的最终位置while (low < high && arr[high] >= pivot) //从后往前找到第一个小于枢轴的元素跳出循环--high;arr[low] = arr[high];    //将小于枢轴的元素移到左端while (low < high && arr[low] <= pivot)  //从前往后找到第一个大于枢轴的元素跳出循环++low;arr[high] = arr[low];    //将大于枢轴的元素移到右端}arr[low] = pivot;   //枢轴元素放入最终位置return low;         //返回枢轴的最终位置
}// 快速排序顺序表中的元素
void quickSort(ElemType* arr, int low, int high) {if (low < high) {    //递归结束条件//将表分为两个子表，枢轴元素是中间值，左子表小于它，右子表大于它int pivotpos = partition(arr, low, high); //枢轴元素已放入最终位置quickSort(arr, low, pivotpos - 1);  //依次递归处理两个子表quickSort(arr, pivotpos + 1, high);}
}int main() {SqList L;//定义一个顺序表initSqList(L, 10);//初始化顺序表，分配10个空间printSqList(L);//打印顺序表中的值quickSort(L.data, 0, 9);//将顺序表进行排序printSqList(L);return 0;
}