常数操作
跟数据量无关的，是一个固定时间的东西，和数据量有关的就不是常数操作

比如数组的寻址，和数据量没有关系，只想找到i位置的数

加减乘除，位运算都是常数操作

对于链表来说这不是一个常数操作，对于单链表只能从左到右的一个一个去找

选择排序

遍历一下找到最小值，并记录下来，并与（0）位置处的值交换

第一次：对数组中的n个元素分别看一眼，看到的每个数都要与之前找到的最小值进行比较，直到看完找到最小的，放在索引为0的位置处，需要看n眼，比较n-1次，交换一次

第二次：对数组中的n-1个元素分别看一眼，看到的每个数都要与之前找到的最小值进行比较,知道找到最小的，放在索引为1的位置处，需要看n-1眼，比较n-2次，交换一次

最终找的区间会被压缩

找到最小的数，次小的数，次次小的数，以此类推，这样最终就会将数组排好序，效率很低下

O(n)

以n为上限

小数据量，大数据量

代码

public class Code01_SelectionSort {
    public static void selectionSort(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

异或运算

异或运算就是观察二进制位中一的个数是奇数还是偶数

奇数为1偶数为0

异或运算可以理解为无进位相加，位是二进制位

异或运算，满足交换律和结合律，所以对于异或操作来说，对数异或的顺序无关，最总只会得到一个数

例如一个数组中的元素为 8 7 3 6 3 6 7 8 2 1 1 2 3 让一个0 来异或这个数组中的所有元素最终的结果是3 因为数组里面的元素可以看成 1 1 2 2 3 3 3 6 6 7 7 8 8，其中奇数次的数只有3其余的在异或的时候都会变成0

题目：一个数组中有一个数出现奇数次，其余的都出现偶数次，找出这个出现奇数次的数字

题目：一个数组中有两个数字出现奇数次，其余的都出现偶数次，找出这两个出现奇数次的数字

插入排序On^2）

算法的时间复杂度一律按照最差的时间来估计

插入排序是让0~0 ,0~1，0~2，0~3 .....0~n范围的数字依次有序，他与数据状况有关系，像选择排序，是在0~n,1~n,2~n....找到最小的数字放在 0,1,2...n处，它与数据量无关，（原始数据的状况，无法影响流程的进行），冒泡排序也与数据量无关

插入排序和数据量有关，我们让0-i处数字有序，而0~i-1处的数字已经有序了，所以只要判断i处元素的位置就行

ublic class Code04_InsertionSort {
    public static void InsertionSort(int[] arr){
        if(arr==null || arr.length<2) {
            return;
        }
        //0~0处的数字已经有序
        //让0~i处的数字有序
            for(int i=1;i=0&&arr[j]>arr[j+1];j--){//0——i-1处的数字已经有序
                    swap(arr,j,j+1);
            }
        }
    }
    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];
    }
}

算法流程按照时间复杂度最差的来估计，插入排序在好的时间复杂度为O(n)即，都是有序的，就都看一眼，而最差的是O（n^2）都是无序的

二分查找

package com;

public class Code05_Search {
    public static  boolean search(int[] sortArr,int num){
        if(sortArr==null||sortArr.length==0){
            return false;
        }
        int l=0;
        int r=sortArr.length-1;
        while(l>1);
            if(sortArr[mid]==num){
                return true;
            }else if(sortArr[mid]>num){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return sortArr[l]==num;//最后结束是r和l指向的是同一个数
    }
}

二分查找大多数适用于在一个有序的数组中查某个数是否存在，或者查找大于等于一个数最右边的数字的位置，或小于等于一个数最右边的数字的位置，或局部最小值问题。时间复杂度是O(lg2n)n是数组中的元素个数，假设数组中有16个元素，最好的情况就是第一次二分就找到了，此时的复杂度是O(1)，最差的是二分了4次，时间复杂度为O(4)

假设要找的数字设为num，当中间元素x>num的时候，由于数组是有序的，那么x右边的数字都大于num，所以我们可以砍一半，在x的左边继续二分。如果第二次二分的时候，x2

二分查找也可以用于无序

局部最小问题

相邻两个数不相等，就一定会在存在在整个数组上值的变化波动曲线

那么0-n-1处必定存在局部最小值

数据结构和算法（1）写的有些乱这个系列只是给自己看的

Java相关栏目本月热门文章