基本介绍
冒泡排序(Bubble Sorting)的基本思想是:通过对待 排序序列从前向后(从下标较小的元素开始),依次比较
相邻元素的值,若发现逆序则交换,使值较大 的元素逐渐从前移向后部,就象水底下的气泡一样逐渐 向上冒
由于上面的栗子举的不是很好,所以在代码解析板块的栗子我重新找了一个(这里的代码表示排序的过程)
package data_structure;
import java.lang.reflect.Array;
import java.util.*;
public class BublleSortTest {
public static void main(String[] args) {
int arr[]={3,9,-1,19,-2};
//第一趟排序就是将最大的数排在最后
int temp=0;//定义临时变量
for(int i=0;i<arr.length-1;i++) {
if(arr[i] > arr[i+1]) {
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
System.out.println("第一次排序后的数组");
System.out.println(Arrays.toString(arr));
//第二趟排序就是将第二大的数排在倒数第二位
for(int i=0;i<arr.length-1-1;i++) {
if(arr[i] > arr[i+1]) {
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
System.out.println("第二次次排序后的数组");
System.out.println(Arrays.toString(arr));
//第三趟排序就是将第三大的数排在倒数第三位
for(int i=0;i<arr.length-1-2;i++) {
if(arr[i] > arr[i+1]) {
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
System.out.println("第三次排序后的数组");
System.out.println(Arrays.toString(arr));
//第四趟排序就是将第四大的数排在倒数第四位
for(int i=0;i<arr.length-1-3;i++) {
if(arr[i] > arr[i+1]) {
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
System.out.println("第四次次排序后的数组");
System.out.println(Arrays.toString(arr));
}
}
如果说一个简单的排序要写这么多代码的话那简直是挺着裤裆玩拖把没事找事。下面我们就对代码进行优化。
package data_structure;
import java.lang.reflect.Array;
import java.util.*;
public class BublleSortTest {
public static void main(String[] args) {
int arr[]={3,9,-1,19,-2};
//第一趟排序就是将最大的数排在最后
int temp=0;//定义临时变量
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]) {
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
System.out.println("第"+i+"次排序后的数组");
System.out.println(Arrays.toString(arr));
}
}
}
解析:
拓展:
如果出现比如{1,2,3,4,5}这样排好序的数组,我们再按照上面的方式写的话,就会大大的增加时间(对于数量级较小的数组来将)那么我们可以再优化一下代码。
package data_structure;
import java.util.*;
public class bolle {
public static void main(String[] args) {
int arr[] = { 3, 9, 10, 19, 20 };
// System.out.println("排序前");
// System.out.println(Arrays.toString(arr));
//
bublleSort(arr);
//
// System.out.println("排序后");S
// System.out.println(Arrays.toString(arr));
}
public static void bublleSort(int[] arr) {
int temp = 0;// 定义临时变量
boolean flag = false;// 标识变量,表示是否进行过交换
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]) {
flag = true;// 标识变量为真,那么就执行这段代码
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第"+i+"次排序");
System.out.println(Arrays.toString(arr));
if (flag == false) {// 在一趟排序中,一次都没交换过
break;
} else {
flag = false;// 重置flag,进行下一次轮询(判断,循环)
}
}
}
}
解析:
例如上段代码是已经排好序的,当指针指向各个元素发现已经排好序了那就直接退出。