www.pudn.com > Bucket-Sort.rar > main.cpp, change:2016-03-29,size:3032b


#include<iostream> 
using namespace std; 
 
// 分类 ------------- 内部非比较排序 
// 数据结构 ---------- 数组 
// 最差时间复杂度 ---- O(n^2) 
// 平均时间复杂度 ---- O(n + bn) 
// 最差空间复杂度 ---- O(n * bn) 
 
/* 本程序用数组模拟桶 */ 
const int bn = 10;                // 我们这里打算使用10个桶 
int C[bn];                        // 临时数组,存放桶的边界信息 
 
int MapToBucket(int x, int max)    // 把元素x映射到桶中 
{ 
    return (9 * x) / max;        // 返回值范围{0,1,2,...,9},共10个桶 
} 
 
void insertionsort(int A[], int left, int right)// 同一个桶内进行插入排序 
{ 
    for (int i = left + 1; i <= right; i++)    // 从桶内第二张牌开始抓,直到最后一张牌 
    { 
        int get = A[i]; 
        int j = i - 1;                         
        while (j >= left && A[j] > get)         
        { 
            A[j + 1] = A[j]; 
            j--; 
        } 
        A[j + 1] = get; 
    } 
} 
 
void countingsort(int A[], int n, int B[])// 应用计数排序把不同桶中的元素排好序 
{ 
	int i=0; 
    for ( i = 0; i < bn; i++)    // 初始化,将数组C中的元素置0 
    { 
        C[i] = 0; 
    } 
    int max = A[0]; 
 
    for (i = 1; i < n; i++)        // 获得输入数组中的最大值,用于把输入元素向桶中映射 
    { 
        if (A[i] > max) 
            max = A[i]; 
    } 
    for (i = 0; i < n; i++)        // 使C[i]保存着i号桶中元素的个数 
    { 
        C[MapToBucket(A[i], max)]++; 
    } 
    for (i = 1; i < bn; i++)    // 求出每个桶的右边界索引:C[i]-1为第i号桶中最后一个元素的数组下标 
    { 
        C[i] = C[i] + C[i - 1]; 
    } 
    for (i = n - 1; i >= 0; i--)// 从后向前扫描保证计数排序的稳定性(重复元素相对次序不变) 
    { 
        int j = MapToBucket(A[i], max);// 元素A[i]位于第j号桶 
        B[C[j] - 1] = A[i];            // 把每个元素A[i]放到它在输出数组B中的正确位置上 
        C[j]--;                        // 当再遇到同一个桶中的元素时会被放在当前元素的前一个位置上 
    } 
    // 执行完上述循环,C[j]变成了每个桶的左边界索引:C[j]为第j号桶第一个元素的数组下标(下边的插入排序要使用) 
} 
 
void bucketsort(int A[], int n) 
{ 
    int *B = (int *)malloc((n)* sizeof(int));// 分配临时空间,长度为n,用来暂存中间数据 
    countingsort(A, n, B);    // 应用计数排序把不同桶中的元素排好序,同一桶中的元素暂时按输入次序存放 
    for (int i = 0; i < n; i++)    // 把临时空间B中的数据拷贝回A 
    { 
        A[i] = B[i]; 
    } 
    free(B);                    // 释放临时空间   
    for ( i = 0; i < n; i++)    // 对同一个桶中的元素应用插入排序 
    {                                 
        int left = C[i] ;        // C[i]为第i号桶中第一个元素的数组下标 
        int right = C[i + 1] - 1;// C[i+1]-1为第i号桶中最后一个元素的数组下标    
        if (left < right) 
            insertionsort(A, left, right); 
    } 
} 
 
int main() 
{ 
    int A[] = { 112, 240, 554, 75, 447, 789, 3, 69, 28, 447 };// 针对桶排序设计的输入 
    int n = sizeof(A) / sizeof(int); 
    bucketsort(A, n); 
    printf("桶排序结果:"); 
    for (int i = 0; i < n; i++) 
    { 
        printf("%d ",A[i]); 
    } 
    printf("\n"); 
    return 0; 
}