排序和搜索

js原生自带的排序和搜索

冒泡排序

Array.prototype.bubbleSort = function() {
  for(let i = 0; i < this.length - 1; i ++){
    // 完成一轮
    for(let j = 0; j < this.length - 1 - i; j ++){
      // console.log(this[j], this[j+1]);
      if(this[j] > this[j+1]) {
        const tmp = this[j];
        this[j] = this[j+1];
        this[j+1] = tmp;
      }
    }
  }
};



const arr = [5, 4, 3, 2, 1];
arr.bubbleSort(); 
console.log(arr);

时间复杂度：$O(n^2)$O(n2)

选择排序

Array.prototype.selectSort = function() {

  // 一轮
  for(let i = 0; i < this.length - 1; i ++) {
    let indexMin = i;
    for(let j = i; j < this.length; j++){
      if(this[j] < this[indexMin]){
        indexMin = j;
      }
    }
    if(indexMin !== i){ 
      const tmp = this[i];
      this[i] = this[indexMin];
      this[indexMin] = tmp;
    }
  }
}


const arr = [5,4,3,2,1];
arr.selectSort();
console.log(arr);

时间复杂度$:O(n^2)$:O(n2)

归并排序

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,3,2,1];
arr.mergeSort();
console.log(arr);

时间复杂度$:O(nlogn)$:O(nlogn)

快速排序

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 ++) {
      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 = [2,4,5,1,3]; 
arr.quickSort();
console.log(arr);

顺序搜索

Array.prototype.sequentialSearch = function(target) {

  for(let i = 0; i < this.length; i ++){
    if(this[i] === target){
      return i;
    }
  }
  return -1;
}


const arr = [1, 3, 5, 7, 9];
const res = arr.sequentialSearch(5);
console.log(res);

时间复杂度$:O(N)$:O(N)

二分搜索

Array.prototype.binarySearch = function(target) {
  let low = 0;
  let high = this.length - 1;
  while(low <= high){
    const mid = Math.floor((low + high) / 2);
    const element = this[mid];
    if(element < target){
      low = mid + 1;
    }else if(element > target){
      high = mid - 1;
    }else {
      return mid;
    }
  }
  return -1;
}


const arr = [1, 2, 3, 4, 5];

const res = arr.binarySearch(3);
console.log(res);

时间复杂度:$O(logN)$O(logN)

LeetCode 21 合并两个有序链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    const dummy = new ListNode(-1);
    let p = dummy;
    while(l1 && l2){
        if(l1.val < l2.val){
            p.next = l1;
            p = p.next;
            l1 = l1.next;
        }else{
            p.next = l2;
            p = p.next;
            l2 = l2.next;
        }
    }

    if(l1) p.next = l1;
    if(l2) p.next = l2;
    return dummy.next;
};

LeetCode 374 猜数字大小

/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return 	            -1 if num is lower than the guess number
 *			             1 if num is higher than the guess number
 *                       otherwise return 0
 * var guess = function(num) {}
 */

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function(n) {

    let l = 1;
    let r = n;
    while(l <= r){
        const mid = Math.floor((l + r) / 2);
        const res = guess(mid);
        if(res === 0){
            return mid;
        }else if(res === 1){
            l = mid + 1;
        }else if(res === -1){
            r = mid - 1;
        }
    };

};