算法

优先队列

const leftChild = (index) => index * 2 + 1;
const rightChild = (index) => index * 2 + 2;
const parent = (index) => Math.floor((index - 1) / 2);

class PriorityQueue {
  // 构造函数接受一个compare函数
  // compare返回的-1, 0, 1决定元素是否优先被去除
  // (a, b) => a - b 意味着更小的元素排序更靠前,所以最小的元素首先被去除
  constructor(compare) {
    this.compare = (a, b) => compare(a, b) > 0
    this.heap = []
  }
  // 添加一个元素
  /**
   * 在插入元素后，我们通过比较新插入的元素与其父节点的值来正确地定位该元素在堆中的位置。
   * 如果新插入的元素优先级更高，则将其与父节点交换位置。
   * 这个过程会递归调用，直到该元素被正确地定位。
   */
  add(element) {
    this.heap.push(element)
    if (this.heap.length > 1) {
      this.moveUp(this.heap.length - 1)
    }
  }

  moveUp(index) {
    if (index === 0) {
      return
    }
    // 找到第一个非叶子节点 下标索引
    const parentIdx = parent(index);
    if (this.compare(this.heap[parentIdx], this.heap[index])) {
      // 如果元素比父节点小，进行交换
      this.swap(parentIdx, index);
      this.moveUp(parentIdx);
    }
  }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // 去除头元素并返回
  poll() {
    const root = this.heap.shift()
    // 去掉头元素后需要重新调整堆，确保堆维持最小堆/最大堆
    this.heap.unshift(this.heap[this.heap.length - 1]);
    this.heap.pop();
    this.heapify(0);
    return root;
  }

  heapify(index) {
    const childIdx = this.getChildIdx(index); // child index with which we need to swap
    
    // if the value of index has changed, then some swapping needs to be done
    // and this method needs to be called again with the swapped element
    if (index !== childIdx) {
        this.swap(index, childIdx);
        this.heapify(childIdx);
    }
  }

  getChildIdx(index) {
    let left = leftChild(index);
    let right = rightChild(index);
    
    // if the left child has higher priority than the node we are looking at
    // Min heap: a-b : index-Left > 0 means index > left and so we have to give priority to left
    // Max heap: b-a: Left-index > 0 means left > index and so we have to give priority to left
    if (left < this.heap.length && this.compare(this.heap[index], this.heap[left])) {
        index = left;
    }
    
    // if the right child has higher priority than the node we are looking at
    if (right < this.heap.length && this.compare(this.heap[index], this.heap[right])) {
        index = right;
    }
    return index;
  }

  // 取得头元素
  peek() {
    // 第一个元素是树顶，对应最大或者最小
    return this.heap[0]
  }

  // 取得元素数量
  size() {
    return this.heap.length
  }

}


/**
* Testing
*/
const pq = new PriorityQueue((a, b) => a - b)
// (a, b) => a - b means
//returns        1    if    a    has    higher    priority,
//returns        0    if    both    have    the    same    priority
//returns        -1    if    b    has    higher    priority.
// smaller numbers are closer to index:0
// which means smaller number are to be removed sooner

pq.add(5); // now 5 is the only element
pq.add(2); // 2 added
console.log(pq.peek()); // 2, since smaller number are sooner to be removed
pq.add(1); // 1 added
console.log(pq.peek()); // 1, since smaller number are sooner to be removed
console.log(pq.poll()); // 1 is removed, 2 and 5 are left
console.log(pq.peek());// 2 is the smallest now, this returns 2
console.log(pq.poll()); // 2 is removed, only 5 is left

排序

稳定性

• 堆排序, 快速排序, 希尔排序, 直接选择排序不是稳定的排序算法.

• 基数排序, 冒泡排序, 直接插入排序, 折半插入排序, 归并排序是稳定的排序算法.

冒泡排序

1. 比较相邻的元素. 如果第一个比第二个大, 就交换它们两个

2. 对每一对相邻元素作同样的工作, 从开始第一对到结尾的最后一对, 这样在最后的元素应该会是最大的数

3. 针对所有的元素重复以上的步骤, 除了最后一个

4. 重复步骤 1~3, 直到排序完成

function swap(arr, a, b) {
  [arr[a], arr[b]] = [arr[b], arr[a]];
}

function bubbleSort(arr) {
  const len = arr.length
  for (let i = 0; i < len; i += 1) {
    for (let j = 0; j < len - 1 - i; j += 1) {
      if (arr[j] > arr[j + 1]) {
				swap(arr, j, j + 1)
      }
    }
  }
  return arr
}

插入排序

1. 从第一个元素开始, 该元素可以认为已经被排序;

2. 取出下一个元素, 在已经排序的元素序列中从后向前扫描;

3. 如果该元素(已排序)大于新元素, 将该元素移到下一位置;

4. 重复步骤 3, 直到找到已排序的元素小于或者等于新元素的位置;

5. 将新元素插入到该位置后;

6. 重复步骤 2-5.

function insertionSort(arr) {
  const len = arr.length;
  if (!arr || len < 2) return arr;
  for (let i = 1; i < arr.length; i++) {
    let j = i;
    while(j - 1 >= 0 && arr[j - 1] > arr[j]) {
      swap(arr, j - 1, j);
      j--;
    }
  }
  return arr;
}

选择排序

/**
 * 交换排序，每一轮找到最小的值，依次与第一个、第二个位置的数交换....
 * @param {*} arr 
 * @returns 
 */
function selectionSort(arr) {
  const len = arr.length;
  if (!arr || len < 2) return arr;
  for (let i = 0; i < arr.length; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }
    if (i !== min) {
      swap(arr, i, min);
    }
  }
  return arr;
}

快速排序

/**
 * 快速排序，分治法，选择privot中间值，比他小的放进left数组，大的放到right数组，递归进行这个操作，直到所有都有序
 */
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  const pivotIndex = Math.floor(arr.length / 2)
  const pivot = arr[pivotIndex]
  arr.splice(pivotIndex, 1)
  const low = []
  const high = []
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      low.push(arr[i])
    } else {
      high.push(arr[i])
    }
  }
  return quickSort(low).concat(pivot, quickSort(high))
}

归并排序

function mergeSort(arr) {
  if (arr.length <= 1) {
    return;
  }
  const middle = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, middle);
  const rightArr = arr.slice(middle);
  mergeSort(leftArr);
  mergeSort(rightArr);
  merge(arr, leftArr, rightArr);
}

function merge(arr, leftArr, rightArr) {
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < leftArr.length && j < rightArr.length) {
    if (leftArr[i] <= rightArr[j]) {
      arr[k++] = leftArr[i++];
    } else {
      arr[k++] = rightArr[j++];
    }
  }
  while (i < leftArr.length) {
    arr[k++] = leftArr[i++];
  }
  while (j < rightArr.length) {
    arr[k++] = rightArr[j++];
  }
}

Pow(x, n )

var myPow = function(x, n) {
	if (n === 0) {
    return 1;
  }
  if (n > 0) {
    const half = myPow(x, Math.floor(n / 2));
    return n % 2 === 0 ? half * half : half * half * x;
  }
  // n < 0
  return 1 / myPow(x, -n);
};

x的平方根

/**
 * @param {number} x
 * @return {number}
 */
let mySqrt = function (x) {
  let left = 0;
  let right = x;

  let ans = -1;
  while (left <= right) {
    let mid = Math.round((left + right) / 2);
    let product = mid * mid;
    if (product <= x) {
      ans = mid;
      left = mid + 1;
    } else if (product > x) {
      right = mid - 1;
    } else {
      return mid;
    }
  }

  return ans;
};