排序算法1：插入排序 基础知识：

核心：遍历扫描数组，将每一步所得的最小值放入相应的位置。

****：对于同样时间复杂度的算法，比较其速度，执行代码比较时间即可。

时间复杂度：

空间复杂度：

****：空间复杂度

解释:若出执行算法时，需要另外开辟与原数组等规模的空间。

代码实现：

        Java实现：

public static int[] sort(int[] ins){
                
	for(int i=1; i0; j--){
			if(ins[j] 
        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：异或运算 
基础知识： 
性质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;
}
 
相关算法问题及代码实现： 
异或问题1：一堆数中，只有一个数出现了奇数次，其余均出现了偶数次，如何找出该数？ 
解题思路:将所有的数进行异或操作,出现偶数次的数经过异或操作后必定为0,最终的异或结果为出现奇数次的数
 
代码实现: 
public static void printOddTimesNum1(int[] arr){
        int eor = 0;
        for(int cur : arr)
                eor ^= cur;
        system.out.println(eor);
}
 
异或问题2:若有两个数出现奇数次,该如何求解? 
解题思路:仿照问题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);
    }
 
二分法的详解与扩展： 
问题1：在一个有序数组中，找某个数是否存在。 
//算法第四版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;
}
 
问题2：在某个数组中，找>=某个数最左侧的位置。 
待更新
 
问题3：局部最小值问题。 
待更新
 
测试方法:对数器方法（在无OJ的情况下，可以测试代码正确性） 
 
 
对数器的概念和使用
 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
 
 
 1.有一个你想要测的方法a，测试一个选择排序 
//选择排序
public static int[] sort(int[] ins){
                
	for(int i=1; i0; j--){
			if(ins[j] 
2. 实现一个绝对正确但是复杂度不好的方法b， 调用系统的排序 
此方法核心要保证绝对正确，时间复杂度无需考虑
 
 
    public static void  comparator(int [] arr){
        Arrays.sort(arr);
    }
 
3.★★★实现一个随机样本产生器 
//产生随机数组
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;
}
 
4.实现比对的方法 
//测试,复制一个新数组，避免污染原数组
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;
}