选择&冒泡&插入排序以及交换两数的三种方式

选择排序

//0~n位 先排第 0 位的，将 1~n 的分别与 0 上的比较，如果小于它，交换
// 再排第 1 位，将 2~n 的分别与 0 上的比较，如果小于它，交换
//以此类推
public static void selectSort(int[] arr) {
    if (arr == null || arr.length < 2) return;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                swap1(arr, i, j);
            }
        }
    }
}
public static void swap1(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

冒泡排序

public static void bubbleSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // 将 0 ~ n - i 的数中最大的数放到 n - i 位置
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap2(arr, j, j + 1);
            }
        }
    }
}
 
public static void swap2(int[] arr, int i, int j) {
    arr[i] = arr[i] + arr[j];
    arr[j] = arr[i] - arr[j];
    arr[i] = arr[i] - arr[j];
}

插入排序

// 将 j 位置的数与前面的对比，插到自己按顺序该在的地方
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            swap1(arr, j, j - 1);
        }
    }
}
 
public static void swap1(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

三种交换值的方式：

其实三面已经用了两种了，至于为啥没用第三种，主要还是因为第三种交换方式存在一定的使用条件（等下将）。

第一种

int a = 1;
int b = 1;
int tmp = a;
a = b;
b = tmp;
System.out.println(a);
System.out.println(b);

第二种

int a = 1;
int b = 1;
a = a + b;
b = a - b;
a = a - b;
System.out.println(a);
System.out.println(b);

第三种

int a = 1;
int b = 1;
a = a ^ b; // ①
b = a ^ b; // ②
a = a ^ b; // ③
System.out.println(a);
System.out.println(b);
 
//这里就会有错了，这里并不能成功把 a、b 交换
//因为这种交换方式只适用于两个数不相等的情况下

位操作符重要规律：

如果一个操作数异或另一个数两次，那结果还是原来那个数据。是由下面两点推出了的：

1.一个数异或上自己结果为 0
2.一个数异或上 0 结果为自己
这两点都非常好理解（自己写个数试试就知道了）。那么一个操作数异或另一个数两次如： a ^ b ^ b，其中 b ^ b 为 0，那么原来的式子就相当于 a ^ 0 了，那么就等于 a

知道了上面知识点后就来解释下交换的代码：

int a = 1; 
int b = 1;
// 以下为了避免大家混乱，我用 a' 和 b' 表示 a 和 b 交换前的值 
a = a' ^ b'; // ①
b = a ^ b'; // ② 由于 a = a' ^ b'，所以此处相当于：b = a' ^ b' ^ b';  那就等于 a'
a = a ^ b; // ③ 由于 a = a' ^ b'，b 等于 a'，所以此处相当于：b = a' ^ b' ^ a';  那就等于 b'

成功交换，但由于一个值异或上它自己为0，所以不支持两个相等的数交换。