排序算法之相邻之间分高低----冒泡排序

80 阅读 0 评论 53 点赞

我是靠谱客的博主爱笑飞机，这篇文章主要介绍排序算法之相邻之间分高低----冒泡排序，现在分享给大家，希望可以做个参考。

冒泡排序的基本思路是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。
例如，我们需要12 43 54 64 23这几个数从大到小排序。那么小的数自然小排在后面。首先比较12和43，由于12比43小，则互换它们的位置，顺序变成43 12 54 64 23。
按照刚才的做法，比较第二位和第三位，发现12比54小，则互换它们的位置，顺序变成43 54 12 64 23。以此类推，当一轮比较过后，顺序就变成43 54 64 23 12，最小的12就被交换到了最后。我们给这个这个过程称为“一趟”。
开始第二趟时，再次比较第一位和第二位，43比54小，交换，顺序变成54 43 64 23 12；比较第二位和第三位，43比64小，交换，顺序变成54 64 43 23 12；比较第三位和第四位，43比23大，则不交换。此时我们不再需要比较第四位和第五位了，因为在第一趟我们就已经确定好第五位是最小的了。
第三趟同样，最后顺序变成64 54 43 23 12。
第四趟发现已经排好了，但是这是一种巧合，不同的数字会有不同的情况，所以仍要进行第四趟，发现64比54大，则不交换。到此，冒泡排序就结束了。
c语言实现如下：

#include<stdio.h>
int main(){
int a[100],i,j,t,n;
scanf("%d",&n);
//输入一个数，表示有n个数排序
for(i=0;i<n;i++)
scanf("%d",&a[i]);
//冒泡排序核心
for(i=0;i<n-1;i++){
for(j=0;j<n-i-1;j++){
if(a[j]<a[j+1])
{ t=a[j];a[j]=a[j+1];a[j+1]=t; }
}
}
for(i=0;i<n;i++)
printf("%d ",a[i]);
getchar();getchar();
return 0;
}

稍作修改，解决桶排序遗留的问题：
c语言实现如下：

#include<stdio.h>
struct stu{
char name[21];
int score;
};
int main(){
struct stu a[100],t;
int i,j,n;
scanf("%d",&n);
//输入一个数，表示有n个数排序
for(i=0;i<n;i++)
scanf("%s %d",a[i].name,&a[i].score);
//冒泡排序核心
for(i=0;i<n-1;i++){
for(j=0;j<n-i-1;j++){
if(a[j].score<a[j+1].score)
{ t=a[j];a[j]=a[j+1];a[j+1]=t; }
}
}
for(i=0;i<n;i++)
printf("%sn",a[i].name);
getchar();getchar();
return 0;
}

Java语言实现如下：

import java.util.Scanner;
class student{
String name;
int score;
student(String name,int score){
this.name=name;
this.score=score;
}
}
public class Maopao {
public static void main(String[] args) {
student []stu =new student[100];
int i,j,n;
student t;
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
for(i=0;i<n;i++)
stu[i]=new student(sc.next(),sc.nextInt());
for(i=0;i<n-1;i++){
for(j=0;j<n-i-1;j++){
if(stu[j].score<stu[j+1].score)
{ t=stu[j];stu[j]=stu[j+1];stu[j+1]=t; }
}
}
for(i=0;i<n;i++)
System.out.println(stu[i].name);
}
}