美文网首页
2020-01-28 快速排序(原地排序)

2020-01-28 快速排序(原地排序)

作者: 人拆 | 来源:发表于2020-01-28 20:58 被阅读0次
    function swap(arr, i, j) {
      const temp = arr[i]
      arr[i] = arr[j]
      arr[j] = temp
    }
    
    function partition(arr, pIndex, left, right) {
      const p = arr[pIndex]
      let startIndex = left
      for (let i = left; i < right; i++) {
        if (arr[i] < p) {
          swap(arr, i, startIndex)
          startIndex++
        }
      }
      swap(arr, startIndex, pIndex)
    
      return startIndex
    }
    
    function quick_sort_c(arr, left, right) {
      if (left < right) {
        let pIndex = right
        let partitionIndex = partition(arr, pIndex, left, right)
        quick_sort_c(arr, left, partitionIndex - 1 < left ? left : partitionIndex - 1)
        quick_sort_c(arr, partitionIndex + 1 > right ? right : partitionIndex + 1, right)
      }
    
    }
    
    function quickSort(arr) {
      const len = arr.length
      if (len <= 1) return arr
    
      return quick_sort_c(arr, 0, len - 1)
    }
    

    相关文章

      网友评论

          本文标题:2020-01-28 快速排序(原地排序)

          本文链接:https://www.haomeiwen.com/subject/iimmthtx.html