Hexo
0%

简单排序

发表于 分类于

简单排序

选择排序

时间复杂度：O(N^2)

1
2
3
4
5
6
7
8
9
10
int minidx,temp;
for(int i=0;i<n;i++){
    minidx=i;
    for(int j=i;j<n;j++){
        if(arr[minidx]>arr[j]) minidx=j;
    }
    temp=arr[i];
    arr[i]=arr[minidx];
    arr[minidx]=temp;
}

冒泡排序

时间复杂度：O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
bool flag=0;//是否冒泡
for(int i=n-1;i>=0;i--){
    flag=0;
    for(int j=0;j<i;j++){
        if(arr[j]>arr[j+1]){
            temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;
            flag=1;
        }
    }
    if(!flag) break;
}

  • 异或：相同为0，不同为1 = 不进位相加

  • 性质：

    1. 0^N = N ;N^N = 0

    2. 满足交换律和结合律 a^b=b^a;a^b^c=a^(b^c)

      a=a^b;b=a^b;a=a^b;

      跑完的结果：a、b交换；前提：a和b在内存中是两块独立的空间，即a指向的内存 != b指向的内存

      eg:a[0]=a[0]^a[0];a[0]=a[0]^a[0];a[0]=a[0]^a[0];

      结果：a[0]变成0

  • 异或相关题目

    Q：在一个整型数组中，只有一个数出现了奇数次，其他数都出现了偶数次

    要求：时间复杂度O（N），空间复杂度O（1）：即使用有限几个变量

    1. 怎么找到这个这个出现了奇数次的数

      1
      2
      3
      4
      5
      //全部异或
      int answer=arr[0];
      for(int i=1;i<n;i++){
          answer=answer^arr[i];
      }

    2. 若只有两个数出现了奇数次呢

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      int temp=0;
      for(int i=0;i<n;i++){
          temp=temp^arr[i];
      }//temp=a^b!=0——>temp至少有一位是1
      int rightOne=temp&(~temp+1);//原码&补码得到最右侧的1

      int temp1=0;
      for(int i=0;i<n;i++){
          if((arr[i]&rightOne)==rightOne){//在某位上为1的才参加异或
              temp1=temp1^arr[i];
          }
      }
      int answer1=temp1;
      int answer2=temp^temp1;

      ps：int rightOne=temp&(~temp+1);//原码&补码得到最右侧的1

插入排序

思想：将新的数插到原来有序数组中合适的位置

1
2
3
4
5
6
7
8
9
int tmp;
for(int i=1;i<n;i++){
    //0~i-1为有序，0~i为想有序
    for(int j=i-1;j>=0&&arr[j]>arr[j+1];j--){
        tmp=arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=tmp;
    }
}

二分法

有序数组中找某个数是否存在

二分查找，时间复杂度 O（log N）

有序数组中找>=某个数最左侧的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
int aim=4;//找到大于等于3最左侧的索引
int low,mid,high,idx=n;//idx记录答案索引
low=0;high=n;
while(low<=high){
    mid=(low+high)/2;
    if(a[mid]<aim){
        low=mid+1;
    }
    else{
        if(mid<idx) idx=mid;
        high=mid-1;
    }
}

局部最小值问题

arr中，无序但任意相邻数不相等，求一个局部最小的位置，要求时间复杂度好于O（N）

局部最小def：0位置比1位置小 / n-1位置比n-2位置小 / i位置比i-1和i+1位置小

1
2
3
4
5
6
7
8
判断0位置和n-1位置是否为局部最小
若不存在，则0↘↙n-1，则0~n-1之间必存在局部最小 
判断中间位置是否为局部最小，
    若是则直接返回
    若不是，
    	if(m-1↗m↖m+1) 则左右侧都存在局部最小
        if(m-1↗m↗m+1) 则左侧一定存在局部最小
        if(m-1↘m↘m+1) 则右侧一定存在局部最小

所以，二分法不一定只能用于有序数组，取决于研究的问题