[科普中國(guó)]-整序集法

基礎(chǔ)知識(shí)整序的定義

整序源于英文sorting一詞，是對(duì)給定的一組數(shù)字或字符按照一定規(guī)則整理次序。整序又分為內(nèi)部整序和外部整序。所謂的內(nèi)部整序是指要整序的元素全部放在內(nèi)存；所謂的外部整序是指要整序的元素存放在外存。

整序問(wèn)題整序問(wèn)題定義為：給定一些全序（常用≤表示）集中抽出來(lái)的元素序列 ，找出一個(gè)置換π，它把給定的序列映射到一個(gè)非遞減序列 ，即， , 。

1.穩(wěn)定的整序方法

在給定的n個(gè)元素序列整序時(shí)，若其中有幾個(gè)元素相同，上述定義的π不唯一。選擇一種π，使?jié)M足：

（1） , ；

（2）如果在已整序序列中 且 ，則必有in，則i無(wú)兒子。如果2i