基础算法系列之排序算法-2.冒泡排序
上篇文章给大家讲述了二分查找算法，现在让我们来一起学习另一个基础算法——冒泡排序算法。它是一个排序算法，可以将一个无序的序列排成有序。它将会是我们以后常用到的算法，所以学会它，用好它对我们以后学习高级算法是很有益处的，那让我们开始冒泡排序算法的学习吧。
冒泡排序
冒泡排序，顾名思义，就像冒泡泡一样，不断将小的数往上"冒"(左移)，大的数不断往下"坠落"(右移)，最终得到一个一个有序的序列。它是一种简单的排序算法。
冒泡排序的算法思想
通过两两比较相邻的数，如果发现这两个数不满足次序要求使，则将这两个数进行交换，从而实现"冒泡"。
冒泡排序的实现过程
从序列的最后一个数开始，不断地将小的数往上冒，通过n-1(假设有n个数)次循坏之后，这组序列就成了一个有序的序列。
代码实现
public static void bubbleSort (int[] a) {
for(int i =0;i<a.length-1;i++) //控制循坏的次数为n-1次
for(int j = a.length-1;j>i;j--){ //从序列的最后一个数开始，逐渐将小的数往上"冒"
if(a[j]<a[j-1]){
a[j] = a[j-1]+a[j]-(a[j-1]=a[j]); //将两个数进行交换，也可以通过中间值temp进行交换
}
}
}运行下面代码，让我们来进行测试一下吧。
public static void main(String[] args) {
int[] a = new int[]{4,3,2,1,8,6,5,10};
bubbleSort(a);
for(int i =0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
是不是与预期的一样呢？！其实还有第二种实现冒泡排序的方法，就是你可以这样想，它既然是从最后一个数开始逐渐将小的数往上"冒"，那我们可不可以从第一个数开始，逐渐将大的数往下"坠落"呢？抱着这种想法让我们来试试吧。
public static void bubbleSort(int[] a ) {
for(int i=0;i<a.length-1;i++) //控制循坏的次数为n-1次
for(int j=0;j<a.length-1-i;j++){ //从序列的第一个数开始，逐渐将大的数往下坠落
if(a[j]>a[j+1]){
a[j] = a[j] + a[j+1] -(a[j+1] = a[j]); //将两个数进行交换，也可以通过中间值temp进行交换
}
}
}让我们继续用上面的测试代码来测试看看吧。
果然，和我们预期的一样，大家以后学习算法的时候也可以逆着想想，看看能不能达到一样的效果，这就是所谓的逆向思维嘛，既然我们已经学了冒泡排序算法，那让我们来做道题，试试手吧。
HDU 2689 Sort it
Problem Description
You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need. For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.
Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.
Output
For each case, output the minimum times need to sort it in ascending order on a single line.
Sample Input
3
1 2 3
4
4 3 2 1Sample Output
0 6问题大意：排序一个序列，并统计要进行交换的次数。
问题分析：这道题是不是让我们想起了之前我们测试用的例子，用我们刚才学习的冒泡排序算法，只要在两个数交换顺序的时候，添加一个计数器count，不就完成了题目的要求嘛。
代码实现：
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("请输入元素个数：");
int n = input.nextInt();
int[] a = new int[n]; //定义数组来存储我们输入的值
System.out.println("请依次输入元素：");
for(int i =0;i<n;i++){
a[i] = input.nextInt();
}
int count=0; //定义计数器count
count = bubbleSort(a);
for(int i =0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
System.out.println("需要交换的次数为："+count);
}
public static int bubbleSort(int[] a ) {
int count=0; //定义计数器count
for(int i=0;i<a.length-1;i++) //控制循环次数为n-1次
for(int j=0;j<a.length-1-i;j++){ //从序列的第一个数开始，逐渐将大的数往下"坠落"
if(a[j]>a[j+1]){
a[j] = a[j] + a[j+1] -(a[j+1] = a[j]); //将两个数进行交换，也可以通过中间值temp进行交换
count++; //计数器自增
}
}
return count;
}让我们来测试一下吧。
总述
通过以上的学习，你是否学会了冒泡排序算法呢~相信以你的聪明才智肯定学会了ヾ(◍°∇°◍)ﾉﾞ