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