privateint[] bubbleSort(int[] array) { int temp; for (int i = 0; i < array.length - 1; i++) { boolean Flag = false; // 是否发生交换。没有交换,提前跳出外层循环 for (int j = 0; j < array.length - 1 - i; j++) { if (array[j] > array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; Flag = true; } } if (!Flag) { break; } } return array; }
这样理解上,经常会有困难,为什么这样写的是对的?总感觉不太直观。
我试着换了种写法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
publicstaticint[] bubbleSort(int[] nums) { // i is the begin of sorted range, from nums.length ~ 1 for (int i = nums.length; i > 1; i--) { // j is the next max value pointer for (int j = 1; j < i; j++) { int n = nums[j]; // swap if the bubble > the next if (n < nums[j - 1]) { nums[j] = nums[j - 1]; nums[j - 1] = n; } } } return nums; }
// i is the begin of sorted range, from nums.length ~ 1, for (int i = nums.length; i > 1; i--) { // check has swap boolean hasSwap = false; // j is the next max value pointer for (int j = 1; j < i; j++) { int n = nums[j]; // swap if the bubble > the next if (n < nums[j - 1]) { nums[j] = nums[j - 1]; nums[j - 1] = n; hasSwap = true; } }
publicstaticint[] bubbleSortWithSwapIndex(int[] nums) { // bubble sort, add has swap check, add the sorted range
// i is the begin of sorted range, from nums.length ~ 1, for (int i = nums.length; i > 1; ) { // swap index int swapIndex = 0; // j is the next max value pointer for (int j = 1; j < i; j++) { int n = nums[j]; // swap if the bubble > the next if (n < nums[j - 1]) { nums[j] = nums[j - 1]; nums[j - 1] = n; swapIndex = j; } }
if (swapIndex == 0) { break; } else { i = swapIndex; } } return nums; }