排序算法

产生随机数进行测试
    function randomNum(num) {
      const data = []
      for (let i = 0; i < num; i++) {
        const val = Math.round(Math.random() * 100)
        data.push(val)
      }
      return data
    }

  

一。插值排序算法:从小到大排序 => 思想是通过当前值与前一个值进行比较判断数组 i - 1 的值是否大于当前值,是就将 i - 1 的值替换成大的值,然后再取数组的 i - 1 -1... 的值与当前值比较,直到前面的值小于当前值为止或取到数组的第一个值为止。重复直到对该数组循环排序完成。

插值排序算法
      function insertionSort(data = []) {
      if (typeof data === 'object' && JSON.stringify(data).indexOf('[') === 0 && data.length > 0) {
        for (let i = 1; i < data.length; i++) {
          const val = data[i]
          let j = i - 1
          for (j; j > -1 && data[j] > val; j--) {
            data[j + 1] = data[j]
          }
          data[j + 1] = val
        }
        return data
      } else {
        console.log('类型只能为数组且长度大于0')
      }
    }

二。快速排序:从小到大排序 => 首先找数组中间的一个值为基准,然后通过循环比较得出小于的值、等于的值、大于的值,然后递归调用,最后将数组拼接起来。

快速排序算法  
    function fastSort(data = []) {
      if (data.length > 1) {
        const centerVal = data.splice(Math.floor(data.length / 2), 1)[0]
        const leftData = []
        const centerData = [centerVal]
        const rightData = []
        for (let i = 0; i < data.length; i++) {
          if (data[i] > centerVal) {
            rightData.push(data[i])
          }
          if (data[i] === centerVal) {
            centerData.push(data[i])
          }
          if (data[i] < centerVal) {
            leftData.push(data[i])
          }
        }
        return fastSort(leftData).concat(centerData, fastSort(rightData))
      } else {
        return data
      }
    }

相关推荐