基数排序、桶排序
这里介绍一下非比较排序
头绪比较乱
编程珠玑 I 第一节中就讲到一种排序方法：大批量的数排序，内存有限，利用 bitmap 可以很好的解决。时间为 O(N) 。
对于不重复出现的数的集合，也就是说对于某个数最多只出现一次。可以利用 bitmap 来解决。因为一个 bit 只有两个状态： 0 和 1 。
1.
对于重复出现的数，可以利用一般类型数组来解决。对于每个数，以每个数为索引，记录以该索引的元素自加 1 。处理完后，扫描这个辅助数组，将记录的信息，也就是索引的次数，把索引以次数存入原来数组中。
2.
这种直接以待排序的数为索引，需要很大的辅助数组。所以可以利用针对待排序的数的每位来处理，每个位的范围也就是 0 - 9 十的大小。对于多维的待排序数处理方式有两种。即从左到右和从右到左。
从左到右：左面的排完序后，整体次序不变了，只是调整的次位的相对顺序。
从右到左：右面的排完序后，整体的次序还会有变化的，只不过是随着从右到左，依次调整的次数越来越少了。
3.
桶排序，对于一系列待排序数，可以先按照各个数的属性将所有数分配到各个桶里。这样后，对于每个桶里的数可以使用插入排序进行各个桶的排序。
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 阅读(364)
评论(0) 编辑 收藏 引用