quickSort

算法: 快速排序

• 快排分割
  @param list 数组
  @param left 数组第一个元素的下标
  @param right 数据最后一个元素的下标

  function division(list, left, right) {
      //首先选择一个基准元素
      var basenum = list[left];
      while (left < right) {
         //从数组的右端开始向前找，一直找到比base小的数字为止(包括base同等数)
         while (left < right && list[right] >= basenum) {
             right = right - 1;
          }
          //最终找到了比baseNum小的元素，要做的事情就是此元素放到base的位置
          list[left] = list[right];
  
          //从数组的左端开始向后找，一直找到比base大的数字为止（包括base同等数）
          while (left < right && list[left] <= basenum) {
              left = left + 1;
          }
          //最终找到了比baseNum大的元素，要做的事情就是将此元素放到最后的位置
          list[right] = list[left];
          //最后就是把baseNum放到该left的位置
          list[left] = basenum;
          //最终，我们发现left位置的左侧数值部分比left小，left位置右侧数值比left大
          //至此，我们完成了第一篇排序
          return left;
      }
  }

• 调用
  @param list 数组
  @param left 数组第一个元素的下标
  @param right 数据最后一个元素的下标

  function quickSort(list, left, right) {
      //左下标一定小于右下标，否则就超越了
      if (left < right) {
          //对数组进行分割，取出下次分割的基准标号
          var i = division(list, left, right)
          //对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
          quickSort(list, left, i - 1);
          //对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
          quickSort(list, i + 1, right);
      }
  }
  var array = [20, 40, 50, 10, 60];
  quickSort(array, 0, array.length - 1);

• 算法分析
  数组：
  [20,40,50,10,60]

  第一步：
  首先我们从数组的left位置取出该数（20）作为基准（base为20）参照物。

  第二步：
  从数组的right位置向前找，一直找到比（base）小的数，

  如果找到，将此数赋给left位置（也就是将10赋给20），

  此时数组为：10，40，50，10，60，

  left和right指针（下标）分别为前后的10。

  第三步：
  从数组的left位置向后找，一直找到比（base为20）大的数，

  如果找到，将此数赋给right的位置（也就是40赋给10），

  此时数组为：10，40，50，40，60，

  left和right指针分别为前后的40。

  第四步：
  重复“第二,第三“步骤，直到left和right指针（下标）重合，

  最后将（base）插入到40的位置，

  此时数组值为： 10，20，50，40，60，至此完成一次排序。

  第五步：
  此时20已经潜入到数组的内部，20的左侧一组数都比20小，20的右侧作为一组数都比20大，

  以20为切入点对左右两边数按照”第一，第二，第三，第四”步骤进行，最终快排大功告成。

• 复杂度
  平均复杂度： O(n*logn)
  最坏复杂度： 0(n^2)