荷兰国旗算法

逆序对:如果列表中左边的数比右边的大,称为逆序对
或者说右边的数比左边小

如果求相邻的那么直接遍历比较即可

如果不相邻也算,那么可以利用拆分排序(左边无序,右边有序(提高查询效率,二分法查等于他或者比他大一点数为位置))
第一次拆为2个数组左边是从头到倒数第二位,末尾一个
第二次左边头到N-2,右边N-2和n-12个有序的
…第X次左边头到N-X,右边倒数的X个数字(N-X,N有序)

荷兰国旗:
一个数组arr,将大于num的放在右边,小于num的放在左边
实际上就是粗排序,声明2个临时数组,左边和右边,大于的放在右边,小于的放在左边,这种方案时间复杂度0(N),但是额外空间复杂度不好

减少额外空间复杂度,可以考虑数组中直接不符合的交换即可
声明3个int变量l=0,r=len-1,mid=r+(r-l)>>1
遍历数组,获取0-mid中大于num的角标集合(有序,正序)Z
和mid-尾部的小于num的角标集合(有序,正序)Y
对比ZY长度,遍历长度小的,2者交换

处理剩余的,Z头部还处在比num大的X个,那么和mid左边的x个交换,
尾部剩余比num小的和mid右边的换

更优:不借助临时数组存储角标,遍历中直接交换

从头开始遍历:遍历过程中发现当前角标i>num,从尾部遍历数组(范围尾部到i看是否有小num的,如果有没有就做到前面小于=后面大于)

荷兰国旗:
如果要做到小于在前面,等于在中间,大于在后面
头部遍历,
1.碰见大于,找尾部倒序的第一个大于等于的交换,交换,记录尾部游标end,找不到就代表当前完成了排序
2.碰见等于,从smallInedx(第一次默认当前位置+1,后续对比smallIndex和当前开始)开始找到end,第一个小于交换,记录小于开始位置smallInedx(方便下次直接从此处寻找,如果节点碰撞代表后面没有小的了,后面不找了,next)
3,小于直接next

实现如下:
/*
* 小于num的在左边,等于中间,大于放右边
* */

public int[] sLeftAndBRight(int[] a, int num) {//边界校验省略//完成标志,碰到大于后面找不到小于等于即视为成功boolean successFlag = false;//尾部查找小于等于的起始位置int endSmall = a.length - 1;//碰到等于时,找后面第一个小于num的位置int smallIndex = 0;for (int i = 0; i < a.length; ) {int tmp = a[i];//大于找从尾部找小于等于的交换,停在原地,处理交换过来的(交换过来的可能是等于)if (tmp > num) {for (int j = endSmall; j > i; j--) {int tmpEnd = a[j];if (tmpEnd <= num) {swap(a, i, j);endSmall = j - 1;break;}//如果之后无小于等于那么直接跳出if (j == i + 1) {successFlag = true;}}} else if (tmp == num) {//等于,从当前角标向后到尾部endSmall范围内找第一个小于当前的smallIndex = smallIndex > i + 1 ? smallIndex : i + 1;if (smallIndex <= endSmall) {for (int j = smallIndex; endSmall >= j; j++) {int tmpEnd = a[j];if (tmpEnd < num) {swap(a, i, j);smallIndex = j + 1;break;}//如果范围内无,对比下一个if (j == endSmall) {i++;}}//如果smallIndex>end代表中间已经无小于的了,i++} else {i++;}if (endSmall <= i) {break;}} else {//小于直接跳过,nexti++;}if (successFlag) {break;}}for (int i = 0; i < a.length; i++) {System.out.print(a[i] + ",");}return a; }

总结

以上是生活随笔为你收集整理的荷兰国旗算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。