位运算符、冒泡、插入、选择排序

理想

2022-1-6

CS基础知识 Java

写在前面

关于文章

本系列文章主要根据算法大神左神（左程云）的算法与数据结构基础教程进行整理的，这里文章主要学习了有时间复杂度、^位运算符、寻找数组中出现的单数、冒泡排序、插入排序、选择排序、对数器等。这里只是基于Java的相关代码实现。

我的站点

网络云书签-理想](http://dh.imyjs.cn/

理想智能云解析 (imyjs.cn)

任务墙 (imyjs.cn)

LiXiang's Blog (gitee.io) 不再更文

学编程那点事儿 (imyjs.cn)
联系我

🐧：2410685763

WeChat：Super_Baby_00

公众号：编程那点事儿

异或运算

^ 异或操作，相同为0，不同为1.理解为不进位相加
有交换率、结合律
a^a=0 a^0=a

案例一

要求：使用异或运算交换两个数，不使用第三个变量。

public static void main(String[] args) {
        int[] arr = new int[] {1, 2, 3, 4};
        System.out.println(Arrays.toString(arr));
        swap(arr,1,2); //交换数组中 2 和 3 的位置
        System.out.println(Arrays.toString(arr));
    }

    public static void swap(int[] arr, int i, int j){
        if (i != j){  //不能两个值指向同一地址
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j]; //就是arr[i]^arr[j]^arr[j]就成了arr[i]
            arr[i] = arr[i] ^ arr[j]; //表示arr[i]^arr[j]^arr[i]就是arr[j]
        }
    }

不能两个值指向同一地址

a^a=0、a^0=a

案例二

题目：一组数只有一个数出现一次，其他出现两次，找出这个出现一次的数

public static int process(int[] arr){
        if (arr == null){ 
            return -1;
        }
        int eor = 0;
        for (int num:
             arr) {
            eor ^= num;
        }
        return eor;
    }

案例三★

取出一个数最右边1的位置

public static void main(String[] args) {
        int pos = 10; // 二进制：0000 1010
        int mostRightOne = pos & (~pos + 1); 
        // ~取反：1111 0101  再+1：1111 0110  再&最终得: 0000 0010 转十进制为2
        // mostRightOne值在二进制位上的位次就是pos得最右第一个1的位置
        System.out.println(mostRightOne); //2
    }

题目：一组数只有两个数出现一次，其他出现两次，找出这两个数

因为两个值不同，所以两个值定存在二进制某一位定不同，用这两个值的异或结果二进制中的1，从而将数字分成两组，该位为1和不为1

public static void process2(int[] arr) {
        int eor = 0;
        // 首先拿0异或数组全部数字
        // 由异或的a^a=0、a^0=a得结果为eor = a ^ b
        // 因为a≠b所以eor≠0 所以eor至少有一位不为0
        // 假设第12位为1 那么a 和 b 在第12位不同

        for (int num: arr) {
            eor ^= num;
        }
        int rightOne = eor & (~eor + 1); // 取出eor中二进制为1的位值（必存在，因为a 和 b 不同值）

        // 此时在拿eor2 再去异或数组中的数字，但是此时只异或在第12位不是1的数字
        int eor2 = 0;
        for (int cur : arr) {
            // 对应位为1的值取出进行^最后的到两个单数对应位为1的
            // (num&rightOne)==0得到对应位为0
            if ((cur & rightOne) == 0) {
                eor2 ^= cur;  //最终得到就是a或b
            }
        }
        System.out.println(eor2); // 必须先打印eor2 因为此时eor等于a^b
        System.out.println(eor ^ eor2); // 两个单数其中一个值
    }

这里需要好好理解一下!

排序

冒泡排序

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动图演示

代码实现

private static void bubbleSort(int[] arr){
        boolean flag;
        for (int i = 0; i < arr.length; i++){
            flag = true; //设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            for (int j = i + 1; j < arr.length; j++){
                if (arr[j] < arr[i]){
                    swap(arr,i,j);
                    flag = false;
                }
            }
            if (flag){
                return;
            }
        }
    }
    private static void swap(int[] arr, int i, int j){
        if (i != j){
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }
    }

算法分析

最佳情况：T(n) = O(n)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)

选择排序

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

动画演示

代码实现

private static void OptionSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {  // 确定几轮比较
            int minIndex = i;  //每次将第一个数记为最小
            for (int j = i + 1; j < arr.length; j++) {  //依次往后比较
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;  //比第一个数小交换坐标
            }
            swap(arr, i, minIndex); //最后将第i个坐标的数字换成最小的 保证了前i个坐标的数字是有序的
        }
    }

算法分析

最佳情况：T(n) = O(n2)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)

插入排序

算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

动画演示

代码实现

private static void insertionSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        for (int i = 1; i < arr.length; i++){  // 保证 0 ~ i 有序
            // j 为当前i的前一个元素 当j>=0 保证访问数组不越界 且第j个数大于其后边的数 交换位置 
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--){
                swap(arr,j,j + 1);
            }
        }
    }

其他实现：

// 前移动
public static void insertSort(int[] arr) {
        for (int i=1;i<arr.length;i++){
            int insertValue = arr[i];
            int i2 = i-1;
            while (i2>=0&&insertValue<arr[i2]){
                arr[i2+1]=arr[i2];
                i2--;
            }
            arr[i2+1]=insertValue;
        }
    }

//交换
public static void insertSort(int[] arr) {
        for (int i=1;i<arr.length;i++){
            int insertValue = arr[i];
            int i2 = i-1;
            while (i2>=0&&insertValue<arr[i2]){
                arr[i2+1]=arr[i2];
                i2--;
            }
            arr[i2+1]=insertValue;
        }
    }

算法分析

最佳情况：T(n) = O(n)
最坏情况：T(n) = O(n2)
平均情况：T(n) = O(n2)

对数器

public static void isSuccess(){
    Random random = new Random();
    int[] ints = new int[100];
    int[] ints1;
    for (int i=0;i<10000;i++){
        for (int i1 = 0; i1 < ints.length; i1++) {
            ints[i1]=random.nextInt(100);
        }
        ints1=ints.clone();
        int[]ints2=ints.clone();
        //两种排序方法进行排序
        mergeSort(ints,0,ints.length-1,new int[ints.length]);
        optionSort(ints1);
        if (!Arrays.equals(ints,ints1)){
            System.out.println(Arrays.toString(ints2)+"失败");
            return;
        }
    }
    System.out.println("成功");