(排序)冒泡排序的三种实现
排序 实现 三种 冒泡排序
2023-09-14 08:59:06 时间
主要内容:
1、冒泡排序
2、冒泡排序实现1
3、冒泡排序实现2
4、冒泡排序实现3
一、冒泡排序的原理
冒泡排序是简单的一种排序方法,效率低下,复杂度为O(n^2),其具体的算法流程如下:
1、算法需要对数组遍历n-1遍;
2、在每一次遍历中,比较前后相邻元素的大小,如果第一个比第二个大,则交换他们,这样第一次遍历之后数组最后一个值就是最大值;
3、依次重复上面的步骤,就可以得到升序排序的数组。
复杂度分析:
最差时间复杂度(数组从大到小,交换次数):(n-1)+(n-2)+……+1=n*(n-1)/2=O(n^2)
最好时间复杂度(数组从小到大,交换次数):0
二、冒泡排序的实现1
如上述原理:
// naive bubbleSort void bubbleSort1(int a[],int n){ int tmp; for(int i=1;i<=n-1;i++){ for(int j=0;j<n-i;j++){ if(a[j]>a[j+1]){ tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp; } } } }
三、冒泡排序的实现2
设置一个标识,如果在某一趟遍历中没有发生交换,说明排序已经完成,即算法完成。
// set flag to indicate which step to stop void bubbleSort2(int a[],int n){ int tmp; bool change=true; for(int i=1;i<=n-1 && change;i++){ change=false; for(int j=0;j<n-i;j++){ if(a[j]>a[j+1]){ tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp; change=true; } } } }
四、冒泡排序的实现3
如果数组有100个数,仅前面10个无序,后面90个有序,那么第一趟遍历后,最后发生交换的位置必定小于10,记录下这个位置,第二次遍历只需要从数组头部遍历到这个位置即可。
// set flag to indicate what next step should begin from void bubbleSort3(int a[],int n){ int tmp; bool change=true; int flag=n-1; int k; for(int i=1;i<=n-1 && change;i++){ change=false; k=flag; for(int j=0;j<k;j++){ if(a[j]>a[j+1]){ tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp; change=true; flag=j; } } } }
相关文章
- Skill语言实现将一个table中的坐标point(x,y)按照x和y进行从小到大排序的函数
- 重新排序-研究生组G题
- 高性能排序函数实现方案
- java桶式排序算法详解编程语言
- python实现快速排序详解编程语言
- 排序MySQL升序降序排序实现方法(mysql升序降序)
- MySQL排序之中文实现(mysql排序中文)
- 以大小排序 Linux: 实现更佳性能(linux大小排序)
- 排序按行排序查询SQL Server中的数据(sqlserver查询行)
- MySQL求和排序实现细节分析(mysql求和排序)
- 利用Oracle排序语句实现数据排序(oracle排序语句)
- 功能利用 Oracle 实现精准的数据排序(oracle的排序)
- MySQL实现汉字拼音排序的办法(mysql汉字拼音排序)
- SQL语句中MySQL的两种升序排序方法(mysql两种升序)
- Oracle中排序的优先级排序简介(oracle中排序的顺序)
- C#排序算法之快速排序
- js对象数组按属性快速排序
- 如何让access自动编号从1开始排序实现方法
- C语言实现排序算法之归并排序详解