美文网首页
用JavaScript实现快速排序

用JavaScript实现快速排序

作者: 酷鼠666 | 来源:发表于2018-06-14 11:17 被阅读0次

    1.首先,定义一个quickSort函数,它的参数是一个数组。

    var quickSort = function(arr) {
    
    };
    

    2.然后,检查数组的元素个数,如果小于等于1,就返回。

    var quickSort = function(arr) {
      if (arr.length <= 1) {return arr;}
    };
    

    3.接着,选择"基准"(pivot),并将其与原数组分离,再定义两个空数组,用来存放一左一右的两个子集。

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

    4.然后,开始遍历数组,小于"基准"的元素放入左边的子集,大于基准的元素放入右边的子集。

    var quickSort = function(arr) {
      if (arr.length <= 1) { return arr; }
      var pivotIndex = Math.floor(arr.length / 2) ;
      var pivot = arr.splice(pivotIndex, 1)[0];
      var left = [];
      var right = [];
      for (var i = 0; i < arr.length; i++){
        if (arr[i] < pivot) {
          left.push(arr[i]);
        } else {
          right.push(arr[i]);
        }
      }
    };
    

    5.最后,使用递归不断重复这个过程,就可以得到排序后的数组。

    var quickSort = function(arr) {
      if (arr.length <= 1) { return arr; }
      var pivotIndex = Math.floor(arr.length / 2);
      var pivot = arr.splice(pivotIndex, 1)[0];
      var left = [];
      var right = [];
      for (var i = 0; i < arr.length; i++){
        if (arr[i] < pivot) {
          left.push(arr[i]);
        } else {
          right.push(arr[i]);
        }
      }
      return quickSort(left).concat([pivot], quickSort(right));
    };
    

    运行看看


    image

    相关文章

      网友评论

          本文标题:用JavaScript实现快速排序

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