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

选择排序

//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.一个数异或上自己结果为 02.一个数异或上 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，所以不支持两个相等的数交换。