JavaScript

JavaScript如何快速排序

特别声明:如果您喜欢小站的内容,可以点击 终身VIP¥188.00元 包年VIP¥88.00元 包季VIP¥28.00 包月VIP¥10.00元 进行全站阅读。 如果您对付费阅读有任何建议或想法,欢迎发送邮件至: 864479410@qq.com,或添加QQ:864479410(^_^)

基本思想

1 在数据集之中,选择一个元素作为"基准"(pivot)。
2 所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。
3 对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

举个栗子

    let array = [2, 9, 6, 3, 80, 34, 7, 8];

JavaScript如何快速排序

    function quickSort(list) {
      if(list.length <= 1) { return list; }
      let left = [], right = [];
      let pivotIndex = Math.floor(list.length / 2);
      let pivot = list.splice(pivotIndex, 1)[0];

      for(let index = 0, len = list.length; index < len; index++) {
        let val = list[index];

        if(val <= pivot) {
          left.push(val);
        } else {
          right.push(val);
        }
      }

      return [...quickSort(left), pivot, ...quickSort(right)];
    }

输出: [2, 3, 6, 7, 8, 9, 34, 80]

quickSort函数解构

      let left = [], right = [];
      let pivotIndex = Math.floor(list.length / 2);
      let pivot = list.splice(pivotIndex, 1)[0];

      for(let index = 0, len = list.length; index < len; index++) {
        let val = list[index];

        if(val <= pivot) {
          left.push(val);
        } else {
          right.push(val);
        }
      }

这部分逻辑正是对基本思想中的1、2点的实践。

  • #### 1 找出基准数

let pivotIndex = Math.floor(list.length / 2); let pivot = list.splice(pivotIndex, 1)[0];
  • #### 2 以“基准”二分数组

for(let index = 0, len = list.length; index < len; index++) { let val = list[index]; if(val <= pivot) { left.push(val); } else { right.push(val); } }
  • #### 3 重复1、2点

在栗子中的数组执行一次1、2点实现后,你会发现此时执行后出现三个结果
1)letf = [2];
2)pivot = 3;
3)right = [9, 6, 80, 34, 7, 8];

然后依次组合

    [...left, pivot, ...right]
    // [2, 3, 9, 6, 80, 34, 7, 8]

你会发现left只有一个元素,那就没有必要继续对left排序,所以没有必要再排序

    if(list.length <= 1) { return list; }

然后再看right,并不是有序数组。那要怎么办?继续对right排序,调用quickSort

    quickSort(right)
    // [...quickSort(left), pivot, ...quickSort(right)];

    return [...quickSort(left), pivot, ...quickSort(right)];

正是对第3点的实践。

(0)

本文由 Web秀 作者:Javan 发表,转载请注明来源!

热评文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注