[数据结构与算法]认识时间复杂度和简单排序算法

排序问题的时间复杂度

选择排序

工作原理：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法
时间复杂度O(N^2)

void selectSort(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);
        }

    }

冒泡排序

工作原理：主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的
时间复杂度O(N^2)

void bullSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        for (int e = arr.length-1; e > 0; e--){
            for (int i = 0; i < e; i++){
                if (arr[i] > arr[i+1]){
                    swap(arr,i,i+1);
                }
            }
        }
    }

交换

以下方法：若i和j是同一个未知的话，会报错

//通过异或运算交换两个数的位置 
 void swap(int[] arr,int i, int j){
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

思考

问题一：
在一个整形数组中，有一个数出现了奇数次，其余数出现了偶数次，请问如何通过异或运算求得该数？

思路：
声明一个int类型的变量eor，让eor依次与该数组中的数值进行异或运算，最后求得eor就是出现了奇数次的数值

问题二：
在一个整形数组中，有两个数出现了奇数次，其余数出现了偶数次，请问如何通过异或运算求得这两个数？

思路：
假设这两个数分别为a，b
声明一个int类型的变量eor，让eor依次与该数组中的数值进行异或运算，最后求得eor为a^b
假设此时a和b中的第八位数值不同（这里采用二进制数，整形32位）并且a的第八位为一
然后声明一个int类型的变量eor1，让eor1分别对第八位为一的数值进行异或运算，最后求得eor1即为a
然后再将eor与eor1进行异或运算，得到b

 void oddTimesNum2(int[] arr){
        int eor = 0;
        for (int i = 0; i<arr.length; i++){
            eor ^= arr[i];
        }
        /*
        * eor = a ^ b
        * eor != 0
        * eor必然有一个位置上是1
        * */
        int rightOne = eor & (~eor + 1);//提取出最右面的1
        //~eor是eor的取反
        int onlyOne = 0;
        for (int cur:arr){
            if ((cur & rightOne) == 0){
                onlyOne ^= cur;
            }
        }
        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }

插入排序

工作原理：每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，寻找最适当的位置，直至全部记录插入完毕
时间复杂度O(N^2)

 void insertSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        //0~0有序的
        //0~i想有序
        for (int i = 1; i < arr.length; i++){
            for (int j = i - 1; j >= 0 && arr[j] >arr[j + 1]; j--){
                swap(arr, j,j + 1);
            }
        }
    }

二分法

经典二分：

在一个有序数组中，找出等于X的数组下标
时间复杂度O(logN)

补充

在一个有序数组中，找出大于等于X最左侧的数组下标（该数组含有多个与X值相同的值）
时间复杂度O(logN)

局部最小值

局部最小：同时小于左侧和右侧的值
在一个无序数组中，任何两个相邻的数不相等，求一个局部最小的数组下标

对数器的概念和使用

1.有一个你想要测的方法a
2.实现复杂度不好但是容易实现的方法b
3.实现一个随机样本产生器
4.把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
5.如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者方法b
6.当样本数量很多时比对测试依然正确，可以确定方法a已经 正确
（个人理解）用自己所写的方法产生的结果与系统所提供的的方法（或者自己所写的另一种实现相同目的方法）产生的额结果进行大规模的对比实验，来判断该方法的正确性