【比较难写的算法】最坏情况线性时间的选择
发布网友
发布时间：2022-04-28 21:34
共2个回答
热心网友
时间：2022-06-23 07:19
问题是快速排序要求枢纽元在最后一个，如果采用hoare的划分算法，就没有这个要求。而给出的是枢纽元的值，然后要找到位置（搜索一遍），再交换。
如果采用hoare划分法，不用搜索，不过算法和书上描述的就稍有不同了。
另外，因为代码复杂，所以对于随机输入，此算法较慢
下面是hoare划分的选择代码
# include <ctime>
# include <cstdlib>
# include <iostream>
inline void swap(int &x, int&y)
{
int temp = x;
x = y;
y = temp;
}
// A[p..r]
int hoarePartitionX(int *A, int p, int r, int x)
{
int i = p - 1;
int j = r + 1;
for(;;)
{
while( A[--j] > x)
;
while( A[++i] < x)
;
if(i<j)
{
swap(A[i], A[j]);
}
else
{
return j;
}
}
}
// A[0..size-1]
void insertionSort(int *A, int size)
{
int i;
int key;
for(int j=1; j<size; j+=1)
{
key = A[j];
i = j - 1;
while(i >= 0 && A[i] > key)
{
A[i+1] = A[i];
i -= 1;
}
A[i+1] = key;
}
}
// return the ith smallest element of A[p..r]
int select(int *A, int p, int r, int i)
{
if(p == r) // only one element, just return
{
return A[p];
}
// #1. groupNum & rest
int groupNum = (r - p + 1) / 5; // not counting the rest
int rest = (r - p + 1) % 5;
// #2. sort the groups
for(int t=0; t<groupNum; t+=1)
{
insertionSort(A + p + t*5, 5);
}
if(rest != 0)
{
insertionSort(A + p + groupNum * 5, rest);
}
// #3. get the mid value x
int *mids;
if(rest == 0)
mids = new int[groupNum];
else
mids = new int[groupNum+1];
for(int t=0; t<groupNum; t+=1)
{
mids[t] = A[ p + t*5 + 2 ];
}
if(rest != 0)
{
mids[groupNum] = A[ p + groupNum*5 + (rest-1)/2 ];
}
int x;
if( rest == 0 )
{
x = select(mids, 0, groupNum-1, (groupNum-1) / 2 + 1);
}
else
{
x = select(mids, 0, groupNum, groupNum / 2 + 1);
}
delete []mids;
// #4. partition with x
int k = hoarePartitionX(A, p, r, x) - p + 1; // so the value A[p+k-1] is the kth smallest
// #5.
if(i <= k)
{
return select(A, p, p+k-1, i);
}
else
{
return select(A, p+k, r, i-k);
}
}
int main()
{
int array[100];
for(int i=0; i<100; i+=1)
array[i] = i;
for(int i=0; i<100; i+=1)
{
int rnd = rand()%100;
swap(array[0], array[rnd]);
}
std::cout << select(array, 0, 99, 82);
std::cin.get();
return 0;
}
热心网友
时间：2022-06-23 07:19
