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

桃扇骨 2024-03-30 16:20 37阅读 0赞

## 选择排序 ##

//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，所以不支持两个相等的数交换。