最小的k个数(小顶堆、快排)

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

解决这个问题的方法有三种：

• 暴力解法，sort
• 堆
• 快速排序

1、sort (省略)

sort的原理是基于快排，不过性能最低。

2、堆 （小顶堆）

堆有很多种实现方式，具体参考 https://en.wikipedia.org/wiki/Heap_(data_structure)，其中最简单实现的是二叉堆，而且代码阅读起来通俗易懂。

JS中没有二叉堆的数据结构，我们需要用代码去实现它。

class BinaryHeap {
  
  constructor (arr) {
    this.list = []
    if (Array.isArray(arr)) {
      arr.forEach(this.insert.bind(this))
    }
  }

  insert (val) {
    const { list, swap } = this
    list.push(val)
    let point = list.length - 1
    while (point) {
      const parent = Math.floor((point - 1) / 2)
      if (list[point] <= list[parent]) {
        break
      }
      this.swap(point, parent)
      point = parent
    }
  }

  deleteTop () {
    const { list } = this
    if (!list.length) return null
    this.swap(0, list.length - 1)
    const res = list.pop()
    const len = list.length
    let index = 0
    let exchange = index * 2 + 1
    while (exchange < len) {
      // 取左右child中较大的那个，作为置换
      let rightChild = index * 2 + 2
      if (list[exchange] < list[rightChild] && rightChild < len) {
        exchange = rightChild
      }
      if (list[exchange] <= list[index]) {
        break
      }
      this.swap(index, exchange)
      index = exchange
      exchange = index * 2 + 1
    }
    return res
  }

  show () {
    return this.list
  }

  top () {
    if (!this.list.length) return null
    return this.list[0]
  }

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

}

var getLeastNumbers = function(arr, k) {
   const len = arr.length
   if (len <= k) return arr
   const heap = new BinaryHeap(arr.slice(0, k))
   for (let i = k; i < len; i++) {
       if (heap.top() > arr[i]) {
            heap.deleteTop()
            heap.insert(arr[i])
       }
   }
   return heap.list
};

const arr = [222, 33, 114, 52, 0, -19, -299, 92, 94, -1]

console.log(getLeastNumbers(arr, 8));

// [94, 92, 33, 52, 0, -19, -299, -1]

复杂度分析：

时间复杂度：O(nlogk)，其中 n 是数组 arr 的长度。由于小顶堆实时维护前 k 小值，所以插入删除都是 O(logk) 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 O(nlogk) 的时间复杂度。

空间复杂度：O(k)，因为堆里最多 k 个数。

3、 快速排序

快排的划分函数每次执行完后都能将数组分成两个部分，小于等于分界值 pivot 的元素的都会被放到数组的左边，大于的都会被放到数组的右边，然后返回分界值的下标。

与快速排序不同的是，快速排序会根据分界值的下标递归处理划分的两侧，而这里我们只处理划分的一边。

• 如果p = k，说明第 k 个元素已经放入正确位置，返回前 k 个元素
• 如果k < p，前 k 个元素在[left, p - 1]之间，缩小查找范围，继续查找
• 如果p < k，前 k 个元素在[p + 1, right] 之间，缩小查找范围，继续查找

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var getLeastNumbers = function(arr, k) {
 if (arr.length<=1 || k>=arr.length) return arr;
 let left = 0, right = arr.length - 1;
 let p = pivot(arr, left, right);
 while (p !== k) {
     if (p < k) {
         left = p + 1;
         p = poivet(arr, left, right);
     } else if (p > k) {
         right = p - 1;
         p = poivet(arr, left, right);
     }
 }
 return arr.slice(0, k);
};

function pivot(arr, low, high) {
  const l = low;
  const point = arr[low];
  while (low < high) {
    while (low < high && arr[high] > point) {
      high--;
    }

    while (low < high && arr[low] <= point) {
      low++;
    }
    swap(arr, low, high);
  }
  swap(arr, l, low);
  return low;
}

function swap(arr, i, j) {
  [arr[j], arr[i]] = [arr[i], arr[j]];
}

快速排序的的平均时间复杂度是O(n * log n)，但最坏的复杂度是O(n ^ 2)，比如：[1, 2, 3, 4, 5] 这种有序数组。最好情况和最坏情况差很多。属于比较极端的情况。

完整的快排: 写法1:

function quickSort(arr, low, high) {
  if (high - low < 1) return;
  const l = low, h = high;
  const point = arr[low];
  while (low < high) {
    while (low < high && arr[high] > point) {
      high--;
    }

    while (low < high && arr[low] <= point) {
      low++;
    }
    swap(arr, low, high);
  }
  swap(arr, l, low);
  quickSort(arr, l, low - 1);
  quickSort(arr, low + 1, h);
  return low;
}

写法2:

   function quickSort(array, start, end) {
      if (end - start < 1) {
        return;
      }
      const target = array[start];
      let l = start;
      let r = end;
      while (l < r) {
        while (l < r && array[r] >= target) {
          r--;
        }
        array[l] = array[r];
        while (l < r && array[l] < target) {
          l++;
        }
        array[r] = array[l];
      }
      array[l] = target;
      quickSort(array, start, l - 1);
      quickSort(array, l + 1, end);
      return array;
    }

写法3: 附上多数组实现快排，更通俗易懂:

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const poivet = arr[0];
  const poivetArr = [];
  const lowArr = [];
  const hightArr = [];
  arr.forEach(item => {
    if (item === poivet) {
      poivetArr.push(item);
    }
    if (item > poivet) {
      hightArr.push(item);
    }
    if (item < poivet) {
      lowArr.push(item);
    }
  });

  return [...quickSort(lowArr), ...poivetArr, ...quickSort(hightArr)]

}