交换排序之冒泡排序
2018-02-26 本文已影响3人
官先生Y
基本思想
冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
两种操作：比较和交换
Java代码实现
冒泡排序非标准版
public class BubbleSortForNonstandard {
public static void main(String[] args) {
int[] sequence = new int[]{9, 1, 5, 8, 3, 7, 4, 6, 2};
System.out.println("排序前：" + Arrays.toString(sequence));
bubbleSort(sequence);
System.out.println("排序后：" + Arrays.toString(sequence));
}
private static void bubbleSort(int[] sequence) {
for (int i = 0; i < sequence.length - 1; i++) {
for (int j = i + 1; j <= sequence.length - 1; j++) {
if (sequence[i] > sequence[j]) {
swap(sequence, i, j);
}
}
}
}
private static void swap(int[] sequence, int i, int j) {
int temp;
temp = sequence[i];
sequence[i] = sequence[j];
sequence[j] = temp;
}
}
- 因为此代码实现不满足"两两比较相邻记录"的冒泡排序思想，从严格意义上不算是标准的冒泡排序算法。但是它跟冒泡排序一样在序列中小的数会想冒泡一样放在前面。
- 思路就是让每一个关键字，都和它后面的每一个关键字比较，如果大则交换，这样第一位置的关键字在一次循环后一定变成最小值，后面的关键字类似。
- 缺陷：（9, 1, 5, 8, 3, 7, 4, 6, 2）在排序好1和2位置后，对其余关键字的排序没有什么帮助（数字3反而还被换到了最后一位）。也就是说，这个算法的效率是非常低的。
冒泡排序标准版
public class BubbleSortStandard {
/**
* 从后往前冒泡，头部元素先确定顺序
*
* @param sequence
*/
public static void bubbleSort(int[] sequence) {
int length = sequence.length;
for (int i = 0; i < length - 1; i++) {
for (int j = length - 1; j > i; j--) {
if (sequence[j - 1] > sequence[j]) {
swap(sequence, j - 1, j);
}
}
}
}
/**
* 从前往后冒泡，尾部元素先确定顺序
*
* @param sequence
*/
private static void bubbleSort2(int[] sequence) {
for (int i = 0; i < sequence.length - 1; i++) {
for (int j = 0; j < sequence.length - i - 1; j++) {
if (sequence[j] > sequence[j + 1]) {
swap(sequence, j, j + 1);
}
}
}
}
private static void swap(int[] sequence, int formerIndex, int latterIndex) {
int temp;
temp = sequence[formerIndex];
sequence[formerIndex] = sequence[latterIndex];
sequence[latterIndex] = temp;
}
public static void main(String[] args) {
System.out.println("方法一 ：从后往前冒泡，头部元素先确定顺序");
int[] sequence = new int[]{9, 1, 5, 8, 3, 7, 4, 6, 2};
System.out.println("排序前：" + Arrays.toString(sequence));
bubbleSort(sequence);
System.out.println("排序后：" + Arrays.toString(sequence));
System.out.println("----------------------");
System.out.println("方法二 ：从前往后冒泡，尾部元素先确定顺序");
int[] sequence2 = new int[]{9, 1, 5, 8, 3, 7, 4, 6, 2};
System.out.println("排序前：" + Arrays.toString(sequence2));
bubbleSort2(sequence2);
System.out.println("排序后：" + Arrays.toString(sequence2));
}
}
关注点：
- 事实上，在不断循环的过程中，除了将关键字1放到第一的位置，我们还将关键字2从第九位提到了第三的位置，显然这一算法比前面的要有进步，在上十万条数据的排序过程中，这种差异会体现出来。
- 较小的数字从如同气泡般慢慢浮到上面，因此就将此算法命名为冒泡算法。
冒泡排序优化版
public class BubbleSortOptimized {
/**
* 冒泡排序优化 第一种写法 推荐
*/
public static void main(String[] args) {
System.out.println("方法一 ：从后往前冒泡，头部元素先确定顺序");
int[] sequence = new int[]{9, 1, 5, 8, 3, 7, 4, 6, 2};
sequence = new int[]{2, 1, 3, 4, 5, 6, 7, 8, 9};
System.out.println("排序前：" + Arrays.toString(sequence));
bubbleSort(sequence);
System.out.println("排序后：" + Arrays.toString(sequence));
System.out.println("----------------------");
System.out.println("方法二 ：从前往后冒泡，尾部元素先确定顺序");
int[] sequence2 = new int[]{9, 1, 5, 8, 3, 7, 4, 6, 2};
sequence2 = new int[]{2, 1, 3, 4, 5, 6, 7, 8, 9};
System.out.println("排序前：" + Arrays.toString(sequence2));
bubbleSort2(sequence2);
System.out.println("排序后：" + Arrays.toString(sequence2));
}
/**
* 冒泡排序优化 第二种写法
*/
private static void bubbleSort2(int[] sequence) {
for (int i = 0; i < sequence.length - 1; i++) {
boolean flag = true;
for (int j = 0; j < sequence.length - i - 1; j++) {
if (sequence[j] > sequence[j + 1]) {
swap(sequence, j, j + 1);
flag = false;
}
}
if (flag)
break;
}
}
/**
* 从后往前冒泡，头部元素先确定顺序
*/
public static void bubbleSort(int[] sequence) {
int length = sequence.length;
boolean flag = true;
for (int i = 0; i < length - 1 && flag; i++) {
flag = true;
for (int j = length - 1; j > i; j--) {
if (sequence[j - 1] > sequence[j]) {
swap(sequence, j - 1, j);
flag = false;
}
}
}
}
private static void swap(int[] sequence, int formerIndex, int latterIndex) {
int temp;
temp = sequence[formerIndex];
sequence[formerIndex] = sequence[latterIndex];
sequence[latterIndex] = temp;
}
}
关键点：
- 代码改动的关键点在于i变量的for循环中，增加了对flag是否为true的判断。经过这样的改进，冒泡排序在性能上就有了一些提升，可以避免在已经有序的情况下的无意义循环判断
