荷兰国旗问题和快速排序

大家好，我是星期一。上几篇文章一直在讲归并排序，归并排序也差不多。今天我们来谈谈快速排序。一、荷兰国旗的问题1、荷兰国旗的问题是什么？并且随机生成一个新的图形，新的图形可能如下图所示，但不只是这种情况：要求是：将这些条纹按颜色排列，红色的在上，而白色的在中间部分，蓝色的在下半部分，我们称这类问题为荷兰国旗问题。2.荷兰国旗问题的抽象我们将荷兰国旗问题抽象成一个数组如下：给定一个整数数组和一个值M（原数组中存在），要求将数组中小于M的元素放入数组左边，等于M的元素放在数组中间，大于M的元素放在数组右边，最后返回一个整型数组，只有两个值，0的位置是等于M的数组部分的左下标值，1位置等于M的数组部分的右下标值。进一步抽象成更一般的形式如下：给定数组arr，其中的数范围[l,r]（当然默认是[0-arr.length-1]），小于arr[r]（这里直接取数组最右边的值进行比较）放在数组左边，等于arr[r]放在数组中间，大于arr[r]就放在数组右边。最后返回等于arr[r]的左右下标值。3.解的思路是定义一个小于面积，一个大于面积；遍历数组，与arr[r]逐一比较，（1）小于arr[r]，与下一个小于该区域的位置交换，将当前位置向后移动；(2)等于arr[r]，当前位置直接向后移动；(3)大于arr[r]，与前一个大于面积的位置交换，当前位置不变（交换到这个位置的数还没有比较过，所以不动）。遍历后arr[r]与大于区最左边的位置交换。最后返回。此时小于区域的最后一个位置，大于区域的位置，即最后一个左右下标值等于arr[r]。4.详细参考代码/***荷兰国旗问题**

*将数组arr中[l,r]范围内小于arr[r]的数字放到数组最左边，等于arr[r]到数组中间，比arr[r]大，放在数组最右边**@return返回等于arr[r]的左右下标值*/publicstaticint[]netherlandsFlag(int[]arr,intl,intr){if(l>r){returnnewint[]{-1,-1};}if(l==r){returnnewint[]{l??,r};r/]arr[右边界从L的左位开始intless=l-1;//大于arr[r]的左边界，从r开始，即当前右边界已经有arr[r]intmore=r;//当前正在比较的索引intindex=l;//不能与大于arr[r]的左边界碰撞while(index=r){返回；向上（即数组最右边的位置）//这一步是保证快排时间复杂度为O(N*logN)的关键，否则快排时间复杂度为O(N^2))swap(arr,l+(int)((r-l+1)*Math.random()),r);//将数组分成小于、等于、大于的左、中、右三块arr[r]int[]equalArea=netherlandsFlag(arr,l,r);//此时等于面积的值已经在最终排序结果的位置//递归排序左半部分processRandom(arr,l,equalArea[0]-1);//递归排序右半边processRandom(arr,equalArea[1]+1,r);}publicstaticvoidswap(int[]arr,inti,intj){inttmp=arr[i];arr[i]=arr[j];arr[j]=tmp;}