时间复杂度O

常数时间的操作

一个操作如果和样本数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。

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

在表达式中，只要高阶项，不要低阶项，也不要高阶的系数，剩下的部分如果为f(N)，那么时间复杂度为O(f（N)）。
评价一个算法流程的好坏，先看时间复杂度的指标，然后在分拆不同数据样本下的实际运行时间，也就是“常数项时间”。

简单排序算法

选择排序、冒泡排序细节的讲解与复杂度分析（稳定）

时间复杂度O（N^2）,额外空间复杂度O（1）

选择排序源码分析：（Java）

public class Code01_SelectionSort {
    //测试函数
    public static void main(String[] args){
        int arr[] = {3,1,2,6,7,8};
        System.out.print("排序前：");
        for (int a : arr)
            System.out.print(a);
        selectionSoet(arr);
        System.out.print("\n排序后：");
        for (int a : arr)
            System.out.print(a);
    }
    //选择排序算法
    public static  void  selectionSoet(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        for (int i = 0;i < arr.length - 1; i++){ //i ~ N-1
            int minIndex = i;
            for(int j = i + 1; j < arr.length; j++){
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr,i,minIndex);
        }
    }
    //两数交换
    public static void swap(int[] arr,int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

冒泡排序源码分析：（Java）

public class Code02_BubbleSort {

    public static void main(String[] args){
        int arr[] = {3,1,2,6,7,8};
        System.out.print("排序前：");
        for (int a : arr)
            System.out.print(a);
        bubbleSort(arr);
        System.out.print("\n排序后：");
        for (int a : arr)
            System.out.print(a);
    }
    //冒泡排序算法
    public static void bubbleSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        for (int e = arr.length - 1; e > 0; e--){  //0 ~ e
            for(int i = 0; i< e ; i++){
                if(arr[i] > arr[i + 1]){
                    swap(arr, i, i+1);
                }
            }
        }
    }
    // 交换arr的i和j的值
    public static 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];
    }
}

异或运算（^）

1、0 ^ N = N
2、满足交换律、结合律

• a ^ b = b ^ a
• (a ^ b) ^ c = a ^ (b ^ c)

常见面试题（异或）

1. 一个数组中只有一种数出现奇数次，找出这一个数 {3,3,2,2,7,8,7}
2. 一个数组中只有两种数出现奇数次，找出这两个数{3,3,2,7,8,7,8,9,2,10}

异或题解源码实现（提示：偶数次的异或为0，0与任何数异或为任何数）

public class Code07_EvenTimesOddTimes {

    //一个数组里面只有一种数出现奇数次，剩下所有数均出现偶数次，找到这个奇数值
    public static void printOddTimesNum1(int[] arr){
        int eor = 0;
        for (int cur : arr){
            eor ^= cur;
        }
        System.out.println(eor);
    }


    //一个数组里只有两种数出现奇数次，找到这两个出现奇数次的数
    public static void printOddTimesNum2(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
        int onlyOne = 0; //eor'
        for(int cur : arr){
            if((cur & rightOne) == 0){
                onlyOne ^= cur;
            }
        }
        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }


    public static void main(String[] args){
        int arrOne[] = {3,3,2,2,7,8,7};
        int arrTwo[] = {3,3,2,7,8,7,8,9,2,10};
        System.out.print("只有一种数现奇数次：");
        printOddTimesNum1(arrOne);
        System.out.print("\n只有2种数现奇数次：");
        printOddTimesNum2(arrTwo);
    }
}

插入排序讲解与复杂度分析（不稳定）

时间复杂度O(N^2)，额外空间复杂度O（1）
算法流程按照最差情况来估计时间复杂度（某些数据状况的时间复杂度要优于选择排序和冒泡排序）

插入排序源码分析：（Java）

public class Code03_InsertionSort {
    public static  void insertionSort(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);
            }
        }
    }
    //i 和j是一个位置会出错
    public static 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];
    }
}