http://www.algolist.net/Algorithms/
https://docs.oracle.com/javase/tutorial/collections/algorithms/
https://en.wikipedia.org/wiki/Sorting_algorithm
冒泡排序（Bubble sort）
https://en.wikipedia.org/wiki/Bubble_sort
loop1:
4,6,1,3,7 -> 4,6,1,3,7
4,6,1,3,7 -> 4,1,6,3,7
4,1,6,3,7 -> 4,1,3,6,
4,1,3,6,7 -> 4,1,3,6,7
loop2:
4,1,3,6,7 -> 1,4,3,6,7
1,4,3,6,7 -> 1,3,4,6,7
1,3,4,6,7 -> 1,3,4,6,7
1,3,4,6,7 -> 1,3,4,6,7
loop3:
1,3,4,6,7 -> 1,3,4,6,7
1,3,4,6,7 -> 1,3,4,6,7
1,3,4,6,7 -> 1,3,4,6,7
1,3,4,6,7 -> 1,3,4,6,7
当第三次循环，没有发生swap 说明已排序完成 ，应 break
冒泡排序特点：
1）比较相邻的两个数
2）只能通过判断没有交换来提前结束
最好的情况：
loop1:
1,2,3 -> 1,2,3
1,2,3 -> 1,2,3
最坏的情况：
loop1:
3,2,1 -> 2,3,1
2,3,1 -> 2,1,3
loop2:
2,1,3 -> 1,2,3
1,2,3 -> 1,2,3
loop3:
1,2,3 -> 1,2,3
1,2,3 -> 1,2,3
package sorting;
import java.util.Arrays;
import org.junit.Test;
public class BubbleSorting {
int[] items = { 4, 6, 1, 3, 7 };
int step = 0;
// ① 相邻
// ② 差一步
// ③ n个数可产生 n-1 对
@Test
public void sort() {
for (;;) {
boolean swapped = false;
for (int i = 0; i < items.length - 1; i++) {
step++;
if (items[i] > items[i + 1]) {
swap(i, i + 1);
swapped = true;
}
}
if (!swapped)
break;
}
System.out.println(step + ":" + Arrays.toString(items));
}
public void swap(int i, int j) {
int backup = items[i];
items[i] = items[j];
items[j] = backup;
}
}优化1（砍掉最后一个）
Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
loop1:
4,6,1,3,7 -> 4,6,1,3,7
4,6,1,3,7 -> 4,1,6,3,7
4,1,6,3,7 -> 4,1,3,6,7
4,1,3,6,7 -> 4,1,3,6,7
loop2:
4,1,3,6 -> 1,4,3,6
1,4,3,6 -> 1,3,4,6
1,3,4,6 -> 1,3,4,6
loop3:
1,3,4 -> 1,3,4
1,3,4 -> 1,3,4
无swap 结束
package sorting;
import java.util.Arrays;
import org.junit.Test;
public class BubbleSorting {
int[] items = { 4, 6, 1, 3, 7 };
int step = 0;
// ① 相邻
// ② 差一步
// ③ n个数可产生 n-1 对
// ④ 把最大(小)数移到末尾，n = n -1 来缩小循环次数
@Test
public void sort() {
int l = items.length;
for (;;) {
boolean swapped = false;
for (int i = 1; i < l; i++) {
step++;
if (items[i - 1] > items[i]) {
swap(i - 1, i);
swapped = true;
}
}
l = l - 1;
if (!swapped)
break;
}
System.out.println(step + ":" + Arrays.toString(items));
}
public void swap(int i, int j) {
int backup = items[i];
items[i] = items[j];
items[j] = backup;
}
}优化2（砍掉最后一段）
loop1:
4,6,1,3,7 -> 4,6,1,3,7
4,6,1,3,7 -> 4,1,6,3,7
4,1,6,3,7 -> 4,1,3,6,7
4,1,3,6,7 -> 4,1,3,6,7
loop2:
4,1,3 -> 1,4,3
1,4,3 -> 1,3,4
loop3:
1,3 -> 1,3
package sorting;
import java.util.Arrays;
import org.junit.Test;
public class BubbleSorting {
int[] items = { 4,6,1,3,7 };
int step = 0;
// ① 相邻
// ② 差一步
// ③ n个数可产生 n-1 对
// ④ 找到最后一次交换下标，只保留前面部分
// ⑤ 当 最后一次交换下标 == 0 时，说明没有交换，则终止循环
@Test
public void sort() {
int l = items.length;
for (;;) {
int lastSwapIndex = 0;
for (int i = 1; i < l; i++) {
step++;
if (items[i - 1] > items[i]) {
swap(i - 1, i);
lastSwapIndex = i;
}
}
l = lastSwapIndex;
if (l < 1)
break;
}
System.out.println(step + ":" + Arrays.toString(items));
}
public void swap(int i, int j) {
int backup = items[i];
items[i] = items[j];
items[j] = backup;
}
}