ヒルの並べ替え、高速の並べ替え、積み上げの順序

最近はデータ構造の試験を準備していますので、自分で復習する過程をブログで記録しています.今日の内容は3つの高級順位です.ヒル順序付けは、シーケンス増分がincr[k]=2(t-k+1)-1であるとき、時間複雑度はO(n 1.5)である.シーケンスインクリメントでグループごとにサイズ調整を行います.

template
void ShellInsert(T elem[],int n,int incr)
{
	for(int i=incr;i=0&&e
void ShellSort(T elem[],int n,int incr[],int t)
{
	for(int k=0;k

急速な並べ替えの迅速な順序付けは、すべての同数級O(nlogn)の並べ替えアルゴリズムの中で最も平均的な性能が高いと認められているが、元の順序が整然としている場合、急速な順序付けは泡立ち秩序化され、時間的複雑度はO(n^2)である.

template
int Patition(T elem[],int low,int high)
{//                  ，        。
	while(low
void QuickSortHelp(T elem[],int low,int high)
{//      
	int pos=Partition(elem,low,high);
	QuickSortHelp(elem,low,pos-1);
	QuickSortHelp(elem,pos+1,high);
}
template
void QuickSort(T elem[],int n)
{
	QuickSortHelp(elem,0,n-1);
}

ヒープの並べ替えが最悪の場合、時間の複雑度はO(nlogn)で、一時的な交換のための一時的な記憶空間だけを占有します.

template
void SiftAdjust(int elem[],int high,int low)
{//elem  elem[low]        ，  elem[low]       
	for(int f=low,i=2*f+1;i<=high;i=2*i+1)
	{	
		if(i=elem[i])
			break;
		Swap(elem[f],elem[i]);
		f=i;
	}
}
template
void HeapSort(int elem[],int n)
{//            ，                ，        
	int i;
	for(i=(n-2)/2;i>=0;i--)
		SiftAdjust(i,n-1);
	for(i=n-1;i>=0;i--)
	{
		Swap(elem[0],elem[i]);
		SiftAdjust(0,i-1);
	}
}