【待续】面试算法笔记 | L1排序总结

一、简单排序

• 1.定义：每次选取最小的数放在待排序数组的首位置，然后后面的数组继续排，知道待排序数组的元素为0。
• 2.图解：
  
• 3.代码：

void selectSort(int[] arr){
   if(arr.size == 0|| arr.size() < 2)
      return;
   for(int i = 0; i< arr.size()-1; i++){
     int minIndex = i;
     for(int j = i+1; j<arr.size(); j++){
       minIndex = arr[j] < arr[minIndex]? j：minIndex; 
     }
     swap(arr,minIndex,i);
   }

二、冒泡排序

• 1.定义：从左往右（或从右往左）比较相邻两个元素的大小，将小的元素放在左边，直到比较到最后一个数结束一次冒泡，此时当前位置的元素为该待排序序列的最小值。以此类推，进行n次。
• 2.图解：

• 3.代码

void bubbleSort(int[] arr){
      if(arr.size() == 0 || arr.size() <2)
         return;
      for(int i = arr.size()-1;i>=0;i--){
         for(int j = 0 ; j<i ; j++){
           if(arr[i]>arr[i+1]){
              swap(arr,i,i+1);
           }
         }
      }
}

三、谈谈异或（^）

• 1.规则：相同为0，不同为1，且满足结合律和交换律，也就是a异或b异或c = b异或a异或c 以及 （a+b）异或 c = a异或c + b异或c
• 2.题目一：一种数出现了奇数次，其他数出现了偶数次，求这个出现奇数次的数？
• 3.题目一思路：全部异或，相同全变为0，0与奇数次数异或为它本身。
• 4.题目二：有两种数出现了奇数次，其他数出现了偶数次，求这个两个出现奇数次的数？
• 5.题目二思路：全部异或，此时得到的是两个出现奇数次的数异或的结果，而且异或的结果必有一位是1（转换为2进制表示），另一个数该位置为0，然后可以将原来的数组根据这一位是否为1划分为两个数组，然后分别异或，即可得到两个数。
• 6.题目二代码：

void qiShu2(int[] arr){
  int onlyOne1,onlyOne2, eor = 0;
  
  for(int i : arr) {
     eor ^= i;
  }

  int rightOne = eor & (~eor + 1); //提取最右边的1

  for(int cur : arr){
    if ((cur & rightOne) == 0){
        onlyOne1 ^= cur;   //得到指定位置不为1的数的值
    }
  }
  onlyOne2 = eor ^ onlyOne1;
}

四、插入排序

• 1.定义：第一次排序，保证数组 0——1 的数有序，第二次排序，保证数组 0——2范围上的数有序，以此类推，直到 0——n范围上的数有序

• 2.图解：
  

• 3.代码：

void insertSort(int[] arr){
  if(arr.size() ==0 || arr.size() < 2)
    return;
  for(int i = 0;i<arr.size()-1;i++){
    for(int j = i; j>=0 && arr[j] > arr[j+1]; j--){
      swap(arr,j,j+1)
    }
  }
}