一步一步写算法(之挑选最大的n个数)

《一步一步写算法(之挑选最大的n个数)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一步一步写算法（之挑选最大的n个数）【声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing@163.com】   从一堆数据中挑选n个最大的数，这个问题是网上流传的比较广的几个问题之一。具体来说，它的意思就是：假设我们有100个数据，我们需要挑选出最大的n个数据(n<100)，那么有没有办法实现这样一个目标呢？在这里，我想从排序的角度看看有没有什么办法可以实现这样一个目标。   在前面的博客当中，我们实现的排序算法有下面几种：   （1） 冒泡排序、插入排序、希尔排序   （2） 快速排序   

2、（3） 合并排序   （4） 堆排序   （5） 选择排序   （6） 基数排序   那么是不是这8种算法都适合今天的题目呢？我简单的对它们进行了分析和归类：   a）不到最后无法求出最大数据的算法，（插入算法，合并算法，基数排序）   这些算法的特点就是可以保证局部的数据基本有序，但是无法保证全局的数据有序。在全部数据得到正确地排序之前，没有人知道最大的数据是什么。所以针对这个题目而言，要想知道最大的n个数，那就等于要对所有的数据全部排序一遍。   b）每次求出一个最大的数据，依次类推，直到所有的数据都已经排序。（冒泡

3、排序、希尔排序、选择排序、堆排序）   这些算法的特点就是，排序的时候，所有的数据都是按照从大到小排列出来的。按照冒泡排序来说，首先我们选出最大的数据，然后是第二大的数据，依次类推，直到第n大的数据找到为止。堆排序也是这样，我们在构建堆之后，也是每次从堆顶获得一个数据，不断调整堆，再接着获得第二大、第三大......第n大的数据的。我们以冒泡排序为例，看看这一次的算法应该怎么写？1.void find_n_max_number(int array[], int length, int number)2.{3.    in

4、t inner ;4.    int outer;5.    int median;6.  7.    if(NULL == array 

5、

6、 0 == length)8.        return;9.  10.    if(number > length)11.        return;12.  13.    for(outer = length -1; outer > (length - 1 - number); outer --){14.        for(inner = 0; inner < oute

7、r; inner ++){15.            if(array[inner] > array[inner +1]){16.                median = array[inner];17.                array[inner]  = array[inner + 1];18.                array[inner + 1]= median;19.            }1.        }2.    }3.}   c）迭代搜索，首先对数据进行分类，小于于数组第

8、一个数据的排在左边，大于的排在右边。如果右边的数据小于n，为m，那么在左边数组继续寻找剩下的（n-m）个数据；如果右边的数据大于n，那么在右边的数据继续寻找。（快速排序）   不知道上面的解释说明白了没，没有清楚的同学可以看一看下面这个代码。1.int partion(int array[], int start, int end, int swap[])2.{3.    int loop;4.    int left = 0;5.    int right = end - start;6.    int value =

9、 array[start];7.  8.    for(loop = start +1; loop <= end; loop++){9.        if(array[loop] < value)10.            swap[left ++] = array[loop];11.        else12.            swap[right --] = array[loop];13.    }14.    swap[left] = value;15.    memmove(&array[start]

10、, swap, sizeof(int) * (end - start +1));16.    return left + start;17.}18.  19.void _quick_sort(int array[], int start, int end, int swap[], int number)20.{21.