快速排序步骤

效果图

3450630-103cc7c8c6ab5298.gif

其实上面的这个动图不了解原理的话看起来有点晦涩难懂,了解了就简单了,这个图可以放到最后看,现在解释太费劲了
先上代码

  mounted () {
    var arr = [6, 8, 12, 6, 7, 9, 3, 4, 19]
    this.quickSort(arr, 0, arr.length - 1)
  }

    // 快速排序,使用递归
    quickSort (arr, left, right) {
      console.log(arr)
      console.log(left + '/' + right)
      // 定义i和j的原因是下面需要使用这两个值确定下一个分组的递归左右边界
      let i = left
      let j = right
      // 不能使用0,因为arr永远是完整的数组,但是left是一直变的
      let key = arr[i]
      // 排序结束
      if (left >= right) {
        return
      }
      while (i < j) {
        // 当i<j,关键值小于从后面数的出现比key值小的数之前一直自减
        while (i < j && arr[j] >= key) {
          j--
        }
        // 这个时候key值是最小的,证明结束了
        if (i === j) {
          break
        }
        // 这里需要了解一下i++和++i是不一样滴
        arr[i++] = arr[j]
        while (i < j && arr[i] <= key) {
          i++
        }
        // 这个时候key值是最大的,证明结束了
        if (i === j) {
          break
        }
        // 这里需要了解一下j--和--j是不一样滴
        arr[j--] = arr[i]
      }
      arr[i] = key
      this.quickSort(arr, left, j - 1)
      this.quickSort(arr, j + 1, right)
    }

这里用的是递归的方式,因此会执行多遍,这里介绍只介绍第一轮递归,后面的与本次一样
var arr = [6, 8, 12, 6, 7, 9, 3, 4, 19]
定义三个值
第一个i,i代表的是最左侧值的下标.var i = 0
第二个j,j代表的是最右侧值的下标.var j = arr.length - 1
第三个key值,默认取最左侧的值 var key = arr[i] = 6

接下来就是费脑环节了,仔细一步步的跟着思路走,

(1)先从右侧起寻找比key(6)小的值,如果没有j--,再进行下轮寻找,可以找到j = 7, i = 0时 4 < 6停止循环
执行操作(i++先赋值在增1)
arr[i++] = arr[j]
即arr[1] = 4
arr = [4, 8, 12, 6, 7, 9, 3, 4, 19]

(2)接下来从左侧寻找比key(6)大的值,如果没有i++,再进行下轮寻找,可以找到当i = 1,j = 7时 8 > 6停止循环
执行操作(j--先赋值再减1)
arr[j--] = arr[i]
即arr[7] = 8
arr = [4, 8, 12, 6, 7, 9, 3, 8, 19]

(3)继续循环
此时i = 1,j = 6
从右侧寻找比key(6)小的值,可以找到i = 1,j = 6时 3 < 6,停止循环
执行操作
arr[i ++] = arr[j]
arr[1] = arr[6]
arr = [4, 3, 12, 6, 7, 9, 3, 8, 19]

(4)此时i = 2,j = 6
从左侧找比key大的值,找到 i = 2,j = 6 时12 > 6,停止循环
执行操作
arr[j --] = arr[i]
arr[6] = arr[2]
arr = [4, 3, 12, 6, 7, 9, 12, 8, 19]

(5)此时i = 2,j = 5
从右侧开始寻找比key小的值
发现直到i === j 即 2 === 2时也没找到,所以第一轮递归结束
此时设置arr[i] = key,arr[2] = 6
arr = [4, 3, 6, 6, 7, 9, 12, 8, 19]

(6)接下来就是将数组形式上分割成两部分,分别递归
this.quickSort(arr, left, j - 1)
this.quickSort(arr, j + 1, right)

this.quickSort(arr,0,1) [4, 3]
this.quickSort(arr, 3, 8) [6, 7, 9, 12, 8, 19]

依次进行下去即可,不信的话可以按照上面的方式继续推导
下面写一下(arr,0,1)接下来的过程,仔细观察
原始数据 arr = [4, 3, 6, 6, 7, 9, 12, 8, 19]

(1)[4, 3]
定义三个值
第一个i,i代表的是最左侧值的下标.var i = left = 0
第二个j,j代表的是最右侧值的下标.var j = j - 1 = 1
第三个key值,默认取最左侧的值 var key = arr[i] = 4
从右侧找比4小的值,发现第一个就是于是执行
arr[i++] = arr[j]
arr[0] = arr[1]
于是数组变成了
arr = [3, 3, 6, 6, 7, 9, 12, 8, 19]
i = 1

(2)接下来从左侧开始找比key大的值,此时发现i === j
所以终止循环执行arr[i] = key
arr[1] = 4
arr = [3, 4, 6, 6, 7, 9, 12, 8, 19]
好了这半个就结束了

下一个就是[6, 7, 9, 12, 8, 19]这半个的操作了,重复以上操作即可

个人觉得想法简单,但是转化为代码就得费点心了.可以在纸上写出来,然后就简单了