JS如何实现排序和搜索算法

归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一 个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。因此需要用到递归

核心：归并排序，拆分成左右两块数组，分别排序后合并

动图：

注意：递归中最小的左右数组比较为单个元素的数组，因此在较上层多个元素对比时，左右两个数组一定是顺序的

代码：

function mergeSort(arr) {
 const len = arr.length;

 if (len < 2) return arr; // 递归的终止条件
 const middle = Math.floor(len / 2); // 拆分左右数组
 const left = arr.slice(0, middle);
 const right = arr.slice(middle);
 
 return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) { // 将左右两侧比较后进行合并
 const ret = [];

 while (left.length && right.length) {
 if (left[0] > right[0]) {
 ret.push(right.shift());
 } else {
 ret.push(left.shift());
 }
 }

 while (left.length) {
 ret.push(left.shift());
 }
 while (right.length) {
 ret.push(right.shift());
 }

 return ret;
}

2.5 快速排序

快速排序也许是最常用的排序算法了。它的复杂度为O(nlogn)，且它的性能通常比其他的复 杂度为O(nlogn)的排序算法要好。和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组

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

动图：

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

代码：

function quickSort(arr, left = 0, right = arr.length - 1) {
 // left和right默认为数组首尾
 if (left < right) {
 let partitionIndex = 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表示法

大O表示法用于描述算法的性能和复杂程度。分析算法时，时常遇到一下几类函数

（1）O(1)

function increment(num){
 return ++num;
}

执行时间和参数无关。因此说，上述函数的复杂度是O(1)(常数)

（2）O(n)

以顺序搜索函数为例，查找元素需要遍历整个数组，直到找到该元素停止。函数执行的总开销取决于数组元素的个数(数组大小)，而且也和搜索的值有关。但是函数复杂度取决于最坏的情况：如果数组大小是10，开销就是10；如果数组大小是1000，开销就是1000。这种函数的时间复杂度是O(n)，n是(输入)数组的大小

（3）O(n2)

以冒泡排序为例，在未优化的情况下，每次排序均需进行n*n次执行。时间复杂度为O(n2)

4.2 时间复杂度比较

（1）常用数据结构时间复杂度

（2）排序算法时间复杂度

相关视频教程推荐：《JavaScript教程》