【排序算法】冒泡排序(Bubble Sort)


0. 说明

  参考 *中的冒泡排序

  冒泡排序 (Bubble Sort) 是与插入排序拥有相等的执行时间,但是两种算法在需要的交换次数却很大地不同。

  在最坏的情况,冒泡排序需要 O(n2)  次交换。

  冒泡排序演算法的运作如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

1. 伪代码

function bubble_sort (array, length) {
var i, j;
for(i from to length-){
for(j from to length--i){
if (array[j] > array[j+])
swap(array[j], array[j+])
}
}
}
函数冒泡排序输入一个数组名称为array 其长度为length
i 从0 到(length - )
j 从0 到(length - - i)
如果array[j] > array[j + ]
交换array[j] 和array[j + ] 的值
如果结束
j循环结束
i循环结束
函数结束

2. 助记码

 i∈[,N-) //循环N-1遍
j∈[,N--i) //每遍循环要处理的无序部分
swap(j,j+) //两两排序(升序/降序)

3. Java 实现

/**
* 冒泡排序
*/
public class Bubble1 {
// 定义冒泡排序方法 bubbleSort1
public static int[] bubbleSort1(int[] arr) {
// 使用循环排序
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 将较大值赋值给中间值
int e = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = e;
}
}
}
return arr;
} // 定义遍历输出方法
public static void output(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
} public static void main(String[] args) {
// 定义整形数组
int[] arr1 = {5, 7, 2, 9, 3};
int[] arr2 = bubbleSort1(arr1);
output(arr2);
}
}

上一篇:asp.net mvc ActionResult


下一篇:Django 之 序列化