排序算法

• 冒泡排序
• 附录：交换的技巧

冒泡排序

第一种写法

public static void bubbleSort(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]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

第二种改良写法

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

第三种写法，在下一轮比较时，只需比较到上一轮比较中，最后一次发生交换的位置即可。因为后面的所有元素都没有发生过交换，必然已经有序了。

public static void bubbleSort(int[] arr) {
    int lastExchangeIndex = 0;
    int sortBorder = arr.length - 1;
    for (int i = 0; i < arr.length - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < sortBorder; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        if (!flag) {
            break;
        }
    }
}

附录：交换的技巧

一般的我们会用中间变量，进行两个值的交换，如下

int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

但是这种情况，需要额外的空间，如果我们不使用额外的空间，如何交换呢？

加法：

arr[j] = arr[j] + arr[j + 1];
arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];

减法：

arr[j] = arr[j] - arr[j + 1];
arr[j + 1] = arr[j] + arr[j + 1];
arr[j] = arr[j + 1] - arr[j];

但是这两种方式都有可能造成数组越界，最好使用异或的方式进行交换。

arr[j] = arr[j] ^ arr[j + 1];
arr[j + 1] = arr[j] ^ arr[j + 1];
arr[j] = arr[j] ^ arr[j + 1];