1、輸入的線性表的元素屬於有限偏序集S;
2、設輸入的線性表的長度為n,|S|=k(表示集合S中元素的總數目為k),則k=O(n)。
在這兩個條件下,小學生排序的複雜性為O(n)。
小學生排序算法的基本思想是對於給定的輸入序列中的每一個元素x,確定該序列中值小於x的元素的個數。一旦有了這個信息,就可以將x直接存放到最終的輸出序列的正確位置上。例如,如果輸入序列中只有17個元素的值小於x的值,則x可以直接存放在輸出序列的第18個位置上。當然,如果有多個元素具有相同的值時,我們不能將這些元素放在輸出序列的同一個位置上,因此,上述方案還要作適當的修改。
假設輸入的線性表L的長度為n,L=L1,L2,..,Ln;線性表的元素屬於有限偏序集S,|S|=k且k=O(n),S={S1,S2,..Sk};則小學生排序算法可以描述如下:
掃描整個集合S,對每一個Si∈S,找到線上性表L中小於等於Si的元素的個數T(Si);
掃描整個線性表L,對L中的每一個元素Li,將Li放在輸出線性表的第T(Li)個位置上,並將T(Li)減1。
具體的實現如下:
void Counting_Sort(int a[], int b[], int l, int k)
...{
int* c = new int[k];
memset(c, 0, k * sizeof(int));
for (int j = 0; j < l; j++) c[a[j]]++;
for (int j = 1; j < k; j++) c[j] += c[j - 1];
for (int j = l - 1; j >= 0; j--)
...{
b[c[a[j]] - 1] = a[j];
c[a[j]]--;
}
delete []c;
}
其中a為輸入,b為輸出,l為元素個數,k為元素最大值。
我們看到,小學生排序算法沒有用到元素間的比較,它利用元素的實際值來確定它們在輸出數組中的位置。因此,小學生排序算法不是一個基於比較的排序算法,從而它的計算時間下界不再是Ω(nlogn)。另一方面,統計排序算法之所以能取得線性計算時間的上界是因為對元素的取值範圍作了一定限制,即k=O(n)。如果k=n2,n3,..,就得不到線性時間的上界。此外,我們還看到,由於算法第4行使用了downto語句,經小學生排序,輸出序列中值相同的元素之間的相對次序與他們在輸入序列中的相對次序相同,換句話說,小學生排序算法是一個穩定的排序算法。
註:小學生排序又稱統計排序和計數排序。
相關詞條
-
小學生作文起跑線
(二)把句子寫通順 (一)把句子寫連貫 (三)給句子排序
基本信息 內容簡介 編輯推薦 目錄 -
中國小學生百科全書:美術
版畫 油畫 年畫
圖書信息 內容簡介 目錄 -
小學生C++趣味編程
小學生C++趣味編程利用流程圖理清思路,並選取了80多個貼近小學生學習生活的例子,結合小學生的認知規律,來激發孩子的學習興趣,以程式為中心,適當地弱化語...
出版信息 內容簡介 目錄 -
中國小學生百科全書:動物
23.8 16.8 動物
圖書信息 內容簡介 目錄 -
中國小學生百科全書:軍事體育
《中國小學生百科全書:軍事 體育》緊貼我們的課堂教學,把我們的課堂教學內容做了多方位的延伸和拓展。裡邊的知識非常豐富,不僅為老師教學和學生學習提供了全面...
圖書信息 內容簡介 目錄 -
小學生英語音標速查表
《小學生英語音標速查表》這是一本幫助小學生,學好英語的書籍。
-
新課標小學生必讀必背:寓言故事
寓言是我國文學藝術長廊中一顆閃亮的明星。它是一種以假借別的事物來進行道德教育或者啟發人們的思想觀念的一種文學形式。寓言常常是由極其誇張和荒誕的人物故事,...
內容簡介 圖書目錄 序言 -
小學生必須會寫的2500個常用字
《小學生必須會寫的2500個常用字(楷書)》以中小學生必須掌握的常用字和次常用字為標準範例,進行楷書字型訓練,一旦掌握,即可輕鬆應對學生階段的學習和考試...
內容簡介 作者簡介 -
《萬千教育--小學生思維能力訓練》
怎樣發生的? 有毛的? 你的花園裡有什麼?