JS数据结构与算法-快速排序与二分查找算法

1. 快速排序
   快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法通过不断重复这个步骤知道所有数据都是有序的。

• 算法实现
  这个算法首先要在列表中选择一个元素作为基准值（pivot）。数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部（左边），将大于基准值的元素移到数组的顶部（右边）。

  ①选择一个基准元素，将列表分成两个子序列；
  ②对列表重新排序，将所有小于基准值的元素放在基准值前面，所有大于基准值的元素放在基准值的后面；
  ③分别对较小的元素的子序列和较大元素的子序列重复步骤①和步骤②。

function qSort(list) {
    //检查数组的长度是否为0，是则不需要任何排序，返回空数组
    if(list.length == 0) {
        return [];
    }
    //创建两个数组，一个用来存放比基准小的元素，另一个存放比基准值大的元素
    var left = [];
    var right = [];
    //基准值取自数组的第一个元素
    var pivot = list[0];
    //遍历数组，根据它们与基准值的关系放到合适的数组中
    for(var i=1;i<list.length;i++) {
        if(list[i] < pivot) {
            left.push(list[i]);
        }else{
            right.push(list[i]);
        }
    }
    //然后对于较小的数组和较大的数组分别递归调用这个函数
    return qSort(left).concat(pivot,qSort(right));
}

var test = [4,3,5,1,2];

console.log(qSort(test)); //[1,2,3,4,5]

ps：递归的过程大概是这样

灵魂画手

2. 二分法算法
   如果你要查找的数据是有序的，二分查找算法比顺序查找算法更高效。

• 算法理解
  二分搜索算法的原理和猜数字游戏类似，就是那个有人说“我正想着一个1到100的数字”的游戏。我们每回应一个数字，那个人就会说这个数字是高了、低了还是对了。

• 算法描述
  ①选择中间值；
  ②如果选择的值是待搜索的值，算法结束并返回；
  ③如果待搜索值比选中值要小，则返回步骤①并在选中值左边的子数组中寻找。
  ④如果待搜索值比选中值要大，则返回步骤①并在选中值右边的子数组中寻找。

• 算法实现

function binSearch(arr,data) {
    //将传入的数组用快速排序算法排序一下
    var arr = qSort(arr);
    //将最后一个元素所在的位置设为上边界
    var upperBound = arr.length-1;
    //将数组的第一个位置设为下边界
    var lowerBound = 0;

    while(lowerBound <= upperBound) {
        //中点
        var mid = Math.floor((upperBound + lowerBound)/2);
        //如果待查询的值大于中点元素，则将下边界设置为中点元素所在下标加1，也就是选取数组的右半边(不包括中点元素)，然后再在里面查找
        if(arr[mid] < data) {
            lowerBound = mid+1;
        //如果待查询的值小于中点元素，同理如上
        }else if(arr[mid] > data) {
            upperBound = mid-1;
        //否则如果相等，返回
        }else {
            return mid;
        }
    }
    return -1;
}

var test = [1,2,3,4,5,6];
console.log(binSearch(test,2)); //位置"1"

执行步骤：

执行步骤.png

参考学习：

《数据结构与算法javascript描述》
《学习javascript数据结构与算法》