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

news/2025/2/17 19:34:58/

目录

1.冒泡排序原理

2.快速排序原理

3.冒泡代码实现

4.快速排序代码实现


1.冒泡排序原理

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

原理:

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

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

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

示例

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

  • 第一次遍历:

    • 比较 52,交换,得到 [2, 5, 9, 1, 5, 6]
    • 比较 59,不交换
    • 比较 91,交换,得到 [2, 5, 1, 9, 5, 6]
    • 比较 95,交换,得到 [2, 5, 1, 5, 9, 6]
    • 比较 96,交换,得到 [2, 5, 1, 5, 6, 9]
    • 第一轮结束,最大元素 9 已经“冒泡”到最后。
  • 第二轮遍历:

    • 比较 25,不交换
    • 比较 51,交换,得到 [2, 1, 5, 5, 6, 9]
    • 比较 55,不交换
    • 比较 56,不交换
    • 第二轮结束,最大元素 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;
}

文章来源:https://blog.csdn.net/qq_57342311/article/details/143079973
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ppmy.cn/news/1567773.html

相关文章

spring spring-boot spring-cloud发布以及适配

https://spring.io/blog/2024/10/01/from-spring-framework-6-2-to-7-0 看了 spring 的官网&#xff0c;提到 2025 年 spring 会跟随 jdk 25 LTS发布后&#xff0c;接着发布 Spring Framework 7.0 GA&#xff0c;与之对应 spring 系列的组件版本情况如下。 Spring Framework版…

JavaScript系列(45)--响应式编程实现详解

JavaScript响应式编程实现详解 &#x1f504; 今天&#xff0c;让我们深入探讨JavaScript的响应式编程实现。响应式编程是一种基于数据流和变化传播的编程范式&#xff0c;它使我们能够以声明式的方式处理异步数据流。 响应式编程基础概念 &#x1f31f; &#x1f4a1; 小知识…

设计模式Python版 单例模式

文章目录 前言一、单例模式二、单例模式实现方式三、单例模式示例四、单例模式在Django框架的应用 前言 GOF设计模式分三大类&#xff1a; 创建型模式&#xff1a;关注对象的创建过程&#xff0c;包括单例模式、简单工厂模式、工厂方法模式、抽象工厂模式、原型模式和建造者模…

【山东乡镇界】面图层shp格式乡镇名称和编码wgs84坐标无偏移arcgis数据内容测评

标题中的“山东省乡镇界面图层shp格式乡镇名称和编码wgs84坐标无偏移arcgis数据”指的是一个地理信息系统&#xff08;GIS&#xff09;的数据集&#xff0c;专为山东省的乡镇区域设计。这个数据集包含了乡镇的边界信息&#xff0c;以Shapefile&#xff08;shp&#xff09;格式存…

【数据资产】数据资产管理概述

导读&#xff1a;数据资产管理在企业的数字化转型和业务发展中扮演着至关重要的角色。它直接关系到企业的决策效率、运营优化、业务创新以及风险防控等多个方面。数据资产作为企业的重要战略资源&#xff0c;能够为企业带来经济利益&#xff0c;其价值可能来自于数据本身的稀缺…

Unbutu虚拟机+eclipse+CDT编译调试环境搭建

问题1: 安装CDT&#xff0c;直接Help->eclipse Market space-> 搜cdt , install&#xff0c;等待重启即可. 问题2&#xff1a;C变量不识别vector ’could not be resolved 这是库的头文件没加好&#xff0c;右键Properties->C Build->Enviroment&#xff0c;增加…

前端性能优化指标 - DCL(触发时机、脚本对 DCL 的影响、CSS 对 DCL 的影响)

前端性能优化指标 DCL 1、概述 DCL&#xff08;DOMContentLoaded&#xff09;表示浏览器已经完全加载并解析了页面的初始 HTML 文档&#xff0c;同时完成了 DOM 树的构建&#xff0c;但需等待样式表、图片等外部资源的加载 2、触发时机 当 HTML 文档被完全加载和解析时触发 …

SQL进阶实战技巧:如何构建用户行为转移概率矩阵,深入洞察会话内活动流转?

目录 1 场景描述 1.1 用户行为转移概率矩阵概念 1.2 用户行为转移概率矩阵构建方法 &#xff08;1&#xff09; 数据收集 &#xff08;2&#xff09;定义状态 &#xff08;3&#xff09;数据预处理 &#xff08;4&#xff09;会话划分 &#xff08;5&#xff09;构建状态…