排序和查找

排序算法

排序算法没有优劣之分，在不同的场景中，不同的排序算法执行效率不同。

冒泡排序 Bubble Sort

一次冒泡排序，可以将某个区域序列的最大值排序到该区域的最后一位，具体的方式是：

将第 1 位和第 2 位比较，如果前者比后者大则交换
将第 2 位和第 3 位比较，如果前者比后者大则交换
依次类推，直到比较到该区域的最后两位
重复上述过程，直到序列排序完成

冒泡排序效率一般，在各种情况下不会太好，也不至于太差如果数组本身是比较有序的，冒泡排序还是不错的

function bubbleSort(list) {
 if (!Array.isArray(list)) return []
 for (let i = 0; i < list.length; i++) {
  for (let j = 0; j < list.length - i - 1; j++) {
   if (list[j] > list[j + 1]) {
    ;[list[j], list[j + 1]] = [list[j + 1], list[j]]
   }
  }
 }
 return list
}

const list = [5, 3, 2, 4, 6, 1, 7]
console.log(bubbleSort(list)) // [1, 2, 3, 4, 5, 6, 7]

插入排序 Insertion Sort

将序列分为两个部分，一部分是有序的，一部分是无序的，现在要做的是，就是不断的从无序的部分取出数据，加入到有序的部分，直到整个排序完成

例如：序列[5, 7, 2, 3, 6]

分为有序的序列和无序的序列 (5) (7 2 3 6)
不断的扩充有序序列 (5 7) (2 3 6)
不断的扩充有序序列 (2 5 7) (3 6)
不断的扩充有序序列 (2 3 5 7) (6)
不断的扩充有序序列 (2 3 5 6 7)
排序完成

插入排序在小规模的数组中效率很高，如果数组本身是比较有序的，则效率会进一步提升 V8 引擎在数组比较小的时候会使用插入排序

function insertSort(list) {
 if (!Array.isArray(list)) return []
 for (let i = 1; i < list.length; i++) {
  // 当前下标小于前面排好的右侧边界时才需要排序
  if (list[i] < list[i - 1]) {
   let temp = list[i]
   let j = i
   for (; j >= 0; j--) {
    if (j > 0 && temp < list[j - 1]) {
     list[j] = list[j - 1]
    } else {
     break
    }
   }
   list[j] = temp
  }
 }
 return list
}

const list = [5, 3, 2, 4, 6, 1, 7]
console.log(insertSort(list)) // [1, 2, 3, 4, 5, 6, 7]

快速排序 Quick Sort

选择一个数（比如序列的最后一位）作为基准数，将整个序列排序成两部分，一部分比该数小，另一部分比该数大，基准数在中间，然后对剩余的序列做同样的事情，直到排序完成

例如：序列[5, 7, 2, 3, 6, 4]

选择 4 作为基准数，排序成为：(3, 2) 4 (7, 6, 5)
对于 3,2，继续使用该方式排序，得到： (2, 3) 4 (7,6,5)
对于 7,6,5，继续使用该方式排序，得到： (2, 3) 4 (5,6,7)
排序完成

当数组比较大并且比较混乱的时候，使用快速排序效率很高 V8 引擎在数组较大时会自动使用快速排序

function quickSort(list) {
 if (!Array.isArray(list)) return []
 function _quickSort(left, right) {
  if (left < 0 || right >= list.length || left > right) return
  // 拿一个基准数
  let key = list[right]
  let low = left,
   high = right
  // 此循环结束后low === high
  while (low < high) {
   while (list[low] <= key && low < high) {
    low++
   }
   list[high] = list[low]
   while (list[high] >= key && low < high) {
    high--
   }
   list[low] = list[high]
  }
  // low === high，将基准值放到当前位置
  list[low] = key
  // 搞定左边
  _quickSort(0, low - 1)
  // 搞定右边
  _quickSort(low + 1, right)
 }
 _quickSort(0, list.length - 1)
 return list
}

const list = [5, 3, 2, 4, 6, 1, 7]
console.log(quickSort(list)) // [1, 2, 3, 4, 5, 6, 7]

归并 Merge Sort

归并排序的时间复杂度为O(logn)，因为利用到递归算法，火狐浏览器的排序就是利用的归并排序。

思路:
1. 分: 把数组劈成两半，再递归地对子数组进行“分”操作，直到分成一个个单独的数。
2. 合: 把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组。
3. 新建一个空数组res, 用于存放最终排序后的数组。
4. 比较两个有序数组的头部，较小者出队并推入res中。
5. 如果两个数组还有值，则重复第四步(递归)。

Array.prototype.mergeSort = function() {
  const dfs = (arr) => {
    const res = []
    if (arr.length === 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid, arr.length);
    const orderLeft = dfs(left);
    const orderRight = dfs(right);
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(orderLeft[0] < orderRight[0]? orderLeft.shift() : orderRight.shift())
      } else if (orderLeft.length) {
        res.push(orderLeft.shift())
      } else if (orderRight.length) {
        res.push(orderRight.shift())
      }
    }
    return res
  }
  const res  =  dfs(this)
  res.forEach((n ,i) => this[i] = n)
}

const arr = [6, 4, 7, 2, 5, 1]
arr.mergeSort()
console.log(arr)

查询算法

下面的例子均使用此数组：

const list = [1, 3, 4, 5, 6, 7, 8]

顺序查找 Inorder Search

即普通的遍历，属于算法的穷举法，没啥好解释的

// 顺序查找
function inorderSearch(list, target) {
 if (!Array.isArray(list) || !target) return false
 for (let i = 0; i < list.length; i++) {
  if (list[i] === target) return true
 }
 return false
}
console.log(inorderSearch(list, 5)) // true
console.log(inorderSearch(list, 0)) // false

二分查找 Binary Search

如果一个序列是一个排序好的序列，则使用二分查找可以极大的缩短查找时间

具体的做法是：

查找该序列中间未知的数据

相等，找到
要找的数据较大，则对后续部分的数据做同样的步骤
要找的数据较小，则对前面部分的数据做同样的步骤

// 二分查找
function binarySearch(list, target) {
 if (!Array.isArray(list) || !target) return false
 function _binarySearch(left, right) {
  // 两个指针重合了，判断当前值是否符合条件
  if (left === right && list[left] !== target) return false
  // 排除意外情况
  if (left < 0 || right > list.length - 1 || left > right) return false
  // 在指定范围内，开始二分
  const mid = Math.floor((left + right) / 2)
  if (list[mid] === target) {
   // 中间值正好就是目标值，即找到了
   return true
  } else if (list[mid] > target) {
   // 中间值比目标值大，即目标值在 左边值 ~ 中间值-1 这个范围，在左边继续查找
   return _binarySearch(left, mid - 1)
  } else {
   // 中间值比目标值小，即目标值在 中间值+1 ~ 右边值这个范围，在右边继续查找
   return _binarySearch(mid + 1, right)
  }
 }
 return _binarySearch(0, list.length - 1)
}
console.log(binarySearch(list, 5)) // true
console.log(binarySearch(list, 0)) // false

插值查找 Interpolation Search

插值查找是对二分查找的进一步改进

如果序列不仅是一个排序好的序列，而且序列的步长大致相同，使用插值查找会更快的找到目标。

插值查找基于如下假设：下标之间的距离比和数据之间的距离比大致相同，即：

(目标下标-最小下标) / (最大下标 - 最小下标) ≈ (目标值 - 最小值) / (最大值 - 最小值)

因此可以算出大致的下标落点：

目标下标 ≈ (目标值 - 最小值) / (最大值 - 最小值) * (最大下标 - 最小下标) + 最小下标

这样就可以计算出大致的下标落点，后续的比较和二分查找一样。

// 插值查找
function interpolationSearch(list, target) {
 if (!Array.isArray(list) || !target) return false
 function _interpolationSearch(left, right) {
  if (left === right && list[left] !== target) return false
  if (left > right || left < 0 || right > list.lenght - 1) return false
  // 计算大致下标落点
  const mid = Math.floor(
   ((target - list[left]) / (list[right] - list[left])) *
    (right - left) +
    left
  )
  // 验证mid的范围
  if (mid < left || mid > right) {
   return false;
  }
  if (list[mid] === target) {
   return true
  } else if (list[mid] > target) {
   return _interpolationSearch(left, mid - 1)
  } else {
   return _interpolationSearch(mid + 1, right)
  }
 }
 return _interpolationSearch(0, list.length - 1)
}
console.log(interpolationSearch(list, 5)) // true
console.log(interpolationSearch(list, 0)) // false

# 排序和查找

# 排序算法

# 查询算法

排序和查找

排序算法

查询算法