寻找最小的K个数

寻找最小的K个数

题目描述：查找最小的K个数

题目：输入n个整数，输出其中最小的K个数

例如，输入1、2、3、4、5、6、7、8这8个数字，则最小的4个数字为1、2、3、4。

第一节、各种思路，各种选择

• 要求一个序列中最小的K个数，按照惯有的思维方式，很简单，先对这个序列从小到大排序，然后输出前面的最小的K个数即可；
• 至于选取什么样的排序方法，第一时间应该想到的是快速排序，我们知道，快速排序平均时间复杂度为O(nlogn)，然后再遍历序列中前K个元素输出，即可，总的时间复杂度为O(nlogn + k) = O(nlogn)；——方法一
• 再进一步想想，题目并没有要求要查找的k个数，甚至是后面的n-k个数是有序的，既然这样，咱们又何必对所有的n个数都进行排序呢？

    这个时候，想到了选择或交换排序，即遍历n个数，先把最先遍历到的K个数存入大小为k的数组之中，对这k个数，利用选择或交换排序，找到k个数中的最大数Kmax(Kmax为这K个元素的数组中最大的元素)，用时间为O(k)（你应该知道，插入或选择排序查找操作需要O(k)的时间），后再继续遍历后n-k个数，x与Kmax比较：如果x< Kmax，则x代替Kmax，并再次重新找出K个元素的数组中的最大元素Kmax'；如果x>Kmax，则不更新数组。这样每次更新和不更新数组所用的时间为O(k)或O(0)，整趟下来，总的时间复杂度平均下来为：n*O(k) = O(n*k)；——方法二

• 当然，更好的办法是维护k个元素的最大堆，原理与上述第2个方案一致，即用容量为K的最大堆存储最先遍历的K个数，并假设它们即是最小的K个数，建堆需要O(k)后，有k1）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，x），否则不更新堆。这样下来，总费时O(k+(n-k)*logk) = O(nlogk)。此方法得益于在堆中，查找等各项操作时间复杂度均为logk（不然，就如上述思路2所述：直接用数组也可以找出前k个小的元素，用时O(n*k)）；——方法三
• 按编程之美第141页上解法二的所述，类似快速排序的划分方法，N个数存储在数组S中，再从数组中随机选取一个数X（随机选取枢纽元，可做到线性期望时间O(N)的复杂度），把数组划分为Sa和Sb两部分，Sa<= X <=Sb，如果要查找的K个小的元素小于Sa中的元素个数，则返回Sa中较小的K个元素，否则返回Sa中K个小的元素 + Sb中小的K-|Sa|个元素。像上述过程一样，这个运用类似快速排序的partition的快速选择Select算法寻找最小的K个元素，在最坏的情况下亦能做到O(N)的复杂度。不过值得一提的是，这个快速选择Select算法是选择数组中“中位数的中位数”作为枢纽元，而非随机选择枢纽元；——方法五
• Randomized-Select，每次都是随机选择数列中的一个元素作为主元，在O(n)的时间内找到第K小的元素，然后遍历输出前面的K个小的元素。如果能的话，那么总的时间复杂度为线性期望时间：O(n+k) = O(n)（当n比较小时）；——方法六
• 线性时间的排序，即计数排序，时间复杂度虽能达到O(n)，但是，限制条件太多了，不常用；——方法七
• ”可以用最小堆初始化数组，然后取这个优先队列前k个值。复杂度为O(n)+k*O(logn)“。意思是针对整个数组序列建立最小堆，建堆所用时间为O(n)，然后取堆中的前k个数，即总的时间复杂度为：O(n+k*logn)。——方法八
• 与上述思路7类似，不同的是在对元素数组原地建立最小堆O(n)后，然后提取K次，但是每次提取时，换到顶部的元素只需要下移顶多K次就足够了，下移次数逐次减少（而上述思路7每次提取都需要logn，所有提取K次，思路7需要K*logn，而本思路8只需要K^2）；——方法九（没想明白）

    
    上面的这些思路来自：http://blog.csdn.net/v_JULY_v 
   非常感谢作者，提高了这么多思路。


第二节、C语言实现
    下面的C语言代码，实现了上述的大部分思路，除了快速select算法（主元选择中位数的中位数）和计数排序以及方法九外，没有实现，其他的都已经实现。《已经经过更改了，第一次写的时候，发现代码的实现复杂度并没有达到目的，回过头又看了一遍，发现了这个问题。》

/*
 *        Author: 梦醒潇湘love
 *        Date ：2013/3/9
 *        Email ：9974**[e-mail]
 *
 *        More Infomation:
 *        1> 相关函数之间只有一个空行
 *        2> 不相关函数之间有三个空行，即代表新的方法实现的开始
 *        3> 下面函数的实现，依次是按照上文论述的方法实现的
 *        4> 感谢July提高这么多的思路，非常感谢
 *        5> 代码为梦醒潇湘love实现，若有错误，请指教
 *
 *        求最小的K个数
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#define MAXNUM  1000000        //产生的随机数的个数最大值
#define K  10                //寻找前K个最小的数
#define NUM    20                //从data.txt中读取NUM个数组

//#define DEBUG
//#define DEBUG_RANDOM        //第一次运行时取消注释，再次运行时，为了避免data.txt文件过大，建议注释掉该行
#define DEBUG_QUICKSORT        //快速排序--随机主元、固定主元
#define DEBUG_EXCHANGE //类交换排序
#define DEBUG_MAXHEAP //最大堆
#define DEBUG_QUICKSELECT //快速选择
#define DEBUG_MINHEAP //最小堆

/* 函数功能: 产生随机数，然后写到data.txt文件中
 * 返回值 : 无
 * 参数 : 无
 */
void Random_Num()
{
    long num = 0;
    long i = 1;
    FILE *fp;

    fp = fopen("./data.txt", "a");
    if(fp == NULL)
    {
        fprintf(stderr, "fopen() error: %s\n", strerror(errno));
        return ;
    }

    printf("请输入需要产生的随机数的个数(<= 1000000):\n");
    scanf("%ld", &num);
    if(num > MAXNUM)
    {
        fprintf(stderr, "所输入的产生的随机数个数值过大.\n");
        return;
    }

    srand((unsigned)time(NULL));

    for(i = 1; i <= num; i++)
    {
        long temp = rand() % 1000000;
        fprintf(fp, "%ld ", temp);
    }

    fclose(fp);
}

/*
 * 函数功能：打印前K个最小的元素
 * 返回值 : void
 * 参数    ：
 * @prama a[] 数组a
 * @prama k   前几个最小的元素
 */
void Print(long a[], int k)
{
    int i = 1;
    for(i = 1; i <= k; i++)
    {
        printf("%ld  ", a[i]);
    }
    printf("\n");
}



/*
 * 函数功能: 交换两个数
 * 返回值  ：void
 * 参数       ：
 *    @prama *a 数a
 *    @prama *b 数b
 */
void Swap(long *a, long *b)
{
    long temp = *a;
    *a = *b;
    *b = temp;
}

/*
 * 函数功能: 快速排序中的分治方法-----随机主元
 * 返回值 : 返回的界限
 * 参数    ：
 * @prama a[] 数组a
 * @prama first 数组上标
 * @prama last  数组下标
*/
int Partition_Rand(long a[], int first, int last)
{
    int priot = first + rand() % ( last - first + 1);
    Swap(&a[first], &a[last]);

    long key = a[first];

    while(first < last)
    {
        while(first < last && a[last] >= key)
        {
            last--;
        }
        Swap(&a[first], &a[last]);

        while(first < last && a[first] <= key)
        {
            first++;
        }
        Swap(&a[first], &a[last]);
    }

    return first;
}


/*
 * 函数功能: 快速排序中分治方法-----固定主元
 * 返回值 : 返回的界限
 * 参数    ：
 * @prama a[] 数组a
 * @prama first 数组上标
 * @prama last  数组下标
*/
int Partition(long a[], int first, int last)
{
    long key = a[first];

    while(first < last)
    {
        while(first < last && a[last] >= key)
        {
            last--;
        }
        Swap(&a[first], &a[last]);

        while(first < last && a[first] <= key)
        {
            first++;
        }
        Swap(&a[first], &a[last]);
    }

    return first;
}

/*
 * 函数功能：快速排序算法----随机主元
 * 返回值 : void
 * 参数 :
 * @prama a[] 数组a
 * @prama first 数组上标
 * @prama last  数组下标
 */
void Quick_Rand_Sort(long a[], int first, int last)
{
    if(first < last)
    {
        int priot = Partition_Rand(a, first, last);
        Quick_Rand_Sort(a, first, priot - 1);
        Quick_Rand_Sort(a, priot + 1, last);
    }
}

/*
 * 函数功能：快速排序算法----固定主元
 * 返回值 : void
 * 参数 :
 * @prama a[] 数组a
 * @prama first 数组上标
 * @prama last  数组下标
 */
void Quick_Sort(long a[], int first, int last)
{
    if(first < last)
    {
        int priot = Partition(a, first, last);
        Quick_Sort(a, first, priot - 1);
        Quick_Sort(a, priot + 1, last);
    }
}



/*
 * 函数功能：找到数组a中的最大值，返回最大值所在的下标
 * 返回值  ：返回最大值元素的下标
 * 参数    ：
 * @prama a[] 数组a
 * @prama length 数组长度
 */
int Find_Max(long a[], int length)
{
    int i = 1;
    int max = 1;

    for(i = 1; i <= length; i++)
    {
        if(a[max] < a[i])
        {
            max = i;
        }
    }

    return max;
}

/*
 * 函数功能: 类似于交换排序的方法求取最小K个数
 * 返回值  ：void
 * 参数    ：
 * @prama a[] 数组a
 * @prama k    所求取的最小数的个数
 *
 * 说明：
 *      求取最小的K个数，并没有要求排序，所以，这里每次求取k个元素数组中的最大值的下标*/
void Exchange_Sort(long a[], int k)
{
    int i = 1;

    //先从data.txt中读取K个元素放到数组a中
    FILE *fp;
    fp = fopen("./data.txt", "r");
    if(fp == NULL)
    {
        fprintf(stderr, "fopen() error: %s\n", strerror(errno));
        return;
    }

    while((i <= k) && (fscanf(fp, "%ld", &a[i]) != EOF))
    {
        i++;
    }

    int max = Find_Max(a, k);
    long temp = 0;

    int j = k + 1; // for test
    //while((fscanf(fp, "%ld", &temp) != EOF) && (j <= NUM))    //为了测试，求前20个数字的
    while((fscanf(fp, "%ld", &temp) != EOF))                //求整个文件中数字的最小K个数
    {
        j++;
        if(a[max] <= temp)
        {
            //如果当前数组a中的最大值小于读取的数，则继续
            continue;
        }
        else
        {
            //如果当前数组a中的最大值大于读取的数，则需要交换，重新获得最大值下标
            a[max] = temp;
            max = Find_Max(a, k);
        }
    }

    fclose(fp);
}



/*
 * 函数功能：调整最大堆，以保持最大堆的性质
 * 返回值  ：void
 * 参数 :
 * @prama  a[] 数组a
 * @prama  i    需要调整的节点在数组中的位置
 * @prama len 当前需要调整的长度
 */
void Modify_Heap(long a[], int i, int length)
{
    int left = 2 * i;
    int right = 2 * i + 1;
    int largest = i;

    if(left <= length && a[left] >= a[i])
    {
        largest = left;
    }
    else
    {
        largest = i;
    }
    if(right <= length && a[right] >= a[largest])
    {
        largest = right;
    }

    if(largest != i)
    {
        Swap(&a[i], &a[largest]);
        Modify_Heap(a, largest, length);
    }
}

/*
 * 函数功能: 建立最大堆
 * 返回值  ：void
 * 参数    ：
 * @prama  a[] 数组a
 * @prama len 数组a的长度
 */
void Build_Max_Heap(long a[], int length)
{
    int i;
    for(i = length / 2; i>= 1; i--)
    {
        Modify_Heap(a, i, length);
    }
}

/*
 * 函数功能：利用最大堆求最小k个数
 * 返回值  ：void
 * 参数    ：
 * @prama  a[] 数组a
 * @prama  k  数组a的长度,也是所求的最小数的个数
 */
void Max_Heap_Sort(long a[], int k)
{

    FILE *fp;

    fp = fopen("./data.txt", "r");
    if(fp == NULL)
    {
        fprintf(stderr,"fopen() error: %s\n", strerror(errno));
        return;
    }

    //先读取k个元素
    int i = 1;
    while((i <= k) && (fscanf(fp, "%ld", &a[i]) != EOF))
    {
        i++;
    }

    //建立最大堆
    Build_Max_Heap(a, k);

    //寻找最小的k个数哦
    long temp = 0;
    int j = k + 1; // for test
    //while((j <= NUM) && (fscanf(fp, "%ld", &temp) != EOF)) //方便测试，文件中的前20个数据
    while((fscanf(fp, "%ld", &temp) != EOF))    // 整个文件的
    {
        j++;
        if(temp < a[1])
        {
            a[1] = temp;
            Modify_Heap(a, 1, k);
        }
    }

    fclose(fp);
}



/*
 * 函数功能：快速选择第k小元素
 * 返回值  ：第k小元素
 * 参数    ：
 * @prama  a[] 数组a
 * @prama  first 数组上标
 * @prama  last  数组下标
 * @prama  i     第i小元素
 *
 * 时间复杂度：
 *     平均时间复杂度：O(n)
 *     最坏时间复杂度：O(n^2)
 */
long Quick_Select(long a[], int first, int last, int i)
{
    if(first == last)
    {
        //return a[first];
        return first;
    }

    long p = Partition_Rand(a, first, last); //这里应该选用随机主元分治方法
    long k = p - first + 1;
    if(i == k)
    {
        //return a[p];
        return k;
    }
    if(i < k)
    {
        return Quick_Select(a, first, p - 1, i);
    }
    else
    {
        return Quick_Select(a, p + 1, last, i - k);
    }
}



/*
 * 函数功能: 调整最小堆，使其满足最小堆的性质
 * 返回值 : void
 * 参数 :
 *     @prama  a[] 数组a
 *     @prama  i     调整第i个节点
 *     @prama  length数组a的长度
 *
 * 时间复杂度为：O(logn)
 */
void Modify_Min_Heap(long a[], long i ,long length)
{
    long left = 2 * i;
    long right = 2 * i + 1;
    long least = i;

    if(left <= length && a[left] <= a[i])
    {
        least = left;
    }
    else
    {
        least = i;
    }
    if(right <= length && a[right] <= a[least])
    {
        least = right;
    }
    if(least != i)
    {
        Swap(&a[i], &a[least]);
        Modify_Min_Heap(a, least, length);
    }
}

/*
 * 函数功能：建立最小堆
 * 返回值  ：void
 * 参数    ：
 * */
void Build_Min_Heap(long a[], long length)
{
    int i = 1;
    for(i = length/2; i>= 1; i--)
    {
        Modify_Min_Heap(a, i, length);
    }
}

/*
 * 函数功能：最小堆排序
 * 返回值 : void
 * 参数    ：
 * @prama a[] 数组a
 * @prama len 数组a长度
 */
void Min_Heap_Sort(long a[], long length)
{
    int i = 0;

    Build_Min_Heap(a, length);

#ifdef DEBUG
    for(i = 1; i <= length; i++)
        printf("%ld  ", a[i]);

    printf("\n");
#endif

    for(i = length; i >= 1; i--)
    {
        Swap(&a[1], &a[i]);
        Modify_Min_Heap(a, 1, i - 1);
    }
#ifdef DEBUG
    for(i = 1; i <= length; i++)
        printf("%ld  ", a[i]);

    printf("\n");
#endif
}

/*
 * 函数功能：通过建立的最小堆，求得最小的K个数
 * 返回值  ：void
 * 参数    ：
 * @param  a[] 数组a
 * @param  length 数组的长度
 * 时间复杂度：
 * O(n) + k*logn
 */
void Min_Heap_Find(long a[], long length)
{
    int i = 1;

    //建立最小堆
    Build_Min_Heap(a, length);

    int min = a[1];

    printf("%d   ", min);

    //for(i = 2; i <= K && length > 0; i++, length--)
    for(i = 2; i <= K; i++)

    {
        a[1] = a[length];
        Modify_Min_Heap(a, 1, length);
        printf("%d  ", a[1]);
    }
}


int main(int argc, char **argv)
{
    int first = 1;
    int last = NUM;

#ifdef DEBUG_RANDOM
    //产生随机数，然后将产生的随机数写入到data.txt文件中
    Random_Num();
#endif

    //从data.txt中读取20个数据
    long a[NUM + 1] = {0};
    int i = 1;
    FILE *fp = NULL;

    fp = fopen("./data.txt", "r");
    if(fp == NULL)
    {
        fprintf(stderr, "fopen() error: %s", strerror(errno));
        return -1;
    }

    while((fscanf(fp, "%ld", &a[i]) != EOF) && (i <= NUM))
    {
        i++;
    }
    printf("从data.txt中读取的NUM个数为:\n", NUM);
    for(i = 1; i <= NUM; i++)
    {
        if( i % 11 == 0)
        {
            printf("\n");
        }
        printf("%ld ", a[i]);
    }
    printf("\n\n");

    fclose(fp);

#ifdef DEBUG_QUICKSORT
    //用快速排序方式获得最小的K个元素（为了方便测试，从data.txt前20个元素中选最小K个）
    long b[ NUM + 1];
    long bc[NUM + 1];
    first = 1;
    last = NUM;

    memcpy(b, a, sizeof(a));

    Quick_Rand_Sort(b, first, last);

    printf("通过快速排序---随机主元找到最小的%d个数为：\n", K);
    Print(b, K);

    memcpy(bc, a, sizeof(a));
    Quick_Sort(bc, first, last);
    printf("\n通过快速排序---固定主元找到最小的%d个数为：\n", K);
    Print(bc, K);
#endif

#ifdef DEBUG_EXCHANGE
    //用类似于交换排序的方式获得最小的K个元素
    //这里所求的没有进行排序，只是每次找到k个元素中的最大值
    long c[NUM + 1] = {0};

    Exchange_Sort(c, K);

    printf("\n通过类似交换排序的方法找到最小的%d个数为：\n", K);
    Print(c, K);
#endif

#ifdef DEBUG_MAXHEAP
    //用最大堆方式获得最小的K个元素(为了方便测试,从data.txt前20个元素中选最小的)
    long d[NUM + 1] = {0};

    Max_Heap_Sort(d, K);

    printf("\n通过最大堆排序的方法找到最小的%d个数为：\n", K);
    Print(d, K);
#endif

#ifdef DEBUG_QUICKSELECT
    //用快速选择方法获得最小K个数
    long f[NUM + 1] = {0};

    memcpy(f, a, sizeof(a));

    printf("\n通过快速选择的方法找到最小的%d个数为:\n", K);

    //这个有序
    //for(i = 1; i <= K; i++)    //Quick_Sort的返回值不一样
    //{
    //    printf("%ld  ", Quick_Select(f, first, last, i));
    //}

    //这个无序
    long num = Quick_Select(f, first, last, K);
    for(i = 1; i <= K; i++)
    {
        printf("%ld  ", f[i]);
    }
    printf("\n");


#endif

#ifdef DEBUG_MINHEAP
    //最小堆
    long g[NUM + 1];

    memcpy(g, a, sizeof(a));

    printf("\n通过最小堆的方法找到最小的%d个数为:\n", K);
    Min_Heap_Find(a, NUM);
    /*
    Min_Heap_Sort(g, (long)NUM);
    long  tmp = 1;
    long j = 1;
    for(j = NUM; j >= 1; j--)
    {
        printf("%ld  ", g[j]);
        if(tmp == K)
        {
            break;
        }
        tmp++;
    }
    */
    printf("\n");
#endif

    return 0;
}

    代码如下所示。  测试结构如下所示。

    

    不知道怎么传文件，上述代码可能太长，如果看起来麻烦请谅解。
    另外种没有实现的（计数排序除外，这个比较简单），等搞明白后再添加。
    上面代码是自己实现的，肯定有错误或者代码不规范之处，敬请纠正和指教。
    谢谢。

   

   哈，终于把这个算是弄得相对清楚了，关于各种实现方式的时间复杂度分析，再好好的看看。
    一个愉快的晚上，有所收获。

    感谢今天。





                                                                                                        梦醒潇湘love
                                                                                                      2013-03-09  20:41