锐客网

  1. 首页 > it技术 > >

荷兰国旗问题(分三块）

在说 “荷兰国旗” 问题之前，首先来看一个引例。

  • 给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1）,时间复杂度 O(N）
分析： 设定一个小于等于区，从0开始比较，如果当前数字小于等于num ，让其与小于等于区的下一个值做交换，再将小于等于区扩大一位，直到将所有的数字都与num进行过比较。重新排好的数组就是所求的数组。如下给出示意过程：
荷兰国旗问题(分三块）
文章图片

荷兰国旗问题(分三块）
文章图片

最终就可以得到一个在num左边所有的数都小于等于num右边都大于num。
这个过程实际上可以看成是小于等于区域在推着大于等于区域向右走，而当遇到小于等于num的数时，进行的操作是，与大于区域的第一个数字做交换，这听起来就有些像堆排序的heapify过程。
荷兰国旗问题（直观的“分三块”的问题） —— 有了上面这些问题的基础，荷兰国旗问题就会好想一些。
  • 给定一个数组arr,和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
分析： 上一个题目要求将数组分成两块，而这个是将数组分成三块。上一个问题是在左边设置了一个大于等于区，这个问题可以在左边设置一个小于区，在右边设置一个大于区，不断向中间逼近，最终中间就是相等的数字。操作过程也和上一个问题是完全一样的。如下过程所示：
荷兰国旗问题(分三块）
文章图片

荷兰国旗问题(分三块）
文章图片

这样就将数组分成了不同条件的三块。以下给出算法代码：
  1. 在arr[L…R]范围上，根据数字p分块
  2. 小于p的在左边 等于p的在中间 大于p的在右边
  3. 返回值含义： 一定会返回一个长度为2的数组，等于区域的左边界和右边界（也就是相等区域的边界范围 ）。
int* partition(int arr[],int L,int R,int p) { int less=L-1; //小于区的右边界 int more=R+1; //大于区的左边界 int index=L; while(index

4.若无等于区域，此时返回值，左边界大于右边界。
荷兰国旗问题(分三块）
文章图片

将这个方法与快速排序的查找枢轴值的方法进行比较，看看有什么异同。 快速排序就是一个递归的此过程。在一定区域内进行划分，最终整体都有序。
——————————————【快速排序】· 学习笔记
还可以优化直接插入排序
  • 将数组分成两部分，前半部分有序，后半部分无序，不断地将无序区域的数字放入有序区域，插入的时候可以利用前半部分有序的特点，二分插入排序。例如如下过程：
荷兰国旗问题(分三块）
文章图片

【荷兰国旗问题(分三块）】在插入的时候，先通过二分查找确定要插入的位置，再进行插入即可。

    推荐阅读


    上一篇：c语言|作业day2020-3-29

    下一篇：gitlab学习(21)---创建和接受合并请求 Merge Requests