冒泡排序
1、介绍:
冒泡排序和选择排序的思想是蛮力法,冒泡,顾名思义,每次选择后面一个元素(最大或者最小)冒上来,从而得到一个有序的序列。比如对于序列:10、8、5、7、3、1的冒泡第一趟演示图示如图所示
可见第一趟过后做大元素10已经沉底,第二趟就对另外的8、5、7、3、1进行上述同样的比较冒泡,会使得最大元素8沉底,...... ,最终可得到一个有序序列。
2、C语言实现
#include <stdio.h>
void bubbleSort(); //声明函数
int arr[10] = {10,6,4,9,7,26,3,1,11,2};
#define n 10 //宏定义需要排序的序列元素个数
int main()
{
bubbleSort(); //调用函数
return 0;
}
//以下是冒泡排序算法
void bubbleSort()
{
int count = 0; //记录进行比较的次数,考量算法的复杂度
int i,j,k;
for(i=0;i<n;i++) //第一层循环控制循环的趟数
{
for(j=0;j<n-1-i;j++) //第二层循环在每趟中进行“冒泡”比较
{
count++; //count+1
if(arr[j]>arr[j+1]) //加入前一个比后一个大,则交换两个数的位置
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for(k=0;k<n;k++) //打印排序后的序列
{
printf("%4d",arr[k]);
}
printf("\nTotal count is %d",count); //打印总共比较的次数
}
程序的运行结果:
2-2、Java代码实现
/**
* 冒泡排序
*@author DR
* @param args
* @return
*2014年3月
*/
public int[] bubbleSort(int...args){ //这里使用JDK提供的可变参数作可变数组
for(int i=0;i<args.length-1;i++){
for(int j=args.length-1;j>i;j--){ //这里从右向左扫描
if(args[j]<args[j-1]){
int temp = args[j];
args[j] = args[j-1];
args[j-1] = temp;
}
}
}
return args;
}
注:
程序中有两个for循环,在args[i]左边的元素是已经沉底的,排序好了的元素;j作为一个扫描指针,从右向左扫描,如果j-1位置的大于j位置的元素,则交换它们,直到把最小的那个元素沉底到i+1位置。
3、冒泡排序算法的优化
对于上面的序列我们发现,含有10个元素的序列需要45次比较(第一趟9次,第二趟8次,第三趟7次,....... ,第九趟1次),那么真的需要45次吗?对于下面的这种序列{1,2,4,5,8,9,10,14,15,13},使用上面的算法也是45次,但观察发现该序列大部分是有序的,第一趟将15沉底放置最后,得到{1,2,4,5,8,9,10,14,13,15},第二趟将14沉底放置最后,得到{1,2,4,5,8,9,10,13,14,15},从第三趟到最后一趟都无需再移动,所以那些比较都是徒劳的,因此,我们对上述算法进行如下优化,减少算法的比较次数。优化的方法就是加一个标志位,记录本趟比较是否发生交换,下一趟根据这个标志位,若上一次没有交换,则本趟比较无需进行。
4、冒泡排序算法优化C语言实现
#include <stdio.h>
void bubbleSort();
int arr[] = {1,2,4,5,8,9,10,14,15,13};
int i,j,k;
int main()
{
bubbleSort();
return 0;
}
void bubbleSort()
{
int flag = 1; //添加控制标志位,记录上一趟是否发生交换
int count = 0;
for(i=0;i<10&&flag;i++) //指针i控制次数
{
for(j=0;j<10-1-i;j++) //j从头开始,将最大的元素沉底到最后
{
flag = 0;
count++;
if(arr[j]>arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = 1;
}
}
}
for(k=0;k<10;k++)
{
printf("%4d",arr[k]);
}
printf("\ntotal count is %d",count);
}
程序运行结果:只需比较24次(第一趟9次,第二趟8次,第三趟7次)
4-2、冒泡排序算法优化Java代码实现
/**
* 冒泡排序的优化算法
*@author DR
* @param args
* @return
*2014年3月
*/
public int[] bubbleSort2(int...args){
boolean flag = true; //是否交换标志位
for(int i=0;i<args.length-1&&flag;i++){
flag = false;
for(int j=args.length-1;j>i;j--){
if(args[j]<args[j-1]){
int temp = args[j];
args[j] = args[j-1];
args[j-1] = temp;
flag = true; //发生交换则让标志位为真
}
}
}
return args;
}
5、总结
总的来说,冒泡排序是最基本简单排序的一种,是一种基于蛮力思想的排序,其时间复杂度为o(n²)。
分享到:
相关推荐
冒泡排序的优化算法,减少时间和次数,引入布尔函数
对冒泡排序法进行优化,比较的次数减少,效率提高
设计一个双向冒泡排序算法。要求用C/C++实现。
数据结构冒泡排序算法 数据结构冒泡排序算法
用java 编写的冒泡排序算法,并涵盖了冒泡排序算法的几种优化方式,以及在冒泡排序上的二分查找法。
php优化版本的冒泡排序算法
该 ppt 为课程讲义,讲解冒泡排序算法原理,及用一个简单实例进行具体分析,还有冒泡排序算法原理的总结等。
数组应用及冒泡排序算法示例,适用于初学者
浅析C语言程序中冒泡排序算法的优化.pdf
冒泡排序算法两种C语言实现方法,在VC开发环境下验证通过
插入和冒泡排序算法Demo
冒泡排序算法,包含前向冒泡、后向冒泡以及双向冒泡
1冒泡排序 2改进的冒泡排序,在一次冒泡的过程中,如果没有发生交换,则已经有序 3进一步改进的冒泡排序,如果在某次冒泡过程中,最后一次进行交换的位置为flag,则表示flag之后的序列已经有序,那么下一次冒泡就...
介绍了C语言冒泡排序算法的原理、步骤、实现方法和优化技巧,以及相关的概念和知识,如数组、循环、交换、比较、稳定性、时间复杂度等。本资源适合C语言初学者和考生使用,帮助他们深入理解和掌握冒泡排序算法的原理...
python 冒泡排序算法 Python 冒泡排序算法 冒泡排序算法是一种简单的排序算法,它的基本思想是通过不断比较相邻的元素,将较大的元素向后移动,较小的元素向前移动,从而实现排序的目的。冒泡排序算法的时间复杂度为...
冒泡排序及其改进算法的分析与比较,曾希君,,冒泡排序算法是大家最为熟悉的排序算法之一,传统的冒泡排序算法过程很简单,并广泛应用于现在的教学及科研中,传统冒泡排序算法
用C++语言实现冒泡排序算法的动态掩饰的代码
根据以下ASMD图设计验证冒泡排序算法。数据串行输入Data_in,串行输出Data_out。给出设计程序及时序仿真结果。
,程序实现冒泡排序十万个数(调用),可以改成输入。并附加程序运行计时,用于测试时间复杂度,可以移除
算法(冒泡,选择,插入,数组排序) package Teacher; import java.io.*; import java.util.Scanner; public class Tset { public static void main(String args[]) throws IOException { // 需要排序的数组,...