马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
快速排序和冒泡排序
一、快速排序（Quick Sort）
原理
- 焦颔首脑：像“分蛋糕”一样不停拆解标题。
- 步调：
- 选一个基准值（好比第一个数）
- 把比基准值小的扔左边，大的扔右边
- 对左边和右边重复这个操纵，直到全部数排好
举个栗子 🌰
假设要排序的数组是 [5,3,8,6,4]：
- 第1轮：选第一个数 5 当基准
- 左边找比5大的，右边找比5小的，交换位置：[5,3,4,6,8]
- 终极基准归位：[3,4,5,6,8]
- 递归处理处罚左边 [3,4] 和右边 [6,8]（继续选基准拆分）
明白话表明：
就像整理书架，先恣意挑一本书当“分边界”，把比它薄的书放左边，厚的放右边。然后左右两堆书各自再按同样方法整理，直到全部书排好次序。- #include <stdio.h>
- // 交换两个元素的值
- void swap(int *a, int *b) {
- int temp = *a;
- *a = *b;
- *b = temp;
- }
- // 快速排序的核心分区操作
- int partition(int arr[], int low, int high) {
- int pivot = arr[(low + high) / 2]; // 选择中间元素作为基准值
- int i = low - 1; // 左指针
- int j = high + 1; // 右指针
- while (1) {
- do { i++; } while (arr[i] < pivot); // 找到左边比基准大的元素
- do { j--; } while (arr[j] > pivot); // 找到右边比基准小的元素
- if (i >= j) return j; // 当指针相遇时返回分割点
- swap(&arr[i], &arr[j]); // 交换左右不符合条件的元素
- }
- }
- // 递归实现快速排序
- void quickSort(int arr[], int low, int high) {
- if (low < high) {
- int pi = partition(arr, low, high); // 获取分割点
- quickSort(arr, low, pi); // 排序左半部分
- quickSort(arr, pi + 1, high); // 排序右半部分
- }
- }
- // 测试代码
- int main() {
- int arr[] = {5, 3, 8, 6, 4};
- int n = sizeof(arr) / sizeof(arr[0]);
- quickSort(arr, 0, n - 1);
- printf("快速排序结果：");
- for (int i = 0; i < n; i++)
- printf("%d ", arr[i]); // 输出：3 4 5 6 8
- return 0;
- }
二、冒泡排序（Bubble Sort）
原理
- 焦颔首脑：像“煮开水冒泡”一样把最大的数推到末了。
- 步调：
- 重新开始比力相邻两个数，假如前大后小就交换
- 每轮竣事后，最大的数会“沉”到末了
- 重复直到全部数排好
举个栗子 🌰
同样排序 [5,3,8,6,4]：
- 第1轮：
- 5和3比 → 交换 → [3,5,8,6,4]
- 5和8比 → 不换
- 8和6比 → 交换 → [3,5,6,8,4]
- 8和4比 → 交换 → [3,5,6,4,8]
- 第2轮：处理处罚前4个数 [3,5,6,4]，末了得到 [3,5,4,6,8]
- 重复直到完全有序（共需4轮）
明白话表明：
就像一群人按身高列队，从左到右两两比力，高的今后站。每一轮竣事，最高的人就站到了末了。下一轮不消管末了的人，继续重新开始比，直到全部人排好。- #include <stdio.h>
- // 冒泡排序实现
- void bubbleSort(int arr[], int n) {
- for (int i = 0; i < n-1; i++) { // 外层循环控制轮次
- 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;
- }
- }
- }
- }
- // 测试代码
- int main() {
- int arr[] = {5, 3, 8, 6, 4};
- int n = sizeof(arr) / sizeof(arr[0]);
- bubbleSort(arr, n);
- printf("冒泡排序结果：");
- for (int i = 0; i < n; i++)
- printf("%d ", arr[i]); // 输出：3 4 5 6 8
- return 0;
- }
三、对比总结
对比项快速排序冒泡排序速率快（均匀时间复杂度 O(n log n)）慢（均匀时间复杂度 O(n²)）实用场景大数据量教学演示、小数据量焦点操纵拆分成子标题（分治头脑）相邻元素两两交换比喻分蛋糕 → 切块处理处罚煮开水 → 气泡上浮人话版总结
- 假如你有1000本书要整理：用快速排序（先分堆再整理）。
- 假如你只有5本书要整理：用冒泡排序（一本本对比换位置）。
- 快速排序像“聪明人拆解标题”，冒泡排序像“诚实人一步步来”。
|
发表于 2025-10-10 13:10:40