选择排序

当 i ∈[0,n] 时，找出最小值，然后跟首位交换位置；
当 i ∈[1,n] 时，找出最小值，然后跟首位交换位置；
以此类推。
….
每次都找出最小值，然后跟首位交换位置，最后只要交换 n-1 次位置。
时间复杂度：O(n2)
空间复杂度：O(1)

输入： 5 5 4 3 2 1

输出： 1 2 3 4 5

  1. // 处理数据
  2. const len = parseInt(readline());
  3. const nums = readline().split(" ");
  4. let a, b, minIndex;
  6. // 重点代码
  7. for(let i=0; i<len-1; i++){
  8.     minIndex = i;
  9.     for(let j=i+1; j<len; j++){
  10.           b = parseInt(nums[j]);
  11.         minIndex = b <= parseInt(nums[minIndex]) ? j : minIndex;
  12.      }
  13.     swap(nums,minIndex,i);
  14. }
  16. print(nums.join(" "));
  18. // 交换数据
  19. function swap(nums,i,j){
  20.     const tmp = nums[i];
  21.     nums[i] = nums[j];
  22.     nums[j] = tmp;
  23. }

冒泡排序

在 i ∈[0,n] 之间，两两比较，大的放在后面那一位，最后最大的在最后一个位置；
在 i∈[0,n-1] 之间，重复上面操作，倒数第二大的会在倒数第二个位置；
以此类推。
…
每次都两两比较，找出较大的数放在后一位，最后最大的数就会在数组区间的最后一位。
每次最多进行 n-1 次交换位置。
时间复杂度：O(n2)
空间复杂度：O(1)

输入： 5 5 4 3 2 1

输出： 1 2 3 4 5

  1. // 处理数据
  2. const len = parseInt(readline());
  3. const nums = readline().split(" ");
  4. let a, b;
  6. //重点代码
  7. for(let e=len-1; e>0; e--){
  8.     for(let i=0; i<e; i++){
  9.           a = parseInt(nums[i]);
  10.           b = parseInt(nums[i+1]);
  11.         if(a>b){
  12.             swap(nums,i,i+1);
  13.             }
  14.          }
  15. }
  17. print(nums.join(" "));
  19. // 交换数据
  20. function swap(nums,i,j){
  21.     const tmp = nums[i];
  22.     nums[i] = nums[j];
  23.     nums[j] = tmp;
  24. }

插入排序

依次做到 [0,i] 上有序，即：
[0,0] 一定有序；
[0,1] 做到有序； ====> 从后往前比较大小，前比后大，交换位置
[0,2] 做到有序；
……
[0,i] 做到有序。

临界条件：
nums[j] > nums[j+1] // 前比后大
j >= 0

时间复杂度：O(N²)
空间复杂度：O(1)

输入： 4 4 3 2 1 输出： 1 2 3 4

  1. const len = parseInt(readline());
  2. const numStr = readline().split(" ");
  3. const nums = [];
  4. for(let i=0; i<len; i++){
  5.     nums[i] = parseInt(numStr[i]);
  6. }
  8. // 重点代码
  9. for(let i=1; i<len; i++){
  10.     for(let j=i-1; j>=0 && nums[j]>nums[j+1]; j--){
  11.         swap(nums,j,j+1);
  12.     }
  13. }
  16. print(nums.join(" "));
  17. function swap(nums,i,j){
  18.     const tmp = nums[i];
  19.     nums[i] = nums[j];
  20.     nums[j] = tmp;
  21. }

二分查找

详解与扩展：

  1. 在一个有序数组中，找某个数字是否存在；
  2. 在一个有序数组中，找>=某个数最左侧/某个数的最右侧位置；
  3. 局部最小值问题；

以上三种情况，都可以使用二分查找。

  1. 有序数组 + 找某个数

    1. const msg = readline().split(" ");
    2. const len = parseInt(msg[0]);
    3. const k = parseInt(msg[1]);
    4. const nums = readline().split(" ");
    5. let left = 0, right = len-1, mid, midNum, flag = -1;
    6. while(left <= right){
    7.  mid = left + Math.floor((right - left)/2);        
    8.  midNum = parseInt(nums[mid])                     
    9.  if(midNum === k){
    10.      flag = mid;
    11.      break;
    12.  }
    13.  if(midNum > k){
    14.      right = mid - 1;                              
    15.  }else{
    16.      left = mid + 1;                            
    17.  }
    18. }
    19. print(flag);

  2. 有序数组 + 找>=某个数的最左侧 / 找<=某个数的最右侧 ```javascript const msg = readline().split(“ “); const len = parseInt(msg[0]); const k = parseInt(msg[1]); const nums = readline().split(“ “);

let left=0, right=len-1, mid, midNum, flag = -1; while(left <= right){ mid = left + Math.floor((right-left)/2);
midNum = parseInt(nums[mid]); if(midNum >= k){ // 这里只需要记录中间值，如果找到更左符合情况的，会更新 flag = mid; right = mid - 1; }else{ left = mid + 1; } } print(flag);

  2. 3. 局部最小
  3. ```javascript
  4. const len = parseInt(readline());
  5. const nums = readline().split(" ");
  6. partMin(nums,len);
  7. function partMin(arr,len){
  8.       // 只有一个数 和 局部最小是第一个数的情况
  9.     if(len === 1 || nums[0] < nums[1]){
  10.         print(0);
  11.         return;
  12.     }
  13.     // 局部最小是最后一个数的情况
  14.     if(nums[len-2]>nums[len-1]){
  15.         print(len-1);
  16.         return;
  17.     }
  18.     // 在中间的情况
  19.     let left=0, right=len-1, mid, flag , midNum, midNum1, midNum2;
  20.     while(left <= right){
  21.         mid = left + Math.floor((right-left)/2);
  22.         midNum = parseInt(arr[mid]);
  23.         midNum1 = parseInt(arr[mid-1]);
  24.         midNum2 = parseInt(arr[mid+1]);
  25.         if(midNum1 > midNum && midNum < midNum2){
  26.             flag = mid;
  27.             break;
  28.         }else if(midNum >= midNum1){
  29.             right = mid;
  30.         }else{
  31.             left = mid;
  32.         }
  33.     }
  34.     print(flag);
  35. }

异或运算

无进位相加，我们之前记的是，同为相加为0，异位相加为1，不好记。直接同位相加，如果有进位的情况，舍弃。
性质与扩展
性质

  1. 2. 简单排序 - 图1，0跟任何一个数异或，都是任何数。
  2. 2. 简单排序 - 图2，任何数跟任何数异或，都为0.
  3. 异或运算满足交换律和结合律

2. 简单排序 - 图3 2. 简单排序 - 图4
扩展

  1. 不用额外变量交换两个数
  2. 一个数组中只有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这个数
  3. 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数
    1. // 交换位置
    2. let a = 甲, b = 乙;
    3. a = a^b;    // a = 甲^乙, b = 乙
    4. b = a^b;  // a = 甲^乙, b = 甲^乙^乙 = 甲^(乙^乙=0) = 甲
    5. a = a^b;  // a = 甲^乙^甲 = 乙, b = 甲
    ```javascript // 一种数出现了奇数次，其他数出现了偶数次，找到这个数 /* 找出 eor，所谓 eor 就是所有数的异或完最后的结果 如： 1 2 3 1 1 1 2 3 5 3 5 3 5 奇数次：5
    1.                    1^2^3^1^1^1^2^3^5^3^5^3^5
    最后会变成： 1^1^1^1^2^2^3^3^3^3^5^5^5
    然后，偶数次的数字相乘会相乘： 0^0…^5 => 5 */

const len = parseInt(readline()); const nums = readline().split(“ “); let i = 1, tmp, eor = parseInt(nums[0]); while(i<len){ tmp = parseInt(nums[i]); eor ^= tmp; i++; } print(eor);

  1. ```javascript
  2. // 两种数出现了奇数次，其他偶数次
  3. /*
  4.     找出 eor ，这时的 eor 的值  => eor = a^b
  5.   我们可以知道，a 跟 b肯定不相同，所以二进制的a跟b中肯定有一位是不一样的！！
  6.   怎么找到其中一位呢？
  7.   我们通过 eor 最右为1就可以知道，
  8.   我们假设第四位不同，那么第四位肯定为1，假设a为1，b为0。
  9.   我们通过 eor' = eor & (~eor+1) 就可以把那一位找出来
  10.   找出来之后所有数跟它单独与运算（有相同的一位），找出来所有数中那一位相同的数，
  11.   然后再进行异或运算，那些偶数的就会被异或掉，然后就可以把a和b中那个为1的找出来，即a
  12.   然后再将 eor^a 就可以获取b的结果，eor = a^b^a = b
  14.   把eor中最右位为1的找出来的方法：
  15.   我们假设：eor = 01101101010000
  16.                   ~eor = 10010010101111
  17.          ~eor+1= 10010010110000
  18.          ----------------------------
  19.           & eor'= 00000000010000
  20. */
  22. const len = parseInt(readline());
  23. const nums = readline().split(" ");
  24. let i=0, eor = 0, eorp=0, a=0, b=0;
  25. while(i<len){
  26.     eor ^= parseInt(nums[i]);
  27.     i++;
  28. }
  29. eorp = eor & (~eor + 1);
  30. i = 0;
  31. while(i<len){
  32.     if((parseInt(nums[i]) & eorp) !== 0){
  33.         a ^= parseInt(nums[i]);
  34.     }
  35.     i++;
  36. }
  37. b = eor ^ a;
  38. const str = a < b ? a + " " + b : b + " " + a;
  39. print(str);

对数器

测试自己的代码写对了没有。
生成随机样本（大量），然后由A跑出一个结果，B（能写出来，暴力）也跑一个结果，如果结果都一样，那么A方法大概率是对的。
步骤：

  1. 定义跑的次数，随机数组的长度，随机数组的最大值、最小值。
  2. 随机生成数组
  3. 在自己代码上跑一边
  4. 在对数器中跑一边
  5. 比较跑完是否一致，不一致暂停，一致就输出成功 ```javascript

// 对数器,一种必对的方法(但可能出错)，暴力解法… function comparator(arr) { arr.sort((a,b)=>a-b); }

// 验证方法 function test() { const testTime = 500000; // 测试的次数 const maxSize = 100; // 最大的长度 const maxValue = 100; // 最大值 let succeed = true; // 标记是否成功 // 遍历生成的数组，看与对数器比较是否相同，大量相同就可以判断几乎是对的了 for (let i = 0; i < testTime; i++) { // 随机生成一个数组 const arr1 = generateRandomArray(maxSize,maxValue); // copy一个arr2数组 const arr2 = […arr1]; // 自己写的方法 selectSort(arr1); // 必对的方法 comparator(arr2); // 判断两个结果是否相同,如果不相同就输出,并标记为失败 if(!isEqual(arr1,arr2)){ succeed = false; console.log(i); printArray(arr1); printArray(arr2); break; } } console.log(succeed ? ‘Nice!’ : ‘Shit!’);

}

// 随机生成数组 function generateRandomArray(maxSize,maxValue) { // Math.random() // Math.random()A => [0,A) float A=> int // Math.floor(Math.random()A) => [0,A-1] int

  1. // 生成一个随机长度的数组
  2. const arr = new Array(Math.floor((maxSize+1)*Math.random()));
  3. const len = arr.length;
  4. for (let i = 0; i < len; i++) {
  5.     arr[i] = Math.floor((maxValue+1)*Math.random() - Math.floor(maxValue*Math.random()));
  6. }
  7. return arr;

}

// 判断是否相等 function isEqual(arr1,arr2) { const len = arr1.length; for (let i = 0; i < len; i++) { if(arr1[i] !== arr2[i]){ return false; }
} return true; }

// 自己写的方法,自己放选择排序 function selectSort(arr) { const len = arr.length; for (let i = 0; i < len; i++) { for (let j = i+1; j < len; j++) { if(arr[i] > arr[j]){ swap(arr,i,j); } }
} }

// 交换位置 function swap(arr1,p1,p2) { arr1[p1] = arr1[p1]^arr1[p2]; arr1[p2] = arr1[p1]^arr1[p2]; arr1[p1] = arr1[p1]^arr1[p2]; }

// 输出数组 function printArray(arr) { console.log(arr); }

test(); ```