冒泡排序

(1)冒泡排序的基本思想是在排序过程中,对待排序序列中相邻两个元素关键字的值进行比较,当不满足排序要求时就交换两个元素的位置。这样,关键字值较小的元素就会像水中的气泡一样逐层浮起,直至完成排序过程。利用蛮力法容易实现冒泡排序的算法涉及。

(2)在某一遍扫描中,对元素list[i]与list[i+1]的关键字进行比较,若list[i]>list[i+1],则交换list[i]与list[i+1]的位置,这样重复扫描,直到在某一遍扫描时不存在list[i]>list[i+1]的情况,排序结束。

(3)在经过一次扫描后,关键字最大的元素就沉底了,排到了线性表的最后一个位置,且在比较过程中,凡是关键字较小的元素都浮上了一层。在第i+1次扫描时,不必自上而下的比较线性表中所有的相邻元素对,只需要比较从list[1]到list[N-1]的相邻元素就可以了,这是因为经过i次扫描后,线性表中元素list[N-i+1]到list[N]的元素都已经在正确的位置了,不必再次扫描。实际排序过程中,如果经过k趟冒泡排序后,就已经排好序了,就不必继续进行后序的排序,为此可以设置一个标志flag,用来记录每趟扫描是否还存在元素的交换,若已经没有元素的交换,则排序可以提前结束。

(4)冒泡排序算法

void bubbleSort(int list[],int n){
int i=1,j,t,flag=1;
for(i=1;i<n&&flag;i++){
flag=0;
for(j=1;j<=n-1;j++){
if(list[j]>list[j+1]){
t=list[j];
list[j]=list[j+1];
list[j+1]=t;
flag=1;
}
}
}
}

(5)完整程序

#include
#define N 20
int list[N+1];
void insertSort(int list[],int n){
int i,j;
for(i=2;i<=n;i++){
list[0]=list[i];
j=i-1;
while(j>0&&list[0]<list[j]){
list[j+1]=list[j];
j–;
}
list[j+1]=list[0];
}
}
void bubbleSort(int list[],int n){
int i=1,j,t,flag=1;
for(i=1;i<n&&flag;i++){
flag=0;
for(j=1;j<=n-1;j++){
if(list[j]>list[j+1]){
t=list[j];
list[j]=list[j+1];
list[j+1]=t;
flag=1;
}
}
}
}
int main(){
int i,n;
scanf(“%d”,&n);
for(i=1;i<=n;i++){
scanf(“%d”,&list[i]);
}
//insertSort(list,n);
bubbleSort(list,n);
for(i=1;i<=n;i++){
printf(“%d “,list[i]);
}
return 0;
}