排序：即把数组中每个元素找到合适自己放的位置，数组长度 - 1 个元素都找到位置了，则整个数组就有序了
这两天一直在研究快速排序，根据快速排序的思想，我自己实现了一版分治法，即确定privot元素位置的方法，不同于使用循环，我这里同样使用了递归，也尝试着进行了一些优化，跟一般实现有些区别就是传参的时候要把startindex传进来，因为递归没办法保存开始索引（left）,这里调用partition函数时，直接把startindex当参数传递过来使用
分治部分递归（双向）第一版 for
这是我脑海中第一个想出来的做法，用了for循环，这里其实不合适，换成while循环更佳
// 最先想到的一版
function fast_sortc(arr, startindex, left, right) {
//这里的出口可以不要，直接在fast_sort2中把递归结束条件前移,我之前是写到privot之后了
//if(left === right) return
let privot = arr[startindex]
let temp = 0
//这里循环起始与结束条件不对，不能用left与right, 因为循环的时候left与right一直会改变
//比较粗暴的写法就是从startindex开始到arr.length - 1, 这里可以进一步优化
for(let i = startindex; i < arr.length - 1; i++){
if(arr[right] > privot) {
right --
}else{
// if((left !== right) && arr[left] <= privot) {
if(arr[left] <= privot) {
left ++
}
}
//把基准元素放到找到的位置处,递归出口
if(left === right){
temp = arr[right]
arr[right] = privot
arr[startindex] = temp
return left
}
}
//make the change
temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
//这样每次left,right都确定了，再递归找到下一轮的left,right值
return fast_sortc(arr, startindex, left, right)
}
//升级后的一版
function partition(arr, startindex, left, right) {
let privot = arr[startindex]
let temp = 0
//这里循环次数怎么确定？
//其实这里可以考虑最坏情况，即有一个指针一直不动，另一个指针向他靠，所以最坏情况是比较 arr.length -1 次
for(let i = startindex; i < arr.length - 1; i++){
if(arr[right] > privot) {
right --
}else if(arr[left] <= privot){
left ++
}else{
//console.log('left, right 已经确定了直接交换', left, right)
//make the change
temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
}
//把基准元素放到找到的位置处,递归出口
if(left === right){
temp = arr[right]
arr[right] = privot
arr[startindex] = temp
return left
}
}
return partition(arr, startindex, left, right)
}
分治部分循环（双向）第二版 while
// startindex 没必要传，请看下边正式while循环版
function fast_sort(arr, startindex, left , right){
let privot = arr[startindex]
let temp = 0
while(left !== right){
if(arr[right] > privot){
right --
}else if(arr[left] <= privot){
left ++
}else{
//left,right互换
//console.log('left, right 已经确定了直接交换', left, right)
temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
}
}
//privot与找到的位置元素互换
temp = arr[right]
arr[right] = privot
arr[startindex] = temp
return left
}
分治部分循环（双向）
使用while循环后就不用递归了，这时其实没必要传startindex，把传递过来的left，right保存一下不就行了吗 😂
function fast_sort(arr, left , right){
let privot = arr[left]
let temp = 0
let startindex = left, endindex = right
while(startindex !== endindex) {
if(arr[endindex] > privot){
endindex --
}else if(arr[startindex] <= privot){
//当startindex对应的值小于等于privot的时候，移动指针，因此如果数组中有相同的数，指针还是会移动
//因此相同的数会交换位置，因此快速排序是不稳定排序
startindex ++
}else{
//left,right互换
//console.log('left, right 已经确定了直接交换', left, right)
temp = arr[startindex]
arr[startindex] = arr[endindex]
arr[endindex] = temp
}
}
//privot与找到的位置元素互换
temp = arr[endindex]
arr[endindex] = privot
arr[left] = temp
return startindex
}
//测试用例
function fast_sort3(arr, left, right) {
//递归出口,保证传过去的都是需要处理的
//因为每次分隔要么是只剩一个元素了(left === right)，这时这个元素肯定就在那个位置不用动了
//要么就是分隔后一个元素都没有了, 这时(left > right),直接退出就行了，不需要什么处理逻辑
if(left >= right) return
let privot = fast_sort(arr, left, right)
//递归处理 left 部分
fast_sort3(arr, left, privot - 1)
//递归处理 right 部分
fast_sort3(arr, privot + 1, right)
}
分治部分循环（双向）书上写的
这个写法跟我自己写的那个运行效果都是一样的，只是思路不一样，书上的感觉更突出双向比较吧，while内部又用了两个while循环，并且在交换数据时还要有个if, 避免left === right 做无意义的交换, 个人感觉我写的更好呢 🤣🤣
function fast_sort_good(arr, left, right) {
let privot = arr[left]
let temp = 0
let startindex = left, endindex = right
while(startindex !== endindex) {
while(startindex < endindex && arr[endindex] > privot){
endindex --
}
while(startindex < endindex && arr[startindex] <= privot){
startindex ++
}
if(startindex < endindex) {
//console.log('left, right 已经确定了直接交换', left, right)
temp = arr[startindex]
arr[startindex] = arr[endindex]
arr[endindex] = temp
}
}
//privot与找到的位置元素互换
temp = arr[endindex]
arr[endindex] = privot
arr[left] = temp
return endindex
}
分治部分循环（单向）
单向比较好理解，也比较简洁，推荐
//单向交换
function fast_sort_single(arr, left , right){
let privot = arr[left]
let temp = 0
let mark = left
for(let i = left + 1; i <= right; i++){
if(arr[i] < privot){
mark ++
//元素交换
temp = arr[i]
arr[i] = arr[mark]
arr[mark] = temp
//break
}
}
//privot位置找到了
temp = arr[mark]
arr[mark] = privot
arr[left] = temp
return mark
}
递归排序部分
//递归处理，把数组按privot递归分隔，把一个大规模问题转化成小规模问题解决，前提是大小问题解决思路相同
function quick_sort(arr, startindex, left, right) {
//递归出口,保证传过去的都是需要处理的
//因为每次分隔要么是只剩一个元素了(left === right)，这时这个元素肯定就在那个位置不用动了
//要么就是分隔后一个元素都没有了, 表现为pivot在最左边的位置(0, -1) ,要么在最右边的位置 (3,2), 这时(left > right),直接退出就行了
if(left >= right) return
let privot = partition(arr, startindex, left, right)
//递归处理 left 部分
quick_sort(arr, left, left, privot - 1)
//递归处理 right 部分
quick_sort(arr, privot + 1, privot + 1, right)
}
使用栈回溯排序
使用栈（数组）来实现递归分割，基本上所有用递归实现的逻辑都可以用栈来实现，使用栈就是为了回溯，一开始我脑中的回溯概念是错误的，对于递归的理解也是片面的，认为是所有left,right都push后，再依次pop处理，其实递归是先处理一部分，比如先处理left, left部分返回后再处理right部分，每一部分处理的过程中遵循同样的过程。这里借用栈就是存储一下每次传给partition的left和right值
最开始分析的时候，遇到以下困惑，其实是没有很好理解递归的过程
//把(0,2) pop 传给 fast_sort_single(arr,left,right)
//那么(0,2),(0,-1),(1,2)这些从哪来呢，还是要通过fast_sort_single(arr,left,right)来
//how ?
分析下来递归和用栈来回溯，思想相通，都能解决问题，不过实际上还是有区别的，多在chrome dev tools里debug看看过程，即能理解，用栈这里stack中最多压入三层，而递归函数调用栈最多是4层
function quick_sort(arr, left, right) {
let stack = []
let obj = {left: left, right:right}
stack.push(obj)
while(stack.length){
let ob = stack.pop()
let pivot_left = ob.left
let pivot_right = ob.right
console.log(pivot_left, pivot_right)
// if(pivot_left < pivot_right) {
// let pivot = fast_sort_single(arr, pivot_left, pivot_right)//3
// //先压右边,再压左边
// let objr = {left: pivot + 1, right: pivot_right}
// stack.push(objr)
// let objl = {left: pivot_left, right: pivot - 1} //0,2
// stack.push(objl)
// }
//if语句优化如下：
let pivot = fast_sort_single(arr, pivot_left, pivot_right)//3
if(pivot_right > pivot + 1 ){
let objr = {left: pivot + 1, right: pivot_right}
stack.push(objr)
}
if(pivot_left < pivot - 1) {
let objl = {left: pivot_left, right: pivot - 1} //0,2
stack.push(objl)
}
}
}
本文由 dealdot ＜dealdot＃163.com＞ 创作, Full Stack Developer @ DeepBlue
本文最后编辑时间为: Jun 17, 2021 at 11:39 am
转载请注明来源