放牛的

放牛的日子，是人生初恋的诗...

0%

冒泡排序

发表于

常见的冒泡排序，基本都是这么写的（摘自维基百科）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int[] 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
public static int[] 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;
}

我的理解思路是这样的：

  • 和插入排序类似，冒泡排序也分为排序好的部分 和 未排序的部分
  • 排序好的部分放在右侧，开始为0个，即索引为nums.length
    • 排序好的部分索引范围：[i, nums.length)
    • 每冒一次泡，多一个元素加入排序好的部分，即索引左移1位
    • 当i到第2个元素的时候，就不需要执行了，即 i == 1 不需要执行
  • 未排序好的部分放在左侧，每次从第2个元素开始，与前一个比较，直到未排序的最后一个元素
    • 未排序的部分索引范围：[0, i)
    • 从第2个元素开始，即 j = 1开始，到未排序的最后一个元素，即 i - 1为止
    • 与前一个元素比较，根据需要交换

当然，可以在这个版本上，加上已经全部有序的验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int[] bubbleSortWithSwapCheck(int[] nums) {
    // bubble sort, add has swap check

    // 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;
            }
        }

        if (!hasSwap) {
            break;
        }
    }
    return nums;
}

类似的，还可以进一步优化，缩短外层循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static int[] 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;
}