数据结构与算法-----冒泡排序
浏览数:2485 

冒泡排序
1)算法
A.比较相邻的元素,如果第一个比第二个大就交换它们;
B.对每一对相邻的元素都做同样的工作,从开始的第一对到结尾的最后一对。经过这一步,最后的元素是最大值;
C.针对所有的元素重复以上步骤,除了最后一个;
D.持续每次对越来越少的元素重复以上步骤,直到没有元素需要交换。
2)评价
平均时间复杂度O(N^2),稳定,对数据的有序性敏感。

#include<iostream>
#include<cstdlib>
using namespace std;
int getRandom(){
int num=rand()%100;
return num;
}
int* getArray(int *data,int size){
int num;
for(int i=0;i<size;++i){
 num=getRandom();
 data[i]=num;
//  *(data+i)=i;
}
return data;
}
void Print(int *data,int size){
for(int i=0;i<size;++i){
 cout<<data[i]<<' ';
}
cout<<endl;
}
//冒泡排序算法,经过优化
void bubbleSort(int *data,int size){
int count=0;//测试循环的次数
for(int i=0;i<size-1;++i){
 bool ordered=true;
 for(int j=0;j<size-1-i;++j){
  count++;
  if(data[j+1]<data[j]){
   int tmp=data[j+1];
   data[j+1]=data[j];
   data[j]=tmp;
   ordered=false;
  }
 }
 if(ordered==true)
  break;  
}
cout << "count:" << count<<endl;
}
int main(){
int *data;
int size;
cout<<"Pls input the size:";
cin>>size;

srand(time(0));

int* tmp=getArray(data,size);

bubbleSort(tmp,size);

Print(tmp,size);

return 0;

}

联系管理员
 
 
 
 
 工作时间
周一至周五 :9:30-17:30
免费建站
会员登录
登录
我的资料
留言
回到顶部