首页 > 编程语言 > 详细

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

时间:2019-09-17 00:06:18      阅读:116      评论:0      收藏:0      [点我收藏+]

1.二分查找(nlogn)

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

二分查找的关键是:

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

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

function bsearch(A, x) { // A 是有序升数组;x是待查值; 结果要返回x在A中的位置
   // 循环不变式
   let l = 0,r = A.length-1, guess;
   while(i <= 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)

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

第一反应是用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(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]); // 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--) { // 外层循环遍历N-1次
        for (let j = 0; j<i; j++) { // 内层循环遍历交换N-1次。
            if (A[j] > A[j+1]) { 
                swap(A,j,j+1)
            }
        }
    }
}
function swap(A,i,j) {
    var temp;
    temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

 

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

原文:https://www.cnblogs.com/lyraLee/p/11530827.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!