排序

把某个乱序的数组变成升序或者降序的数组。 sort 动画地址： https://visualgo.net/zh/sorting

冒泡排序

  1. 比较所有相邻的元素，如果第一个比第二个大，则交换他们
  2. 一轮下来，则可以保证最后一个数是最大的
  3. 执行n-1轮，则可以完成排序 ```javascript /*
  • 性能较差
  • 时间复杂度O(n^2) */ Array.prototype.bubbleSort = function () { for(let i = 0; i< this.length - 1; i++) {
    1.   for (let j = 0; j < this.length - 1 - i; j++) {
    2.       if (this[j] > this[j + 1]) {
    3.           swap(this, this[j], this[j + 1])
    4.       }
    5.   }
    } }

function swap(arr, i1, l2) { let temp = arr[i1] arr[i1] = arr[i2] arr[i2] = temp }

const arr = [5,4,2,3,1] arr.sort() console.log(‘arr’, arr)

  1. <a name="RQSqy"></a>
  2. ### 快速排序
  3. > 性能较好.时间复杂度O(n * logn). 其中递归O(logn), 遍历分区O(n)
  5. 1. 从数组中选择一个基准，所有比基准小的元素放在基准前面，比基准大的元素放在基准后面
  6. 1. 递归：递归的对基准前后的子数组进行分区
  7. ```javascript
  8. Array.prototype.quickSort = function () {
  9.     const rec = (arr) => {
  10.         if (arr.length === 1) {
  11.             return arr
  12.         }
  13.         const left = []
  14.         const right = []
  15.         const base = arr[0]
  16.         for (let i = 1; i < arr.length; i++) {
  17.             if (arr[i] < base) {
  18.                 left.push(arr[i])
  19.             } else {
  20.                 right.push(arr[i])
  21.             }
  22.         }
  23.         return [...rec(left), base, ...rec(right)]
  24.     }
  26.     const res = rec(this)
  27.     console.log(res)
  28.     res.forEach((item, index)=>{
  29.         this[index] = item
  30.     })
  31. }
  33. const arr = [2,4,5,3,1]
  34. arr.quickSort()
  35. // console.log('arr', arr)

搜索

找出数组中的位置或者下标。 indexOf

顺序搜索

  1. Array.prototype.sequentialSearch = function (item) {
  2.     for (let i = 0; i < this.length; i++){
  3.         if(this[i] === item){
  4.             return i
  5.         }
  6.     }
  7.     return -1
  8. }

二分搜索

有个前提是顺序数组. 时间复杂度O(logn)

  • 从数组中间元素开始，如果中间元素正好是目标值，则搜索结束
  • 如果目标值大于或者小于中间元素，则在大于或者小于中间元素的那一半数组中搜索 ```javascript Array.prototype.sequentialSearch = function (item) { for (let i = 0; i < this.length; i++){
    1.   if(this[i] === item){
    2.       return i
    3.   }
    } return -1 }

Array.prototype.binarySearch = function (item){ let low = 0 let high = this.length - 1

  1. while(low <= high) {
  2.     const mid = Math.floor((low + high)/2)
  3.     if(this[mid] < item) {
  4.         low = mid + 1
  5.     } else if(this[mid] > item) {
  6.         high = mid - 1
  7.     } else {
  8.         return mid
  9.     }
  10. }
  11. return -1

}

const res = [1,2,3,4,5].binarySearch(3) console.log(‘res’, res)

```