入门算法-二分查找，二分排序，插入排序，冒泡排序

1.二分查找（时间复杂度O(lgn)）

二分查找，需要将业务模拟一个有序数组。然后查找某个值在该数组中的位置。

二分查找的关键是：

1）查找的值一定在某次的范围中间。即使值是最后一个，也要按照二分法的规则去查找。

2）有左右边界的查找范围作为一个循环不变式

function bsearch(A, x) { // A 是有序升数组；x是待查值; 结果要返回x在A中的位置
   // 循环不变式
   let l = 0,r = A.length-1, guess;
   while(l <= r) {
      guess = Math.floor((l+r)/2);
      if (A[guess] === x) {
         return guess;
      } else if (A[guess] > x) {
         r = guess - 1;
      } else {
         l = guess + 1;
      }
   }
   return -1; // 没找到
}

2. 二分排序

 // 主循环执行N-1次（N代表输入的数据长度）
function insertion_sort(A) { // 对无序数组A进行排列，排列时用到插入排序
    for (let i = 1; i < A.length; i++) { // 每次循环排序前i项，第一项默认已经排序，所以从i=1开始
        bSearch(A, i, A[i]);
    }   
}
function bSearch(A, i, x) {
    let l = 0, r = i -1, guess;
    while(l<=r) {
        guess = Math.floor((l+r)/2);
        if (A[guess] === x) {
            r = guess;
        } else if (A[guess] > x) {
            r = guess - 1;
        } else {
            l = guess + 1;
        }
    }
    for (let j = i; j > r; j--) {
        A[j] = A[j-1];
    }
    A[r+1] = x;
}

3. 插入排序（原址排序）

时间复杂度：最坏: Θ(n**2); 平均O(n**2)

子问题：在一个有序数组中插入一个新值，即插入第一个比待插数要大的值前面。

第一反应是用js实现

function jsInsert(A, x) { // A是有序数组，x是待插入值
   const index = A.findIndex(i => i > x); // index第一个比x大的值
   const insertIndex = index > -1 ? index : A.length;
   A.splice(insertIndex, 0, x);
}

考虑实现同样的问题，使用插入排序算法（从最大值开始比较）

 function insert(A, x) {// A是有序数组，x是待插入值
    let p = A.length - 1; // p代表下一个要比较的值所在的位置, p+1留空
    while(p>=0 && A[p] > x) { // 如果最后一个值大于x,则将最后一个值后移，原来的位置先保持原状
       A[p+1] = A[p];
       p--; // 下一个要比较的值的位置
    }
    A[p+1] = x;
 }

插入排序：对无序数组进行排序。

分为两步： 1）默认第一个值是已排序状态。

2）将待排的下一个值插入已经排序的位置。循环不变式。

function insert(A, i, x) {// A和i可以定位已排序的数组, i可以表示已排序数组的长度
   //运行次数按照最坏的计算是1+2+3....+N = (N**2)/2 - N/2

    let p = i - 1; // p指向下一个需要比较的值，i - 1是已排序数组的最后一个值的位置
    while(p >= 0 && A[p] > x) {
        A[p+1] = A[p]
        p--;
    }
    A[p+1] = x;
 }

function insertion_sort(A) { // 对无序数组A进行排列，排列时用到插入排序
    for (let i = 1; i < A.length; i++) { // 每次循环排序前i项，第一项默认已经排序，所以从i=1开始
        insert(A, i, A[i]); //i想当于已经排序数组的长度。 A[i]从A[1]开始，即从第二项插入第一项组成的数组开始
    }   
}

4. 冒泡排序(Bubble sort)/下沉排序(Sinking sort)-原址排序

复杂度和插入排序相同

每次冒泡通过遍历两两比较（交换或者不交换N-1），排出一个最大值；第二次遍历N-1的数组;.....，一共遍历N-1次。

由描述可知，分为内存循环和外层循环

function bubble_sort(A) {
    for(let i = A.length - 1; i >= 1; i--) { // i初始值表示第一次冒泡循环结束的指向，i>=1表示只有一项的时候不需要冒泡
        for (let j = 1; j<=i; j++) { // 冒泡从第二项开始比较，直到比较到数组最后一位
            if (A[j-1] > A[j]) { 
                swap(A,j-1,j)
            }
        }
    }
}
function swap(A,i,j) {
    var temp;
    temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}