基數(shù)排序、桶排序
這里介紹一下非比較排序
頭緒比較亂
編程珠璣 I 第一節(jié)中就講到一種排序方法：大批量的數(shù)排序，內(nèi)存有限，利用 bitmap 可以很好的解決。時(shí)間為 O(N) 。
對(duì)于不重復(fù)出現(xiàn)的數(shù)的集合，也就是說(shuō)對(duì)于某個(gè)數(shù)最多只出現(xiàn)一次。可以利用 bitmap 來(lái)解決。因?yàn)橐粋€(gè) bit 只有兩個(gè)狀態(tài)： 0 和 1 。
1.
對(duì)于重復(fù)出現(xiàn)的數(shù)，可以利用一般類型數(shù)組來(lái)解決。對(duì)于每個(gè)數(shù)，以每個(gè)數(shù)為索引，記錄以該索引的元素自加 1 。處理完后，掃描這個(gè)輔助數(shù)組，將記錄的信息，也就是索引的次數(shù)，把索引以次數(shù)存入原來(lái)數(shù)組中。
2.
這種直接以待排序的數(shù)為索引，需要很大的輔助數(shù)組。所以可以利用針對(duì)待排序的數(shù)的每位來(lái)處理，每個(gè)位的范圍也就是 0 - 9 十的大小。對(duì)于多維的待排序數(shù)處理方式有兩種。即從左到右和從右到左。
從左到右：左面的排完序后，整體次序不變了，只是調(diào)整的次位的相對(duì)順序。
從右到左：右面的排完序后，整體的次序還會(huì)有變化的，只不過(guò)是隨著從右到左，依次調(diào)整的次數(shù)越來(lái)越少了。
3.
桶排序，對(duì)于一系列待排序數(shù)，可以先按照各個(gè)數(shù)的屬性將所有數(shù)分配到各個(gè)桶里。這樣后，對(duì)于每個(gè)桶里的數(shù)可以使用插入排序進(jìn)行各個(gè)桶的排序。
1 #include <iostream>
2 #include <vector>
3 #include <cstring>
4 using namespace std;
5
6 void sort(vector<int>& array)
7 {
8 int temp[1000];
9 memset(temp, 0, sizeof (int) * 1000);
10 for (vector<int>::size_type i = 0; i != array.size(); ++i)
11 {
12 ++temp[array[i]];
13 }
14 array.clear();
15 for (int i = 0; i < 1000; ++i)
16 {
17 while (temp[i]-- != 0)
18 {
19 array.push_back(i);
20 }
21 }
22 }
23
24 int main()
25 {
26 vector<int> array;
27 for (int i = 0; i < 10; ++i)
28 {
29 array.push_back(i);
30 }
31 for (int i = 10; i >= 0; --i)
32 {
33 array.push_back(i);
34 }
35 sort(array);
36 for (vector<int>::size_type i = 0; i < array.size(); ++i)
37 {
38 cout << array[i] << ' ';
39 }
40 cout << endl;
41 return 0;
42 }
posted on 2011-06-21 22:45
unixfy 閱讀(375)
評(píng)論(0) 編輯 收藏 引用