上篇文章给大家讲述了二分查找算法,现在让我们来一起学习另一个基础算法——冒泡排序算法。它是一个排序算法,可以将一个无序的序列排成有序。它将会是我们以后常用到的算法,所以学会它,用好它对我们以后学习高级算法是很有益处的,那让我们开始冒泡排序算法的学习吧。
冒泡排序
冒泡排序,顾名思义,就像冒泡泡一样,不断将小的数往上"冒"(左移),大的数不断往下"坠落"(右移),最终得到一个一个有序的序列。它是一种简单的排序算法。
冒泡排序的算法思想
通过两两比较相邻的数,如果发现这两个数不满足次序要求使,则将这两个数进行交换,从而实现"冒泡"。
冒泡排序的实现过程
从序列的最后一个数开始,不断地将小的数往上冒,通过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 1
Sample 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;
}
让我们来测试一下吧。
总述
通过以上的学习,你是否学会了冒泡排序算法呢~相信以你的聪明才智肯定学会了ヾ(◍°∇°◍)ノ゙