JS数据结构与算法_排序和搜索算法(3)

核心：分治算法，以参考值为界限，将比它小的和大的值拆开

注意：每一次遍历筛选出比基准点小的值

代码：

function quickSort(arr, left = 0, right = arr.length - 1) {  
  // left和right默认为数组首尾  
  if (left < right) {  
    let partitionpartitionIndex = partition(arr, left, right);  
    quickSort(arr, left, partitionIndex - 1);  
    quickSort(arr, partitionIndex + 1, right);  
  }  
  return arr;  
}  
function partition(arr, left, right) {  
  let pivot = left;  
  let index = left + 1; // 满足比较条件的依次放在分割点后  
  for (let i = index; i <= right; i += 1) {  
    if (arr[i] < arr[pivot]) {  
      swap(arr, i, index);  
      index += 1;  
    }  
  }  
  swap(arr, index - 1, pivot); // 交换顺序时，以最后一位替换分隔项  
  return index - 1;  
} 

三、搜索算法

3.1 顺序搜索

顺序或线性搜索是最基本的搜索算法。它的机制是，将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法。

function findItem(item, arr) {  
  for (let i = 0; i < arr.length; i += 1) {  
    if (item === arr[i]) {  
      return i;  
    }  
  }  
  return -1;  
} 

3.2 二分搜索

二分搜索要求被搜索的数据结构已排序。以下是该算法遵循的步骤：

1.     选择数组的中间值
2.     如果选中值是待搜索值，那么算法执行完毕
3.     如果待搜索值比选中值要小，则返回步骤1在选中值左边的子数组中寻找
4.     如果待搜索值比选中值要大，则返回步骤1在选中值右边的子数组中寻找 

function binarySearch(item, arr) {  
  arr = quickSort(arr); // 排序  
  let low = 0;  
  let high = arr.length - 1;  
  let mid;  
  while (low <= high) {  
    min = Math.floor((low + high) / 2);  
    if (arr[mid] < item) {  
      low = mid + 1;  
    } else if (arr[mid] > item) {  
      high = mid - 1;  
    } else {  
      return mid;  
    }  
  }  
  return -1;  
} 

四、算法复杂度

4.1 理解大O表示法

（编辑：ASP站长网）