效果图
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]这半个的操作了,重复以上操作即可
个人觉得想法简单,但是转化为代码就得费点心了.可以在纸上写出来,然后就简单了
网友评论