从一组数中寻找第k大的元素

 2016/08/23
算法目的是希望取得一组数中，从大到小排序第k位(这里默认k＝N/2)的元素。以下程序通过两个算法实现同样的功能。还有第三种更好的方法等待补充。
//
//  算法目的是希望取得一组数中，从大到小排序第k位(这里默认k＝N/2)的元素。
//  以下程序通过两个算法实现同样的功能
//
//  算法一：设置大小位k的数组，将头k个元素存入数组中，进行排序。然后再一个个读入剩下的
//  进行比较，如果比数组中第k个元素的值大，那么按顺序插入数组中，舍弃原本的第k位元素。
//  在读入所有元素之后返回第k位元素。
//
//  算法二：简单粗暴地将所有元素读入数组，然后通过冒泡法进行数组的排序，返回第k位元素。

#include <iostream>
#include <vector>
#include <time.h>
using namespace std;

// 将数字按从大到小顺序插入顺序数组
void insertNum(vector<int> & array, int num) {
    int index = 0;
    for (; index < array.size(); index++) {
        if (num > array[index]) {
            for (int i = (int)array.size() - 1; i != index; i--) {
                array[i] = array[i-1];
            }
            array[index] = num;
        }
    }
}

// 计算运行时间
double runTime(clock_t start, clock_t finish) {
    return 1000 * (double)(finish - start)/CLOCKS_PER_SEC;
}

int main(int argc, const char * argv[]) {
    
    clock_t start,finish;
    double totaltime;
    
    cout << "请输入数字的总个数" << endl;
    int N;
    cin >> N;
    
    int k = N / 2;
    
    vector<int> array(k);
    
    // function one
    //
    start = clock();
    
    int index = 0;
    while (index < k) {
        array[index] = rand();
        index++;
    }
    
    for (int i = 0; i < array.size() - 1; i++) {
        for (int j = i+1; j < array.size(); j++) {
            if (array[i] < array[j]) {
                swap(array[i], array[j]);
            }
        }
    }
    
    for (; index < array.size(); index++) {
        int num = rand();
        if (num > array[k-1]) {
            insertNum(array, num);
        }
    }
    
    finish = clock();
    totaltime = runTime(start, finish);
    cout<<"\n算法1的运行时间为"<<totaltime<<"毫秒！"<<endl;
    
    
    array.resize(N);
    
    // function two
    start = clock();
    
    for (int i = 0; i < N; i++) {
        array[i] = rand();
    }
    
    for (int i = 0; i < array.size() - 1; i++) {
        for (int j = i+1; j < array.size(); j++) {
            if (array[i] < array[j]) {
                swap(array[i], array[j]);
            }
        }
    }
    
    finish = clock();
    totaltime = runTime(start, finish);
    cout<<"\n算法2的运行时间为"<<totaltime<<"毫秒！"<<endl;
    
    return 0;
}
CATALOG
