排序-冒泡排序

冒泡排序介绍

    冒泡排序，使用2层循环，一边比较，一边把大的移动的下一位，这样每次循环最后一个都是当前最大的。

    优化写法，如果循环内没有做一次交换，则没有剩下的就是已经排好序的，无需再继续比较。进一步优化的方法是，如果记录没有交换的下标，下次比较的时候只进行到下标位置。

    时间复杂度O($n^{2}$)，空间复杂度O(1)。

1
2
3
4
5
6
7
8
9
private void bubble(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] < arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}
交换

    最常见的交换方法是开辟临时区域交换。

1
2
3
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

    还有一种方式，通过先加后减或先减后加的方式，不用新内存即可实现，但这种方式有可能因为int越界导致异常。

1
2
3
4
5
6
7
8
9
// 先加后减
arr[j + 1] = arr[j + 1] + arr[j];
arr[j] = arr[j + 1] - arr[j];
arr[j + 1] = arr[j + 1] - arr[j];

// 先减后加
arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
arr[j + 1] = arr[j + 1] + arr[j];

    最好的交换方式是使用位运算。

1
2
3
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];