非比较排序――桶排序 - c++编程基础

相对于计数排序，桶排序和计数排序的差别就在于处理相同数据的差别上。计数排序假设输入数据都属于一个小区间内的整数，而桶排序则是假设输入是由一个随时过程产生的，该过程将元素均匀分布在[0, 1)区间上。

在桶排序的过程中有一个非常重要的地方就是，投射的位置 = current_data * number_array / maximum_array_scope ，如果出现多个数投射在相同的位置上，那么这里就和hash 处理冲突一样，补充一个链表，并且在链表中元素是有序的。

图解：

考虑到图片太大的问题，所以每一张图片都剪成了2张

一共生成30个随机数据，下一张图是和这张图相连的

经过映射之后的情况是：

最后只需要依次序输出即可。

#include   
#include   
#include   
#include   
#include 




  
#define MAX 1000  
#define N 30  
using namespace std;  
typedef list LISTINT;  
  
int main()  
{  
    LISTINT::iterator iter;  
    int a[N];  
    srand(time(NULL));  
      
    for(int i =0;i < N; i++)  
        a[i] = rand()%MAX;  
    for(int i = 0;i < N; i++)  
        cout << a[i] << " ";  
    cout << endl;  
      
    LISTINT *listAll = new LISTINT[N];  
    int index[N];  
    memset(index, 0, sizeof(index));  
      
    for(int i = 0; i < N; i++)  
    {  
        int temp = a[i]*N / MAX;  
        if(index[temp]==0)  
        {  
            index[temp] = 1;  
            listAll[temp].push_back(a[i]);  
        }else{  
            listAll[temp].push_back(a[i]);  
            listAll[temp].sort();  
        }  
    }  
    for(int i = 0; i < N; i++)  
    {  
        if(index[i] != 0)  
            for(iter = listAll[i].begin(); iter != listAll[i].end(); ++iter)  
                cout << *iter << " ";  
    }  
    cout << endl;  
    delete(listAll);  
    return 0;  
}