返回顶部

收藏

找第K大的数||找最大的K个数(快速排序思想)

更多

下面是找第K大数的算法,利用了快速排序的思想,算法复杂度为O(N)找到第K大的数后,扫描一遍数组,即可找出最大的K个数,复杂度为O(N),但找出的数是未排序 好的。若要求找出的k个数是排序好的,可以用堆的方法,具体见http://zhedahht.blog.163.com/blog/static/25411174 20072432136859/

[C/C++]代码

#include <iostream>

using namespace std;

int Partition(int *L,int low,int high)
{

    int pivotkey=L[low];
    int i = low, j = high+1;

    while(i<j)
    {
        while (L[++i]<pivotkey && i<=high);
        while (L[--j]>pivotkey);

        if (i<j){
            int temp = L[i];
            L[i] = L[j];
            L[j] = temp;
        }
    }

    L[low] = L[j];
    L[j]=pivotkey;

    return j;

}

int NSort(int *L,int low,int high,int k)
{

    int mid;

    if(low<=high)
    {
        mid=Partition(L,low,high);
        if(high-mid+1==k)return L[mid];
        else if(high-mid+1<k)return NSort(L,low, mid-1, k);
        else return NSort(L,mid+1, high,k);
    }

    return 0;

}

int main()
{

    int L[10]={11,49,53,86,22,27,98,88,91,100};

    for (int i=1; i<=10; i++){
        int ith=NSort(L,0,9,i);
        printf("%d\n", ith);
    }

    return 0;

}

标签:排序,快速排序

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. 第七星尘 发表 2013-01-10 18:12:39 PHP实现的快速排序
  2. admin 发表 2013-08-03 15:34:09 jquery table 排序
  3. 张映 发表 2014-02-10 07:12:46 json 数据 添加 删除 排序
  4. 博主 发表 2009-08-26 04:00:00 归并排序,比较好理解的一种排序
  5. litianfeiying 发表 2014-08-08 17:05:48 彻底搞定堆排序
  6. 博主 发表 2013-11-06 00:00:00 二分合并排序
  7. 博主 发表 2009-05-27 16:34:00 R语言中matrix的排序
  8. damon 发表 2015-05-12 06:57:10 php函数array_multisort 和 uasort为数组排序的区别
  9. 博主 发表 2015-05-27 15:31:04 Objective-C 对字符串数组排序
  10. 博主 发表 2015-07-19 10:07:23 常见排序算法之简单选择排序
  11. linux@linux.cn (linu 发表 2015-10-03 01:18:45 八大排序算法的 Python 实现
  12. 博主 发表 2014-09-03 00:00:00 Effective STL 学习笔记 31:排序算法

发表评论