# 基础算法系列之排序算法-2.冒泡排序

```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`

```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;
}```

0 条评论

• ### POJ-3275：奶牛排序Ranking the Cows（Floyd、bitset）

Each of Farmer John's N cows (1 ≤ N ≤ 1,000) produces milk at a different positi...

• ### 对比 Dijkstra Bellman—Ford Spfa 最短路之间区别

本质上Dijkstra是一种贪心,满足局部最优,每次找的是离起点最近的（保证了这个点的距离就是最短路）,如果有负边权,当前找到的就不一定是最近的了。

• ### POJ1258:Agri-Net-最小生成树

Farmer John has been elected mayor of his town! One of his campaign promises was...

• ### c++之内存模型

堆区：由程序员分配释放，若程序员不释放，则程序结束时由系统释放。在c++中主要利用new在堆区开辟内存。

• ### C++核心准则ES.64：使用T{e}记法构造对象

The T{e} construction syntax makes it explicit that construction is desired. The...

• ### 剑指offer第11题：机器人运动范围

此方法我们可以直接按照题目中的要求，将所有的方格全都访问一遍，由于所有的格子需要满足一个条件，连续性和单元格的坐标和小于n即可。