|
|
一.堆排序.
以前虽然对堆排序的理论和过程已经非常熟悉了,伪代码也写了不少,但竟然还没有真正在VC中实现过.今天把它写了一下,代码如下:
#includeusingnamespacestd;
//======================================//最大堆Heap
//======================================
classHeap
{
private:
int*array;
size_tsize;
inlinesize_tparent(size_ti)
{
returni>>1;
}
inlinesize_tleft(size_ti)
{
returniarray=array;
this->size=size;
}
voidheapify(size_ti)
{
size_tl,r,max=i;
inttemp;
l=left(i);
r=right(i);
if(l=0;i--)
heapify(i);
}
voidsort()
{
inttemp;
for(inti=size-1;i>0;i--)
{
temp=array[0];
array[0]=array;
array=temp;
size=size-1;
heapify(0);
}
}
};
//一个简单的应用实例------------------voidmain()
{
inta[10]={2,6,3,8,9,7,1,4,0,5};
Heapheap=Heap(a,10);
heap.buildHeap();
heap.sort();
for(inti=0;inextNode
放在min的位置．再花O(lgk)调用heapify 方法将 A 重新建成一个最小堆．然后又将第一个元素 min
放入链表......重复进行就可将 k 个已排序链表合并．（当最后剩余不到 k
个节点时情况会有点变化，但很容易解决）．显然，这样处理的时间复杂为 O(n*lgk);
三.Young
氏矩阵的相关算法.
题:一个 m*n 的 Young 氏矩阵(Young tableau) 是一个
m*n
的矩阵,其中每一行的数据都从左到右排序,第一列的数据都从上到下排序.Young氏矩阵中可能会有一些∞
数据项,表示不存在的元素.所以,Young 氏矩阵可以用来存放 rYoung[x][y 1])
Young[x][y]=EXTRACT_MIN(Young[x...m][y 1...m]);
elseYoung[x][y]=EXTRACT_MIN(Young[x 1...m][y...m]);
END
c). 这个就比较简单了.先将待插入的元素 K 放在 Young[m][n], 然后比较 K
与它左方或上方元素的大小,并与其中较大的一个交换.反复进行直到 K 不小于它左方和上方的元素为止.
在这里,同样有,T(m,n)=T(m-1,n) or
T(m,n-1) O(1),T=O(m n).伪代码如下:
INSERT(k,Young[m][n])
if(Young[m][n]Young[m][n-1])
swap(k,Young[m-1][n]);
m=m-1;
else
swap(k,Young[m][n-1]);
n=n-1;
END
d).
调用 n*n 次 EXTRACT_MIN 过程即可.
e). 同样是递归的思想.递归表达式与 b)中的相同.伪代码如下:
SEARCH(k,Young[x...m][y...n]
if(kYoung[m][n]return"NotFound";
if(k==Young[x][y])return"Found",x,y.
if(k<Young[x 1][y])SEARCH(k,Young[x...x][y 1...n]
elseSEARCH(k,Young[x 1...m][y...n]
END
|
|
