荷兰国旗延伸至快速排序
本文篇幅主要讲述荷兰国旗问题以及快速排序
序言
对于刚学习算法的人来说，直接上手快速排序是有点蒙的，所以我们从数组元素分类问题到荷兰国旗问题再到快速排序，一步一步来理解这些排序算法。
荷兰国旗问题
在说荷兰国旗问题之前，我们先引入一个数组partition的问题:
给定一个数组arr，给定一个划定值fixedNum，将这个数组分成两部分，一部分小于等于划分值，另一部分大于这个划分值
对于这道题，我们只需要设置一个指针less就可，指针less指向的元素以及它左边的全部元素都是小于等于划分值的，那右边自然就是大于划分值的元素了
操作流程如图：
具体代码如下：
let arr = [6,9,100,4,1,78,67];
/*
arr:partition的目标数组
fixedNum:划分值
*/
function partition(arr,fixedNum){
let less = -1; //使用一个指针，指针指向的元素以及元素的左边的全部元素都小于等于划分值
//刚开始还未划分，所以为-1
for(let i = 0;i<arr.length;i++){
if(arr[i]<=fixedNum){ //如果元素的值小于等于划分值，那就用less前面的元素跟小于等于划分值的元素交换位置
++less; //先把指针的指向往前面移动
[arr[less],arr[i]] = [arr[i],arr[less]]; //交换两个元素
}else{
continue; //如果大于就直接跳过
}
}
}
partition(arr,56);
console.log(arr);
partition的结果如下：
实际上荷兰国旗问题就是数组的partition稍加改变。
荷兰国旗是由红白蓝3种颜色的条纹拼接而成，如下图所示：
它的意思是将一个数组分成三个部分，一部分是小于划分值，一部分等于划分值，最后一部分是大于划分值，最后返回等于区域范围。
同样地，我们使用指针去解决这个问题，只是这个问题比上面的partition稍微复杂点，所以需要使用两个指针，less和more，less指针的指向以及它左边部分的元素都是小于划分值，more指针的指向以及它右边部分的元素都是大于划分值，
less和more之间的元素就是等于划分值
下面我们以一个例子来理解这个算法
假设存在数组arr = [2,3,1,9,7,6,1,4,5],fixedNum = 4;
less 用于记录小于 4 的区域的右下标，初始为-1，代表不存在
more 用于记录大于 4 区域的左下标，初始为9，代表不存在
L 用于正在遍历的元素的下标，初始值为0
从 arr[L] 即 arr[0] 开始遍历数组
如果 arr[L] < 4, 交换 arr[++ less] 和 arr[L++] 的值
如果 arr[L] > 4, 交换 arr[--more] 和 arr[L] 的值
如果 arr[L] = 4, 不交换，L++，直接遍历下一个值
当 L >= more，退出循环。
这里要注意++i和i++想要表达的意思
下面是实现荷兰国旗问题的代码：
let arr1 = [2,3,1,9,7,6,1,4,5];
function dutchFlag(arr,fixedNum){
let less = -1; //设置less指针
let more = arr.length; //设置more指针
let cur_index = 0; //遍历的元素的索引值
while(cur_index<more){ //当cur_index=more的时候就中止循环
if(arr[cur_index]<fixedNum){ //如果元素的值小于划分值
++less; //指针往前走
[arr[less],arr[cur_index]] = [arr[cur_index],arr[less]]; //交换元素
++cur_index; //索引值往前走
}else if(arr[cur_index]==fixedNum){
++cur_index; //如果相等，只需要索引值往前走
}else{
--more; //指针往后面走
[arr[more],arr[cur_index]] = [arr[cur_index],arr[more]]; //交换元素
}
}
return [less+1,more-1];
}
console.log( dutchFlag(arr1,4));
console.log(arr1);
我们可以看到算法得到正确的区间
快速排序
好了，上面讲了这么多跟快速排序有什么关系呢？经典快速排序要求选择一个基准值pivot，这个基准一般设定为待排数组的最后一个元素，如图：
说到这里，是不是已经反应过来了，这个基准值不就是荷兰国旗问题的划分值吗？
思想是一样的，但是代码略有不同
//快速排序的荷兰国旗
function quickSort_partition(arr,start,end){
/*
arr:需要划分的数组
start:循环的索引值
end:划分数组的基准值的索引值，end指针默认指向最后一个元素，意味着包含最后一个元素
最后排好会置换回去
*/
let less = start-1;
let more = end;
while(start<more){
if(arr[start]<arr[end]){
++less;
[arr[start],arr[less]] = [arr[less],arr[start]];
++start;
}else if(arr[start]==arr[end]){
++start;
}else{
--more;
[arr[more],arr[start]] = [arr[start],arr[more]];
}
}
[arr[more],arr[end]] = [arr[end],arr[more]]; //因为最后一个元素一定是基准值，所以它一定会放在等于区域
//此时要把最后一个元素从大于区域置换出来
return more;
}
function quickSoft(arr,start,end){
if(start<end){ //待排数组只剩下一个元素的时候停止划分
let middleindex = quickSort_partition(arr,start,end); //得到等于区域的最右边的元素
quickSoft(arr,start,middleindex-1); //以这个元素进一步进行划分
quickSoft(arr,middleindex+1,end); //以这个元素进一步进行划分
}
}
quickSoft(arr1,0,arr1.length-1);
console.log(arr1);
经过对数器的验证，这个快速排序算法没有问题
但是基于荷兰国旗的快速排序算法还可以进行改进，上面这种方式是每次partition都是返回等于区域的右边界(其实就是一个元素)，然后再以这个元素进行划分，划分之后得到的左右两部分都进行partition操作，改进之后的快速排序返回的是等于区域(是一个区域)
下面贴上改进后的快速排序的代码：
//改进后快速排序的partition
function quickSort_partition(arr,start,end){
/*
arr:需要划分的数组
start:循环的索引值
end:划分数组的基准值的索引值，end指针默认指向最后一个元素，意味着包含最后一个元素
最后排好会置换回去
*/
let less = start-1;
let more = end;
while(start<more){
if(arr[start]<arr[end]){
++less;
[arr[start],arr[less]] = [arr[less],arr[start]];
++start;
}else if(arr[start]==arr[end]){
++start;
}else{
--more;
[arr[more],arr[start]] = [arr[start],arr[more]];
}
}
[arr[more],arr[end]] = [arr[end],arr[more]]; //因为最后一个元素一定是基准值，所以它一定会放在等于区域
//此时要把最后一个元素从大于区域置换出来
return [less+1,more]; //这次返回的是一个区域
}
function quickSoft(arr,start,end){
if(start<end){ //待排数组只剩下一个元素的时候停止划分
let p = quickSort_partition(arr,start,end); //得到等于区域
quickSoft(arr,start,p[0]-1); //以等于区域进一步进行划分
quickSoft(arr,p[1]+1,end); //以等于区域进一步进行划分
}
}
quickSoft(arr1,0,arr1.length-1);
console.log(arr1);
今天讲述内容到这已经结束啦，在这祝大家圣诞节快乐辽！！！