爱云校：算法两道（一、1-100所有的素数 二、快速排序）（笔试）

[aaaaaajie]

面试公司：

爱云校

面试环节：

一面笔试

问题：

1.写出一个方法输出1-100内的所有素数。
2.给定一个整数数组，实现快速排序算法进行升序排列。如[2, 5, 8, 9, 3] =>[2, 3, 5, 8, 9]

备注：

1. 素数定义为一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数。

[aaaaaajie]

1.写出一个方法输出1-100内的所有素数。

解析：

由素数（质数）定义可知：

• ① 0、1都不是质数，那么最小的质数就是2。
• ② 除了1和它自身，不能被其他数整除，那么代码表达式表示为：

i % j === 0

代码实现

function fn() {
  const arr = []
  for (let i = 2; i <= 100; i++) {
    let bl = false
    for (let j = 2; j <= i; j++) {
      if (i === j) continue
      i % j === 0 && (bl = true)
    }
    !bl && arr.push(i)
  }
  return arr
}
console.log(fn()) 

输出：// [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

2.给定一个整数数组，实现快速排序算法进行升序排列。如[2, 5, 8, 9, 3] =>[2, 3, 5, 8, 9]

代码实现

function qSort(arr) {
  if (arr.length <= 1) return arr
  const index = Math.floor(arr.length / 2)
  const midVal = arr.splice(index, 1)[0]
  const left = [],
    right = []
  arr.forEach(item => {
    if (item < midVal) left.push(item)
    else right.push(item)
  })
  return [...qSort(left), midVal, ...qSort(right)]
}
qSort([2, 5, 8, 9, 3])

**输出：// [2, 3, 5, 8, 9]

解析：（分治法）

将一个列表分割为左右两块，然后再将字列表再进行分割为左右两块，如何反复，知道子元素长度为1时，结束！

[aaaaaajie]