快速选择算法,是一种能在大致O(N)的时间内选取数组中第k大或者k小的算法.其基本思路与快速排序算法类似,也是分治的思想.

其实这个算法是个基础算法,但是不常用,所以今天编的时候错了POJ2388,才有了这篇文章.

  1. 执行Partition算法(就是那个快排里将区间内所有数划分为小的一部分和大的一部分的过程)
  2. 判断第k大的数是在小的部分还是大的部分
  3. 递归,直到区间足够小,返回结果

下面几段代码,尤其要注意的是

while(i<j)

还是

while(i<=j)

程序1:

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
Program:快速选择算法样例
Author:Comzyh
*/
#include <cstdio>
int array[10000],temp;
int N,K;
int QuickSelect(int arr[],int b,int e,int k);
int main()
{
     scanf("%d%d",N,K);
     for (int i=1;i<=N;i++)
          scanf("%d",array[i]);
     printf("The k th :%d\n",QuickSelect(array,1,N,K));
}
int QuickSelect(int arr[],int b,int e,int k)
{
     int i=b,j=e,mid=arr[(i+j)>>1];
     while (i<=j)//注意,小于等于
     {
          while (arr[i]<mid)i++;
          while (arr[j]>mid)j--;
          if (i<=j)
          {
               temp=arr[i];arr[i]=arr[j];arr[j]=temp;
               i++;j--;
          }
     }
     if (b<j  k<=j)return QuickSelect(arr,b,j,k);//分治
     if (i<e  k>=i)return QuickSelect(arr,i,e,k);
     return arr[k];//如果不属于任何一方,就结束,返回
}

不过,就是这样一个简单的算法,今天也出了点错误,本来我是用用了多少年的快排改的,就像下面这段代码

程序2:

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
Program:快速排序算法样例
Author:Comzyh
*/
#include <cstdio>
int array[10000],temp;
int N,K;
int QuickSort(int arr[],int b,int e);
int main()
{
     scanf("%d",N);
     for (int i=1;i<=N;i++)
          scanf("%d",array[i]);
     QuickSort(array,1,N);
     for (int i=1;i<=N;i++)
          printf("%d\n",array[i]);
}
int QuickSort(int arr[],int b,int e)
{
     int i=b,j=e,mid=arr[(i+j)>>1];
     while (i<j)//注意,小于
     {
          while (arr[i]<mid)i++;
          while (arr[j]>mid)j--;
          if (i<=j)
          {
               temp=arr[i];arr[i]=arr[j];arr[j]=temp;
               i++;j--;
          }
     }
     if (b<j)QuickSort(arr,b,j);
     if (i<e)QuickSort(arr,i,e);
}

几乎一模一样,但是下面这样写就是是错的

程序3:

 
1
2
3
4
5
6
7
8
9
10
11
int QuickSelect(int arr[],int b,int e,int k)
{
     int i=b,j=e,mid=arr[(i+j)>>1];
     while (i<j)//注意,小于
     {
          ....
     }
     if (b<j  k<=j)return QuickSelect(arr,b,j,k);//分治
     if (i<e  k>=i)return QuickSelect(arr,i,e,k);
     return arr[k];//如果不属于任何一方,就结束,返回
}

而这样写是对的

程序4:

 
1
2
3
4
5
6
7
8
9
10
11
int QuickSelect(int arr[],int b,int e,int k)
{
     int i=b,j=e,mid=arr[(i+j)>>1];
     while (i<j)//注意,小于
     {
          ....
     }
     if (b<j  k<=j)QuickSelect(arr,b,j,k);//没有Return
     if (i<e  k>=i) QuickSelect(arr,i,e,k);
     return arr[k];//如果不属于任何一方,就结束,返回
}
快速排序已经模板化了,原理也清楚,实现也正确,但是,有些细节有可能理解不到位,所以才会出错.
下面分析这种情况出现的原因:
出错其实是一种极端情况,即向右扫描的指针i和向左扫描的指针j重合于k位置;.(这种巧合真的不大常见,但是还是让我给碰上了,如果没碰上,估计我的错误也不会被纠正.)
 
假设有一个数组arr[]={1,4,3,6,3,2},当k=4时;(下标从1算起,下同)
快速选择算法细节演示
首先,按照Partition算法,先交换arr[2]=4 和arr[6]=2,变成arr[]={1,2,3,6,3,4}
然后i=3,j=5 如图(1)交换,i++,j–后,i=j=k=4 如图(2)
  • 按照错误的方法(程序3)执行(如图(3)),函数会在闭区间[1,4]中寻找答案,这样是错误的,因为arr[5]=3不在这个区间内
  • 按照程序1中的方法执行,j会自减1,因为不满足i<=j(i=4,j=3)然后会在闭区间[4,6]中递归(如图(4)),寻找答案,这样是正确的
  • 按照程序4中的方法执行,QuickSelect(1,4,4)执行完之后arr[4]=6,这样,再执行QuickSelect(4,6,4)时,程序会返回正确的结果

最新文章

  1. python处理空格脚本
  2. Ubuntu16.04使用阿里云镜像安装Mongodb
  3. [ZigBee] 14、Zigbee无线通信前奏——BasicRF 简单无线点对点传输协议
  4. SharePoint 2013 新建项目字段自动加载上次保存值
  5. ExtJS学习之路第四步：看源码，实战MessageBox
  6. Android 编程下去除 ListView 上下边界蓝色或黄色阴影
  7. mysql字符集基础知识梳理
  8. Altium Designer 覆铜时过孔连接形式的设置——只将过孔连接设置为Direct Connect
  9. 对话框(alert,prompt，confirm,showModalDialog)
  10. vc中主线程等待子线程退出的方法
  11. NYOJ-791 Color the fence （贪心）
  12. Counting Intersections
  13. JS模式---发布、订阅模式
  14. PhiloGL学习（3）——程序员的法宝—键盘、鼠标
  15. qt实现一个简单的计算器
  16. 【Luogu1879】玉米田（状态压缩，动态规划）
  17. Vue双向数据绑定原理
  18. BZOJ.1430.小猴打架(Prufer)
  19. php基础面试题：
  20. JS高级心法——作用域链

热门文章

  1. spfa模板+讲解
  2. java反序列化字节转字符串工具
  3. Linux文件系统概述二
  4. mysql 备份解密脚本
  5. appIcon
  6. 杭电 1159 Common Subsequence
  7. 解决php7.3 configure: error: off_t undefined
  8. nginx+django+uwsgi+https 配置问题点
  9. 【11】specified value,computed value,used value计算方法
  10. Head First HTML5 Programming笔记--chapter2 介绍Javascript和DOM