プログラマー面接問題--スタックソートのC言語実装

多くの会社を面接し、同級生の面接経験と自分の面接経験に基づいて、スタックソートに関する実装コードを整理しました.

//          
void HeapAjust(int data[],int i,int length)
{
	int nChild;
	int nTemp;
	for(nTemp=data[i];2*i+1<length;i=nChild)
	{
		nChild=2*i+1;
		if(nChild<length-1&&data[nChild+1]>data[nChild])//          ，        ，   nChild++；
		{
			nChild++;
		}

		if(nTemp<data[nChild])//            ，   
		{
			data[i]=data[nChild];
			data[nChild]=nTemp;
		}
		else//          ，    
			break;
	}
}

//   
void HeapSort(int data[],int length)
{
	for(int i=(length>>1)-1;i>=0;i--)//      ：i=(length>>1)-1，    ，  ：      
	{
		HeapAjust(data,i,length);//      
	}
	for(int j=length-1;j>0;--j)
	{
		int temp=data[j];
		data[j]=data[0];
		data[0]=temp;
		HeapAjust(data,0,j);
	}
}

上は主に機能関数で、主関数はみんなできました!デバッグに合格しました!スタックソートの時間的複雑度はO(nlogn)であり,最悪の場合もこの時間的複雑度であり,空間的複雑度はO(1)である.しかし、スタックのソートは不安定です!面接の過程で、多くの場合、次の問題がスタックソートの典型的な問題であるなど、スタックソートに使用されます.
1.あなたに100 w個のデータをあげて最大の10個の要素を求めます.この時は小さな天井を使うことができます!これはなぜですか.
2.あなたに100 w個のデータをあげて最小の10個の要素を求めます.この時、私たちは大きな山を使うことができます!これはなぜですか.
多くの学生が上の2つの疑問を聞くことができると信じて、答えは実はとても簡単で、最大の要素を求める時、私達は1つの10の要素の小さいトップの山を創立して、それではトップの要素は間違いなく最小で、それから残りの要素とトップを持って比較して、もしトップより大きいならば、この要素を交換して、それからスタックを調整して、調整が完了した後もスタックトップは10要素の中で最も小さく、残りの要素を順次比較します.
スタックソートと直接挿入ソートの違い
直接選択ソートでは、R[1..n]からキーワード最小のレコードを選択するためには、n-1回の比較を行い、R[2..n]でキーワード最小のレコードを選択し、n-2回の比較を行う必要がある.実際,後のn−2回の比較では,前のn−1回の比較ですでに行われた可能性のある比較が多かったが,前のソートではこれらの比較結果が保持されていなかったため,後のソートではこれらの比較操作が繰り返された.スタックソートは、比較結果の一部をツリー構造で保存し、比較回数を減らすことができます.