左程云算法课堂笔记

        C实现：

void insertionSort(int data[], int size) {
    int i, j, key;
    for (i = 1; i <= size - 1; i++) {
        key = data[i];
        j = i;
        while (data[j-1] > key && j >= 1) {
            data[j] = data[j-1];
            j--;
        }
        data[j] = key;
    }
}

性质1：0与任何数异或，仍是该数本身。

性质2：任何一个数与自身异或，结果为0。

性质3：异或满足交换律与结合律。

        使用异或实现swap函数：

//使用异或实现swap函数
//需保证a与b不指向同一块内存地址
public static void swap (int a,int b){
        a = a^b;
        b = a^b;
        a = a^b;
}

解题思路:将所有的数进行异或 *** 作,出现偶数次的数经过异或 *** 作后必定为0,最终的异或结果为出现奇数次的数

/*一堆数中，只有一个数出现了奇数次，
**其余均出现了偶数次，如何找出该数？*/
public static void printOddTimesNum1(int[] arr){
        int eor = 0;
        for(int cur : arr)
                eor ^= cur;
        system.out.println(eor);
}

解题思路:仿照问题1,将所有数进行异或 *** 作,最终eor中保留的变量结果为两个出现奇数次数的异或结果.由于两个数必定不相同,则根据eor中的某位不为0的数为基准,继续进行异或 *** 作.此时可以获得其中一个出现奇数次的数eor2,最后再将eor与eor2异或,得到第二位奇数次的数.

public static void printOddTimesNum2(int[] arr){
        int eor = 0;
        for(int curNum : arr)
            eor ^= curNum;
        //eor必定不为0
        int eor2 = 0;
        //找到eor中最右边不为0的数
        int rightOne = eor & (~eor + 1);
        //以该位为标准，继续异或整个数组
        for (int cur:arr)
            if ((cur & rightOne) == 0)
                eor2 ^= cur;
        System.out.println(eor2 + " " + eor^eor2);
    }

//算法第四版p15
//rank函数的一个借口，Java中的方法重载
public static int rank(int key, int[] a)
{
    return rank(key, a, 0, a.length - 1);
}
//二分查找的递归实现
public static int rank(int key, a, int lo, int hi)
{
    if(lo > hi)
        return -1;
    int mid = lo + (hi - lo) / 2;//防止溢出
    //位运算速度更快
    //int mid = lo + ((hi - lo)>>1);
    if (key < a[mid])
        return rank(key, a, lo, mid - 1);
    else if (key > a[mid])
        return rank(key, a, mid + 1, hi);
    else
        return mid;
}

待更新

待更新

对数器的概念和使用
0，有一个你想要测的方法a，
1，实现一个绝对正确但是复杂度不好的方法b，
2，实现一个随机样本产生器
3，实现比对的方法
4，把方法a和方法b比对很多次来验证方法a是否正确。
5，如果有一个样本使得比对出错，打印样本分析是哪个方法出错，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
————————————————
版权声明：本文为CSDN博主「qxlxi」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/jia970426/article/details/105057929

//选择排序
public static int[] sort(int[] ins){
                
	for(int i=1; i0; j--){
			if(ins[j]

 /***
     * 2. 实现一个绝对正确的但是复杂度不好的方法b
     *  调用系统中的排序算法Arrays.sort 排序
     */
    public static void  comparator(int [] arr){
        Arrays.sort(arr);
    }

//产生随机数组
public static int[] generateRandomArray(int maxSize, int maxValue){
    //Math.random -> 等概率产生并返回一个[0,1)上所有的小数
    //Math.random() * N -> 所有小数，等概率返回一个
    //(int)(Math.random() * N) -> [0,N-1]上所有的整数，等概率返回一个
    int[] arr = new int[(int)((maxSize + 1) * Math.random())];//数组长度随机
    for (int i = 0;i < arr.length;i++){
        arr[i] = (int)((maxValue + 1) * Math.random()) - (int)(maxValue * Math.random());
    }
    return arr;
}

//测试,复制一个新数组，避免污染原数组
public static int[] copyArray(int[] arr){
    if (arr == null){
        return null;
    }
    int[] res = new int[arr.length];
    for (int i = 0;i < arr.length;i++)
        res[i] = cur[i];
    return res;
}

//for test
public static boolean isEqual(int[] arr1, int[] arr2){
    if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null))
        return false;
    if (arr1 == null && arr2 == null)
        return  true;
    if (arr1.length != arr2.length)
        return false;
    for (int i = 0; i < arr1.length;i++)
        if (arr1 != arr2)
             return false;
    return true;
}