|
|
這個問題屬于常見問題了，我的辦法是采用堆。
截取STL中的partial_sort算法的實現(xiàn)：
 template <class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last, T*, Compare comp) {
make_heap(first, middle, comp);
for (RandomAccessIterator i = middle; i < last; ++i)
if (comp(*i, *first))
__pop_heap(first, middle, i, T(*i), comp, distance_type(first));
sort_heap(first, middle, comp);
}
上面這個函數(shù)是對一個序列進行部分排序，排序之后，在first，middle之間的元素有序。
它的做法首先將原始的first，middle中的數(shù)據(jù)生成一個堆，然后遍歷之后的數(shù)據(jù)，如果比前面的元素中最大的元素大，就把最小的元素刪除插入這個新的元素，這個過程是lg(middle - first），最后進行堆排序。
不是每個元素都需要重新調(diào)整堆，所以最壞的情況時間復(fù)雜度是n * lg(middle - first)。
類似的，可以根據(jù)這個算法并且使用堆算法解決這個問題，如上所言，最壞的時間復(fù)雜度是n * lg(m)，其中n是元素總量，m是待查找的最大的m個數(shù)。
根據(jù)我上面的這個想法， 還有我原來寫過的堆算法，給出解決這個問題的代碼，由于我原來寫的堆算法是大項堆(max-heap)，也就是堆中最大的元素在根部，所以這里面求出來的是數(shù)中最小的10個數(shù)，如果要求最大的10個數(shù)，要講這個堆改成小項堆，其實也就是改變堆中父子之間的大小關(guān)系罷了，其他的地方不變。
/********************************************************************
created: 2007/3/18
filename: main.cpp
author: Lichuang
purpose: 測試模擬堆算法
*********************************************************************/
#include <algorithm>
#include <iostream>
#include <time.h>
using namespace std;
// push_heap為向堆中添加一個新的元素, 調(diào)用這個算法的前提是[First, Last)之間的元素滿足堆的條件
// 新加入的元素為Last
void push_heap(int* pFirst, int* pLast);
// pop_heap為從堆中刪除一個元素, 調(diào)用這個算法的前提是[First, Last)之間的元素滿足堆的條件
// 被刪除的元素被放置到Last - 1位置,由于這里是max-heap,所以被刪除的元素是這個序列中最大的元素
void pop_heap(int* pFirst, int* pLast);
// make_heap將序列[First, Last)中的元素按照堆的性質(zhì)進行重組
void make_heap(int* pFirst, int* pLast);
// 對堆進行排序, 調(diào)用這個函數(shù)可以成功排序的前提是[pFirst, pLast)中的元素符合堆的性質(zhì)
void sort_heap(int* pFirst, int* pLast);
// 判斷一個序列[First, Last)是否滿足堆的條件,是就返回1,否則返回0
char is_heap(int* pFirst, int* pLast);
// 用于根據(jù)堆的性質(zhì)調(diào)整堆, 將nValue放到位置nHoleIndex, 并且保證堆性質(zhì)的成立
void adjust_heap(int *pFirst, int nHoleIndex, int nLen, int nValue);
// 得到一個數(shù)組中最小的n個元素
void get_n_min(int *pArray, int nLen, int n);
void display_array(int *pArray, int nLength);
int main()
{
srand(time(NULL));
int Array[10];
for(int i = 0; i < 10; ++i)
Array[i] = rand();
get_n_min(Array, 10, 2);
return 0;
}
void get_n_min(int *pArray, int nLen, int n)
{
int *pTmp = (int*)malloc(sizeof(int) * n);
if (NULL == pTmp)
{
perror("malloc error");
return;
}
int i;
for (i = 0; i < n; ++i)
pTmp[i] = pArray[i];
make_heap(pTmp, pTmp + n);
display_array(pTmp, n);
for (; i < nLen; ++i)
{
if (pArray[i] < pTmp[0])
adjust_heap(pTmp, 0, n, pArray[i]);
}
// 最后對堆進行排序
sort_heap(pTmp, pTmp + n);
cout << "the min n elements of the array is:\n";
// 打印堆中的數(shù)據(jù)
display_array(pTmp, n);
free(pTmp);
}
// push_heap為向堆中添加一個新的元素, 調(diào)用這個算法的前提是[First, Last)之間的元素滿足堆的條件
// 新加入的元素為Last
void push_heap(int* pFirst, int* pLast)
{
int nTopIndex, nHoleIndex, nParentIndex;
int nValue;
nTopIndex = 0;
nHoleIndex = (int)(pLast - pFirst - 1);
nParentIndex = (nHoleIndex - 1) / 2;
nValue = *(pLast - 1);
// 如果需要插入的節(jié)點值比父節(jié)點大, 上溯繼續(xù)查找
while (nHoleIndex > nTopIndex && pFirst[nParentIndex] < nValue)
{
pFirst[nHoleIndex] = pFirst[nParentIndex];
nHoleIndex = nParentIndex;
nParentIndex = (nHoleIndex - 1) / 2;
}
pFirst[nHoleIndex] = nValue;
}
// pop_heap為從堆中刪除一個元素, 調(diào)用這個算法的前提是[First, Last)之間的元素滿足堆的條件
// 被刪除的元素被放置到Last - 1位置,由于這里是max-heap,所以被刪除的元素是這個序列中最大的元素
void pop_heap(int* pFirst, int* pLast)
{
int nValue;
nValue = *(pLast - 1);
*(pLast - 1) = *pFirst;
adjust_heap(pFirst, 0, (int)(pLast - pFirst - 1), nValue);
}
// make_heap將序列[First, Last)中的元素按照堆的性質(zhì)進行重組
void make_heap(int* pFirst, int* pLast)
{
int nLen, nParentIndex;
nLen = (int)(pLast - pFirst);
nParentIndex = (nLen - 1) / 2;
while (true)
{
// 對父節(jié)點進行調(diào)整, 把父節(jié)點的值調(diào)整到合適的位置
adjust_heap(pFirst, nParentIndex, nLen, pFirst[nParentIndex]);
if (0 == nParentIndex)
return;
nParentIndex--;
}
}
// 對堆進行排序, 調(diào)用這個函數(shù)可以成功排序的前提是[pFirst, pLast)中的元素符合堆的性質(zhì)
void sort_heap(int* pFirst, int* pLast)
{
// 調(diào)用pop_heap函數(shù), 不斷的把當前序列中最大的元素放在序列的最后
while(pLast - pFirst > 1)
pop_heap(pFirst, pLast--);
}
// 判斷一個序列[First, Last)是否滿足堆的條件,是就返回1,否則返回0
char is_heap(int* pFirst, int* pLast)
{
int nLen, nParentIndex, nChildIndex;
nLen = (int)(pLast - pFirst);
nParentIndex = 0;
for (nChildIndex = 1; nChildIndex < nLen; ++nChildIndex)
{
if (pFirst[nParentIndex] < pFirst[nChildIndex])
return 0;
// 當nChildIndex是偶數(shù)時, 那么父節(jié)點已經(jīng)和它的兩個子節(jié)點進行過比較了
// 將父節(jié)點遞增1
if ((nChildIndex & 1) == 0)
++nParentIndex;
}
return 1;
}
// 一個靜態(tài)函數(shù)僅供adjust_heap調(diào)用以證實JJHOU的結(jié)論
static void push_heap(int *pFirst, int nHoleIndex, int nTopIndex, int nValue)
{
int nParentIndex;
nParentIndex = (nHoleIndex - 1) / 2;
while (nHoleIndex > nTopIndex && pFirst[nParentIndex] < nValue)
{
pFirst[nHoleIndex] = pFirst[nParentIndex];
nHoleIndex = nParentIndex;
nParentIndex = (nHoleIndex - 1) / 2;
}
pFirst[nHoleIndex] = nValue;
}
// 對堆進行調(diào)整, 其中nHoleIndex是目前堆中有空洞的節(jié)點索引, nLen是待調(diào)整的序列長度
// nValue是需要安插進入堆中的值
void adjust_heap(int *pFirst, int nHoleIndex, int nLen, int nValue)
{
int nTopIndex, nSecondChildIndex;
nTopIndex = nHoleIndex;
nSecondChildIndex = 2 * nTopIndex + 2;
while (nSecondChildIndex < nLen)
{
if (pFirst[nSecondChildIndex] < pFirst[nSecondChildIndex - 1])
--nSecondChildIndex;
pFirst[nHoleIndex] = pFirst[nSecondChildIndex];
nHoleIndex = nSecondChildIndex;
nSecondChildIndex = 2 * nHoleIndex + 2;
}
if (nSecondChildIndex == nLen)
{
pFirst[nHoleIndex] = pFirst[nSecondChildIndex - 1];
nHoleIndex = nSecondChildIndex - 1;
}
// 以下兩個操作在這個函數(shù)中的作用相同, 證實了<<STL源碼剖析>>中P178中JJHOU所言
//pFirst[nHoleIndex] = nValue;
push_heap(pFirst, nHoleIndex, nTopIndex, nValue);
}
void display_array(int *pArray, int nLength)
{
for (int i = 0; i < nLength; ++i)
std::cout << pArray[i] << " ";
std::cout << std::endl;
}
|