スタックのソートとその応用に関する概要
アウトライン:
1)アルゴリズムの説明
2)コード
3)「三囲」及び証明(複雑度、効率、安定性等の分析)
4)アルゴリズムの直接応用
5)アルゴリズムの原理応用
6)例
一、アルゴリズムの説明:
スタックコンセプト(データ構造):スタックは完全なツリーであり、各ノードがそのサブノードより大きいか小さいかを満たすデータ構造であり、このようなデータ構造は最大スタックまたは最小スタックと呼ばれます.多くのブログでは完全な二叉木と言われていますが、実際には三叉、四叉でもいいですが、対数演算曲線の変化が速いだけで、2叉で十分で、一般的には二叉だけで十分で、このようにアルゴリズムを書くのも簡単です.これはよく理解できるが、10億は約2の30回、すなわち10億個の数を30回で解くことができるので、三叉する必要はない.よく見られる山には二叉の山、フィボナッチの山などがあります.
スタックの特徴:この構造は半順序状態にあり、そのアクセス効率は全体的に秩序と無秩序の間にあり、具体的にはベントリーの「アルゴリズム珠玉」のスタック章の秩序シーケンス、無秩序シーケンスとスタックの操作上の複雑な分析を参照することができる.オブジェクトがダイナミックな場合、非常に優れたデータ構造です.アクセスの時間はlog(a,n)と複雑であり,ここでaは完全ツリーの度であり,この特徴を理解することはその応用に役立つ.
二叉スタックストレージおよび法則:通常、二叉スタックは配列で格納され、親子ノードの下標は、親ノード(下標:i)の左子供ノードの下標:2 i、右子供の下標:2 i+1、またスタックトップ要素の下標は1、層はlog(2,n)と関係がある.注意:下付きは1で計算を開始します.
スタックソートの考え方:1つのスタック(以下、いずれも二叉最小スタックで説明する)について、そのスタックトップ要素を除去し、最末端要素でスタックトップ位置に移動し、再び最小スタックになるように調整します.このように反復して,残りの要素がなくなるまで順次取り出す順序がソートを実現する過程である.擬似コードとして表現すると、次のようになります.
山を築く
ループ(条件:スタックが空でない){
スタックトップ要素を取り出します.
最後の要素をスタックトップ位置に移動します.
再び山になるように調整する.
}
スタック構想:最後の非葉ノードから、下から上への順序で反復し、(下はxと表記)子供ノード(下:2 x、2 x+1)と比較させ、いずれの子供ノードよりも小さい場合、このサブツリーがスタック規則に合致していることを説明する.そうでなければ、他のサブノードを最小のサブノードと交換します.交換後、このノード(x)で元の子供のスタック特性が破壊されるため、ここには適切な位置が見つかるまで上の動作を継続させるサブ反復がある.これにより,ルートノードまで完全な木全体がスタックの性質を備えていることが保証される.具体的には写真を参照してください.この中には大きな根の山の建設過程が描かれています.小さな根の山は同じです.怠け者にしよう
【?】:
1>よく観察し、考えてみると、実際にスタックを構築し、スタックの調整を行うことで、共通の方法を抽出することができることがわかります.サブツリーがスタック特性を有する条件下で,同じ方法で調整できる.(1つのルートノードは特殊なスタックと考えられ,最大スタックでも最小スタックである.
2>なぜ下から上へと缲り返すのかを考えて、逆にしてはいけませんか???試してみると、このようなメリットがわかります.
3>どのような場合,子反復が発生するか,すなわち,その子ノード,孫ノードなどすべての子孫とループして比較する場合を考える.
二、コード(自分で開発した、厳蔚敏先生の「データ構造」の構想に基づくアルゴリズムは、すでにコンパイルしてテストした.)
//program name : heap sort
//author : Dam
//email : [email protected]
//discription : This is a sort that fits for find max or min key from huge data;
// The tree mentioned before is binary tree.And it is not stabled.
// step 1:build a heap
// step 2:delete the root node;
// step 3:rebuild the heap by using the left nodes
// step 4:loop step 2 and step 3,until there is no node left.
//space & time:
// space: S(n)= O(1)
// time: T(n)= nlog(2,n)
#include
#include
#define FALSE 0
#define TRUE 1
#define NUMMAX 1000000
typedef struct hs_data
{
unsigned int key;
char value[30];
}ListType, *pListType;
int print_set(ListType lt[],unsigned int n);
int hs_sift(ListType r[],int k,int n);
int getNTopValue(ListType lt[],int n);//Sub HeapSort - unprogramed.
int HeapSort(ListType r[], int n);
// heap sort in sequent order
int hs_sift(ListType r[],int k,int n)
{
int i=k,j=2*i+1,finished= FALSE;
unsigned int x=r[k].key;
ListType t = r[k];
while((j r[j+1].key))
j++;
if (x <= r[j].key)
finished= TRUE;
else
{
r[i]= r[j];
i= j;
j= 2*i+1;
}
}
r[i]= t;
return 0;
}
// This algs needs one place;
int HeapSort(ListType r[], int n)
{
int i;
//build the heap
//loop every unleaf node,and compare it with its children,grand...children.
for(i=(n-1)/2; i >= 0; i--)
hs_sift(r, i, n);
//printf("after build deap!
");
//print_set(r,n);
//delete the root node from heap,then rebuild the heap,until there no node left
for(i=n-1; i > 0; i--)
{
//replace the root node using the last node,then resort it
ListType t;
t = r[0];
r[0]= r[i];
r[i]= t;
hs_sift(r, 0, i);
}
//printf("after deap sort!
");
//print_set(r,n);
return 0;
}
// print the result in before sorting and after sorting
int print_set(ListType lt[],unsigned int n)
{
printf("=====================================
");
printf("start print....
");
int i=0;
while(i < n )
{
printf("%u
", lt[i].key);
i++;
}
printf("print end ....
");
printf("=====================================
");
return 0;
}
int main(void)
{
ListType big_set[NUMMAX+1];
int i;
//init the rander with different seeds;
srand(time(NULL));
for( i=0; i < NUMMAX; i++)
{
ListType t;
memset(&t,'\0', sizeof(ListType));
t.key=rand()%(NUMMAX);
//t.key=(unsigned int)(10-i);
strcpy(t.value, "");
big_set[i]= t;
}
printf("before sorting,the set is :
");
print_set(big_set, NUMMAX);
HeapSort(big_set, NUMMAX);
printf("after sorting, the set is :
");
print_set(big_set, NUMMAX);
return 0;
}
【？】： 1> ， ， ？？ 、 ： ：O（n) ： h， ：2^h-1, H ：2^(H-1) ， ， 。 ， 。 T(n) =1*（h-1) + 2*(h-2) + 4*(h-3) + ... + 2^(h-3)*(h-(h-2)) + 2^(h-3)*(h-(h-1)) =h(1+2+4+...+ 2^(h-1)) - (1 + 2*2 +4*3 + 8*4 + 16*5 + .. + 2^(h-3) *(h-2) + 2^(h-2)*(h-1) ) ：(a1-an*q)/(1-q) (q≠1) ： 2^（n-1) * n, Sn， n 。 Sn*2 : 2*1 + 4*2 + 8*3 + 16*4 + ... + 2^(h-2) *(h-2) + 2^(h-1)*(h-1) Sn*2 -Sn = Sn = 2^(h-1)*(h-1) - (1 + 2 + 4 + 8 + 16 + ... + 2^(h-2) ) ---- , Sn： Sn = 2^(h-1)*(h-1) - 2^(h-1) = 2^(h-1)*(h-2) Sn, T(n): T(n) = 2^h * h - 2^(h-1)*(h-2) = 2^(h-1) * (h+2) = 2^h * (h+2)/2 ≈ n * log(2,n)/2 ：log(2,n) * n ：O(nlog(2,n)) n n ， ， ： n * log(2,n) ： ：O(1) ： O(1), 。 ： ， ； ， ， ， ， 。 ： ， ， 2 ， 。 【？】： 1> ， ， 。 2 ， 。 ， ， 。 ？？ 2> ， ， 。 、 ， 、 ， ， 。 ， ，c qsort 。 、 : ， ， 。 。 ， （ ） 。 3 ： （1） （ ） ， O（1） （2） ， ， 。 ， log（n+1) 。 ： T(n) = log(2,n+1) + (log(2,n+1)-1) + ... +2 + 1 = (1+log(2,n+1))* log(2,n+1)/2 = (log(2,n+1)+1/2)^2 / 2 -1/8 ≈ log(2,n+1)^2 /2 ：log(2,n) （3） ， ， log(2,n) 、 1. O(nlgk)， k 。 n 。 【 】 ， ： 2kn + (2kn+n) +...+((k-1)n+n) ： ， ， 。 。 k 。 （1） k ， k k 。 O(k)。 （2） k ， 。 O(1)。-- ， 。 （3） ， ， ， 。 O(lgk)。 ， ， ， heapSize 1 。 O(lgk)。 （4） （2）~（3）n-k 。 O(k)+O(nlgk) O(nlgk)。 http://hi.baidu.com/tuangougou/item/872f45d42f69ad3838f6f754 2. 1 ， ( ) 100 ?（ ：O（n lg k）） ： ， 3 ： 1) ： ， ， ， ：10000* n 2) ： ： n , 10000 ， 10000*log(2,n) n+10000*log(2,n)=n+10000*10000 = 2n 3) ： 1 2 ， 2 。 100w ， 100w ， 。 ， 100w ， 。 : log(2,100w)*100w + n+ n/2 + n/4 …+ n/10000 2n。