冒泡排序java实现

2018-10-23  本文已影响0人  雨落千木的时节

//冒泡排序
//基本思想:两个数比较大小,较大的数下沉,较小的数冒起来
//过程:1.比较相邻的两个数,如果第二个数小就交换位置
//2.从后向前两两比较,一直到比较最前面的两个数据。最终最小数被交换到起始的位置,
//这样第一个最小数的位置就排好了
//继续重复上述过程,依次将第2,3,...n-1个最小数排好位置
//平均时间复杂度为:O(n^2)

public class BubbleSort {

public static void main(String[] args) {

int[] arr = new int[]{6,2,4,1,9,3,6,7,0};

System.out.println("排序前=====");

print(arr);

System.out.println("");

System.out.println("排序后");

long start1 = System.currentTimeMillis();

int[] result = BubbleSort(arr);

long end1 = System.currentTimeMillis();

System.out.println((end1-start1));

print(result);

System.out.println("");

System.out.println("优化后===");

long start2 = System.currentTimeMillis();

int[] result2 = BubbleSort2(arr);

long end2 = System.currentTimeMillis();

System.out.println((end2-start2));

print(result2);

}

public static int[] BubbleSort(int[] arr){

int temp;//临时变量

for(int i=0; i<arr.length-1; i++){

for(int j=arr.length-1; j>i; j--){

if(arr[j]<arr[j-1]){

temp = arr[j];

arr[j] = arr[j-1];

arr[j-1] = temp;

}

}

}

return arr;

}

//优化:

//针对问题:数据的顺序排好后,冒泡算法仍会继续进行下一轮的比较,直到arr.length-1次,后面的比较都是没意义的。
//解决方案:
//设置标志位flag,如果发生了交换flag设为true,如果没有交换flag设为false
//这样一轮比较结束后,如果flag仍未=为false,即这一轮没有发生交换,说明数据的顺序已经排好了,没有必要再继续进行下去。

public static int[] BubbleSort2(int[] arr){

int temp = 0;

boolean flag = false;

for(int i=0; i<arr.length-1; i++){

for(int j=arr.length-1; j>i; j--){

if(arr[j]<arr[j-1]){

temp = arr[j];

arr[j] = arr[j-1];

arr[j-1] = temp;

}

}

}

return arr;

}

public static void print(int[] arr){

for(int i=0; i<arr.length; i++){

System.out.print(arr[i]+",");

}

}

}
上一篇下一篇

猜你喜欢

热点阅读