算法笔记——时间复杂度-选择排序-冒泡排序-插入排序-二分法-异或运算-递归行为及时间复杂度_冒泡排序和二分法排序时间复杂度

一、时间复杂度

常数时间的操作

一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常熟操作。
例如：int a = arr[i] 此时只是在数组中寻找偏移量，找到i位置的数，这就是一个常数操作，和数据量无关，还有就是加减乘除也是，位运算等等。
而非常数操作，要得到链表i位置的值，int b = list.get(i)，需要遍历，直到i位置，和数据量是有关的。

时间复杂度为一个算法流程中，常熟操作数量的一个指标。常用O(读作big O)来表示。具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。

在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那 么时间复杂度为O(f(N))。

评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行 时间，也就是“常数项时间”。

二、选择排序

1.算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
1
2
3

2.代码

public class chooseSort {
    public static int [] selectSort(int [] arr){
        if (arr.length == 0 || arr.length < 2){
            return arr;
        }
        for (int i = 0; i < arr.length; i++){
            int midIndex = i;
            for (int j = i+1; j < arr.length; j++){
                //找最小的数
                midIndex = arr[midIndex] > arr[j] ? j : midIndex;
            }
            swap(arr,i,midIndex);
        }
        return arr;
    }
    public static void swap(int []arr,int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、冒泡排序

1.算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1
2
3

2.代码

public class bubbleSort {

    public static int [] bubbleSort1(int arr[]){
        if (arr.length == 0 || arr.length < 2){
            return arr;

        }
        for (int i = 0; i < arr.length-1; i++){
            for (int j = 0; j < arr.length-1-i; j++){
                if (arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    //异或运算 a b 的内存必须不同
//                    arr[j] = arr[j] ^ arr[j+1];
//                    arr[j+1] = arr[j] ^ arr[j+1];
//                    arr[j] = arr[j] ^ arr[j+1];
                }
            }
        }
//        for (int e = arr.length -1; e > 0; e--){ 每轮的范围
//            for (int i = 0; i < e; i++){每轮几次
//                if (arr[i] > arr[i+1]){
//                    int temp = arr[i];
//                    arr[i] = arr[i+1];
//                    arr[i+1] = temp;
//                }
//            }
//        }
        return arr;
    }
    public static void main(String[] args) {
        int arr[] = {2,4,1,4,2,4,2,6};
        int arr1[] = bubbleSort1(arr);
        for (int i = 0 ; i < arr1.length;i++){
            System.out.println(arr1[i]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

四、插入排序

1.算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
1
2

2.代码

public class insertSort {
    public static int [] insertionSort(int arr[]){
        if (arr.length == 0 || arr.length < 2){
            return arr;
        }
        //0-0肯定是有序的
        //保证0-1有序
        //....
        //保证0 - N-1有序
        for (int i = 1; i < arr.length; i++){ //保证0-i有序
            for (int j = i-1; j >=0 && arr[j] > arr[j+1]; j--){
                /*每次从前一个开始比较，如果前一个小，直接跳过
                * 如果arr[j] > arr[j+1]，此时交换，j前移，再和新来的值做个比较
                * 以此类推
                * 一直到j<0，停止*/
                swap(arr,j,j+1);
            }
        }
        return arr;
    }
    public static void swap(int []arr,int i, int j){
//        int temp = arr[i];
//        arr[i] = arr[j];
//        arr[j] = temp;
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

五、二分法和拓展

1.在一个有序数组中，找某个数是否存在

 /*
     * 在一个有序数组中，找某个数是否存在
     */
    public static boolean Exist(int arr[], int num){
        if (arr == null || arr.length == 0){
            return false;
        }
        int L = 0;
        int R = arr.length-1;
        int mid = 0;
        while (L < R){
            mid = L + ((R - L) >> 1);
            if (num < arr[mid]){
                R = mid-1;
            }else if (num > arr[mid]){
                L = mid + 1;
            }else {
                return true;
            }
        }
        //比到最后，剩下了一个数L或R，都可以，这个时候L和R重合了，直接比较即可
        return arr[L] == num;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.在一个有序数组中，找>=某个数最左侧的位置

/*
    在一个有序数组中，找>=某个数最左侧的位置
    定义了一个标记位
    * */
    public static int Exist1(int arr[], int num){

        int L = 0;
        int R = arr.length - 1;
        int mid = 0;
        int index = -1;
        while (L < R){
            mid = L + ((R - L) >> 1);
            if (arr[mid] >= num){
                index = mid; //标记一下
                R = mid - 1; //再去左边找有没有符合情况的数
            }else {
                L = mid + 1;
            }
        }
        return index;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.局部最小值问题

局部最小值问题==在一个数组中，无语，任何两个相邻的数不相等，求一个局部最小，要求算法时间复杂度优于O(N)

嘻嘻~说明无序也可以二分哦
局部最优值:
    局部最小存在的几种情况，
      1. 长度为1，arr[0]就是局部最小；
      2. 数组的开头，如果arr[0] < arr[1] ，arr[0]被定义为局部最小。
      3. 数组的结尾，如果arr[N-1] < arr[N-2] ，arr[N-1]被定义为局部最小。
      4. 所以剩下就是数组下标1~N-2之间的了。再按arr[i-1] < arr[i] <arr[i+1] 找到一个局部最小。
  题目最后要求返回任意一个。
  假如你顺序的去搜索，去找一个比左小比右小的数，那么你的时间复杂度为O(N),比如单调递减的数组，搜索到最后一个。
  使用二分搜索，就能达到O(logN).
1
2
3
4
5
6
7
8
9
10
11
12

 public static int Exist2(int arr[]){
        if (arr == null ||arr.length == 0){
            return -1; //空数组
        }
        if (arr.length == 1 || arr[0] < arr[1]){
            return 0;
        }//第一种情况，长度为1，则arr[0]就是局部最小;和第二种情况一起写
        if (arr[arr.length - 1] < arr[arr.length - 2]){
            return arr.length - 1;//第三种情况
        }

        int L = 1;
        int R = arr.length - 2;
        int mid = 0;
        while (L < R){
            mid = L + ((R-L) >> 1);
            if (arr[mid] > arr[mid - 1]){ //在mid的左边呈下降趋势
                R = mid - 1;
            }else if (arr[mid] > arr[mid + 1]){
                L = mid+1;
            }else {
                return mid;
            }
        }
        return L;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

4.趁热打铁==力扣162. 寻找峰值

峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
示例 1: 输入:nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。
示例 2: 输入:nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。

说明: 你的解法应该是 O(logN) 时间复杂度的。
1
2
3
4
5
6
7
8
9
10
11
12
13

public static int MaxIndex(int arr[]){
        if (arr == null || arr.length == 0){
            return -1;
        }
        int L = 0;
        int R = arr.length-1;
        int mid = 0;
        while (L < R){
            mid = L + ((R-L) >> 1);
            if (arr[mid] < arr[mid + 1]){
                L = mid+1;
            }else {
                R = mid;
            }
        }
        return L;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

六、异或运算与拓展

1. 异或===无进位运算

    异或运算的性质
    1）0^N == N    N^N == 0
    2）异或运算满足交换律和结合率
1
2
3

2. 异或拓展

1）不用额外变量交换两个数
1

 arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
1
2
3

2）一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数
1

 //一堆数中，其它数有偶数个，一个数有奇数个，
    public static void printOddTimesNum(int [] arr){
        int ero = 0;
        for (int ch : arr){
            //每次异或如果相同的就成0，最后剩下的奇数和0异或就是它本身
            ero ^= ch;
        }
        System.out.println(ero);
    }
1
2
3
4
5
6
7
8
9

3）一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数
1

 //一堆数中，其它有偶数个，两个数有奇数个
    public static void printOddTimesNum1(int [] arr){
        int ero = 0;
        for (int ch : arr){
            ero ^= ch;
        }
        //此时ero = a^b（a和b为那两个奇数
        //ero != 0
        //ero位置上必然有一个是1
        int rightOne = ero & (~ero + 1);//取出最右的1

        int ero1 = 0;
        for (int ch1 : arr){
            if ((ch1 & rightOne) == 0){
                ero1 ^= ch1;
            }
        }
        System.out.println(ero1+" "+(ero1^ero));

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

七、递归行为和时间复杂度的估算

1. 用递归方法找一个数组中的最大值

public static int process(int arr[],int L, int R){
        if (L == R){
            return arr[L];
        }
        int mid = L + ((R - L)>>1);
        int leftMax = process(arr,L,mid);
        int rightMax = process(arr,mid+1,R);
        return Math.max(leftMax,rightMax);
    }
1
2
3
4
5
6
7
8
9

2. master公式的使用===子问题规模一样的时候

  **T(n) = a * T(N / b) + O(n ^ d)**
  a表此调用几次，b表示子问题规模，O(n^d)表示其他任务的时间复杂度
  1) log(b,a) > d -> 复杂度为O(N^log(b,a)) 
  2) log(b,a) = d -> 复杂度为O(N^d * logN) 
  3) log(b,a) < d -> 复杂度为O(N^d)
  补充阅读：[补充阅读](http://www.gocalf.com/blog/algorithm-complexity-and-master-%20theorem.html)
1
2
3
4
5
6