这里用的是递归的方式,因此会执行多遍,这里介绍只介绍第一轮递归,后面的与本次一样
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]这半个的操作了,重复以上操作即可