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

冒泡排序的基本思路是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。
例如，我们需要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("%s\n",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);
	}
}

冒泡排序的核心是双重循环嵌套。时间复杂度为O(N*2)。

上节：桶排序。
下节：快速排序。