快速选择算法(时间复杂度o(n)

选择问题是求一个n个数列表的第k个最小元素的问题。 中位数：百度百科定义如下：        对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，通常取最中间的两个数值的 平均数 作为中位数。 中轴p(列表中的第一个元素) Lomuto划分       考虑一个数组，或者更一般的一个字数组A[l...r](0≤l≤r≤n-1),该数组由连续的3段组成。这3段按顺序排在中轴p的后面：一段为已知小于p的元素，一段为已知大于或等于p的元素，还有一段未同p比较过的元素。这些段可以为空，在算法开始时，前两段通常是空的。 在i= l+1开始，算法从左到右扫面字数组A[l...r],并保持这个结构直到划分完成。在每一次迭代中，它把未知段中的第一个元素与中轴p进行对比。如果A[i] >= p,则只要i+1就扩大了大于等于p元素的段，而同时缩小了未处理的段。 <p,则小于p元素的段需要扩大,这将通过s+1来实现，s指向第一段中最后一个元素，再交换a[i]与a[s],然后i+1,使i指向未处理段中的第1个元素。 在未处理段为空时，算法把中轴与a[s]交换，就得到一个我们想要的划分（快排的另一种划分方法）;<p，则小于p元素的段需要扩大，这将通过s+1来实现，s指向第一段中最后一个元素。再交换a[i]与a[s],然后i+1。使之指向缩小后的未处理段的第一个元素。在未处理元素为空时，算法把中轴与a[s]交换，获得了一个我们所要求的划分。 数组中第k小元素的快速选择算法的c代码如下： 

点击(此处)折叠或打开

#include<stdio.h> #include<stdlib.h> #define swap(t,x,y) (t = (x),x = (y),y = (t)) int lomutoPartition(int *a,int lo,int hi) {     int s = lo;     int i = lo+1;     int p =a[lo];     int temp = 0;     for (i = lo+1;i < hi;i++)     {         if (a[i] < p)         {             s = s+1;             swap(temp,a[i],a[s]);         }     }     swap(temp,a[lo],a[s]);     return s; } int quickselect(int *a,int lo,int hi,int k) {              int s = lomutoPartition(a,lo,hi);         if (lo+k-1 == k) return a[s];         else if (lo+k-1 < s) quickselect(a,lo,s-1,k);         else quickselect(a,s+1,hi,lo+k-s-1);//这里lo别忘记写      } int main() {     int a[4] = {1,2,3,4};     int result = quickselect(a,0,3,2);     printf("%d\n",result);     return 0; } 具体见下一篇文章 </p，则小于p元素的段需要扩大，这将通过s+1来实现，s指向第一段中最后一个元素。再交换a[i]与a[s],然后i+1。使之指向缩小后的未处理段的第一个元素。在未处理元素为空时，算法把中轴与a[s]交换，获得了一个我们所要求的划分。 <script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"16"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];</script> 阅读(511) | 评论(0) | 转发(0) | 0

上一篇：linux下非阻塞的tcp研究

下一篇：求数组中最小的k个数

相关热门文章 test123编写安全代码——小心有符号数...使用openssl api进行加密解密...一段自己打印自己的c程序...彻底搞定C语言指针详解-完整版... 给主人留下些什么吧！~~ 评论热议