9. 进阶算法之"搜索排序"

简介

• 排序： 把某个乱序的数组变成升序或者降序的数组
• 搜索：找出数组中某个元素的下标

JS中的排序和搜索

• JS中的排序：数组的 sort 方法
• JS中的搜索：数组的 indexOf 方法

排序算法

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序
• 快速排序
• ...

搜索算法

• 顺序搜索
• 二分搜索
• ...

1. JavaScript 实现：冒泡排序

image.png image.png

Array.prototype.bubbleSort = function() {
    console.log(this);
    for(let i = 0; i< this.length -1; i += 1) {
       for(let j = 0; j< this.length -1 - i;  j += 1) {
          if(this[j] > this[j+1]) {
              const temp = this[j];  
              this[j] = this[j+1];
              this[j+1] = temp;
          }
      }
   }
}
const arr = [5,2,4,1];
arr.bubbleSort();

时间复杂度：O(n^2) // 两个嵌套循环

2. JavaScript 实现：选择排序

image.png

Array.prototype.selectionSort = function() {
    for(let i = 0; i< this.length -1; i += 1) {
       let indexMin = i;
       for(let j = i; j< this.length;  j += 1) {
          if(this[j] > this[indexMin]) {
              indexMin = j;
          }
       }
       if(indexMin !== i) {
           const temp = this[i];  
           this[i] = this[indexMin];
           this[indexMin] = temp;
       }
   }
}
const arr = [5,2,4,1];
arr.selectionSort();

时间复杂度：O(n^2) // 两个嵌套循环

3. JavaScript 实现：插入排序

image.png

Array.prototype.insertionSort = function() {
    for(let i = 1; i< this.length; i += 1) {
        const temp = this[i];  
        let j = i ;
        while(j > 0) {
             if(this[j-1] > temp) {
                this[j] = this[j-1]; 
             } else {
                break;
             }
             j -= 1;
        }  
        this[j] = temp;
    }
};
const arr = [5,2,4,1];
arr.insertionSort();

时间复杂度：O(n^2) // 两个嵌套循环, 但是在小型数组时，性能更好

4. JavaScript 实现：归并排序

image.png image.png

Array.prototype.mergeSort = function() {
  // 递归将数组分开为单个数的数组
  const rec = (arr) => { 
     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  = rec(left);    
     const orderRight = rec(right);
     const res = [];
     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 = rec(this);
  res.forEach((n, i) => {
    this[i] = n;
  })
}
const arr = [5,4,8,0,1,2,3];

arr.mergeSort();

• 分的时间复杂度：O(logn) //
• 合的时间复杂度：O(n) //
• 时间复杂度 O(n*logN)

5. JavaScript 实现：快速排序

image.png

Array.prototype.quickSort = function() {
  const rec = (arr) => {
    if(arr.length <= 1) { return arr; } // 递归终结条件
    const left = [];
    const right = [];
    const mid = arr[0];
    for(let i = 1; i< arr.length; i += 1) {
      if(arr[i] < mid) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return [...rec(left), mid, ...rec(right)];
  };
  const res = rec(this);
  res.forEach((n, i) => { this[i] = n; }); 
}
const arr = [5,2,4,1];
arr.quickSort();
console.log(arr);

• 递归时间复杂度：O(logn) //
• 分区的时间复杂度：O(n) //
• 时间复杂度 O(n*logN)

6. JavaScript 实现：顺序搜索

image.png

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

• 时间复杂度 O(n)

7. JavaScript 实现：二分搜索（折半搜索，前提是数组是有序的）

image.png

Array.prototype.binarySearch = function(item) {
  let low = 0;
  let hight = this.length - 1;
  while(low <= hight) {
    const mid = Math.floor((low + hight) / 2);
    const element = this[mid];
    if(element < item) {
      low = mid +1
    } else if(element < item) {
      hight = mid -1
    } else {
      return mid;
    }
  }
  return -1;
}
const res = [1,2,3,4,5].binarySearch(0);

• 时间复杂度 O(logN)

Leecode 21. 合并两个有序链表

image.png image.png image.png

function ListNode(val) {
  this.val = val;
  this.next = null;
}
var mergeTwoLists = function(l1, l2) {
  const res = new NodeList(0);
  let p = res;
  let p1 = l1;
  let p2 = l2;
  while(p1 && p2) {
    if(p1.val < p2.val) {
      p.next = p1;
      p1 = p1.next;
    } else {
      p.next = p2;
      p2 = p2.next;
    }
    p = p.next;
  }
  // 如果某个链表还有值，拼接到新链表的结尾即可
  if(p1) {
    p.next = p1;
  }
  if(p2) {
    p.next = p2;
  }
  return res.next;
}

时间复杂度O(n)
空间复杂度O(1)

Leecode 374. 猜数字大小

image.png image.png image.png

// 0 mid
// 1 higher than the guess number
//-1 lower than the guess number
//var guess = function(num) {}
var guessNumber = function(n) {
  let low = 1;
  let heigh = n;
  while(low <= heigh) {
    const mid = Math.floor((low + heigh) / 2);
    const res = guess(mid);
    if(res === 0) {
      return mid;
    } else if(res === 1) {
      low = mid + 1 
    } else {
      heigh = mid - 1 
    }
  }
}

时间复杂度O(n) && 空间复杂度O(1)