64
Java常用算法1——冒泡排序
冒泡排序
时间复杂度：O(n^2)
空间复杂度：O(1)，冒泡排序空间效率很高，只需要一个附加程序单元用于交换
思路：
对于一组包含n个数据的记录，冒泡排序在最坏的情况下需要进行n-1趟排序
第1趟：依次比较0和1、1和2、2和3...（n-2）和（n-1）索引的元素，如果发现第1个数据大于第2个数据，交换他们
经过第1趟排序，最大的元素排到了最后
第2趟：依次比较0和1、1和2、2和3...（n-3）和（n-3）索引的元素，如果发现第1个数据大于第2个数据，交换他们
经过第2趟排序，第二大的元素排到了倒数第二个位置
...
第n-1趟：比较0和1索引的元素，如果发现第1个数据大于第2个数据，交换他们
经过第n-1趟排序，第二小的元素排到了第二个位置
冒泡排序是稳定的
代码：
public class BubbleSort {
private static final int SIZE = 10;
public static void bubbleSort(int[] nums) {
int temp;
for(int i = 1; i < nums.length; i++) {
for(int j = 0; j < nums.length - i; j++) {
if(nums[j] > nums[j+1]) {
temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
System.out.print("第" + i + "次排序的结果为：");
for(int k = 0; k < nums.length; k++) {
System.out.print(" " + nums[k]);
}
System.out.println();
}
}
/**
* 优化过的冒泡排序
* 上面的方法中，即使n个数本来就是有序的，也会进行(n-1)次排序
* 改进：当数组已经有序后，就中断循环
*/
public static void bubbleSortOptimize(int[] nums) {
int temp;
for(int i = 1; i < nums.length; i++) {
boolean flag = true;
for(int j = 0; j < nums.length - i; j++) {
if(nums[j] > nums[j+1]) {
temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
flag = false;
}
}
if(flag) {
// 如果某趟没有交换，说明数组已经有序
break;
}
System.out.print("第" + i + "次排序的结果为：");
System.out.println(Arrays.toString(nums));
}
}
public static void main(String[] args) {
int[] nums = ArraysUtil.makeIntArray(10, 100, SIZE);
System.out.print("排序前的数组为：");
System.out.println(Arrays.toString(nums));
// bubbleSort(nums);
bubbleSortOptimize(nums);
System.out.print("排序后的数组为：");
System.out.println(Arrays.toString(nums));
}
}
生产数组的工具类：
import java.util.Random;
/**
* 操作数组的工具类
*/
public class ArraysUtil {
private static Random rand = new Random();
/**
* 返回长度为size，并且数组中元素的大小范围为[begin, end)的int数组
*/
public static int[] makeIntArray(int begin, int end, int size) {
int[] nums = new int[size];
for(int i = 0; i < size; i++) {
nums[i] = begin + rand.nextInt(end - begin);
}
return nums;
}
}
最后更新：2017-09-06 16:32:34