数据结构与算法之冒泡排序(一)
冒泡排序
冒泡排序是基于交换思想的排序方法。它将相邻的两个元素加以比较,若左边元素值大于右边元素值,则将这两个元素交换位置;若左边元素值小于右边元素值,则这两个元素位置不变。右边元素继续和下一个元素进行比较,重复这个过程,直到比较到最后一个元素为止。
伪代码描述
BUBBLE-SORT(A)
1 for i <—— 0 to length[A]-1
2 do for j <—— 0 to length[A]-i-1 downto i+1
3 do if A[j] > A[j+1]
4 then exchange A[j] > A[j-1]
下图说明了输入实例为A={5,2,4,6,1,3}时,算法BUBBLE-SORT的工作过程。对外层迭代一次,在A[length-i]的位置得到一个A[0 - length-1]的一个最大值.深色表示交换的两个元素。
java代码实现
/*
* @author ZWT
*
* @date 2019/04/07
*
*冒泡排序 参数
* a -- 待排序的数组
*/
public static int[] BubbleSort(int[] a) {
//控制遍历次数为a.length-1次
for (int i = 0; i < a.length-1; i++) {
//控制每次遍历比较次数
for (int j = 0; j < a.length-1-i; j++) {
if (a[j] > a[j+1]) {
//交换
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
return a;
}
现在对刚才的代码进行优化,提高算法的效率
/*
* @author ZWT
*
* @date 2019/04/07
*
*冒泡排序 参数
* a -- 待排序的数组
*/
public static int[] BubbleSort(int[] a) {
//设置标志
int flag ;
//控制遍历次数为a.length-1次
for (int i = 0; i < a.length-1; i++) {
flag = 0;
//控制每次遍历比较次数
for (int j = 0; j < a.length-1-i; j++) {
if (a[j] > a[j+1]) {
//交换
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
//将标志置为1
flag = 1;
}
}
//判断标志是否为0
if(flag == 0){
return a;
}
}
return a;
}