桶排序(BucketSort) C++

浏览数：40 / 时间：2015年06月08日

1 桶排序核心思想是根据数据规模n划分 x个相同大小的区间（每个区间为一个桶，桶可理解为容器）

2 每个桶存储区间内的元素(区间为半开区间例如[0,10) 或者 [200,300) )

3 将n个元素按照规定范围分布到各个桶中去

4 对每个桶中的元素进行排序，排序方法可根据需要，选择快速排序，或者归并排序，或者插入排序

5 依次从每个桶中取出元素，按顺序放入到最初的输出序列中(相当于把所有的桶中的元素合并到一起)

6 桶可以通过数据结构链表实现

7 基于一个前提，待排序的n个元素大小介于0~k 之间的整数或者是(0, 1)的浮点数也可（算法导论8.4的例子）

8 通常桶越多，执行效率越快，即省时间，但是桶越多，空间消耗就越大，是一种通过空间换时间的方式

注意：代码前部分为辅助代码

辅助类：链表Link

辅助函数：冒泡排序BubbleSort

  1 #include <iostream>
  2 #include <crtdbg.h>
  3 #include <cstring>
  4 using namespace std;
  5 
  6 typedef int DataType;
  7 //建立链表
  8 class Link
  9 {
 10 private:
 11     struct Node
 12     {
 13         DataType data;
 14         Node *next;
 15     };
 16     Node *head; //哨兵位
 17 public:
 18     Link()
 19     {
 20         Init();
 21     }
 22     ~Link()
 23     {
 24         Delete();
 25     }
 26     void Init()
 27     {
 28         head = new Node;
 29         head->next = NULL;
 30     }
 31     void Delete()
 32     {
 33         for (Node *p = head; p != NULL;)
 34         {
 35             Node *pTemp = p->next;
 36             delete p;
 37             p = pTemp;
 38         }
 39         head = NULL;
 40     }
 41     void Print()
 42     {
 43         for (Node *p = head->next; p != NULL; p = p->next)
 44         {
 45             cout << p->data << endl;
 46         }
 47     }
 48     //顺序插入 考虑两种情况 1.空表 2.当插入值是最大值的时候
 49     void SortInsert(DataType data)
 50     {
 51         Node *p = head;
 52         do 
 53         {
 54             if (p->next == NULL || p->next->data > data)
 55             {
 56                 Node *pNew = new Node;
 57                 pNew->data = data;
 58                 pNew->next = p->next;
 59                 p->next = pNew;
 60 
 61                 return;
 62             }
 63             p = p->next;
 64         } while (true);
 65     }
 66     //尾插法直接插入
 67     void Insert(DataType data)
 68     {
 69         Node *p = head;
 70         while(p->next != NULL)
 71         {
 72             p = p->next;
 73         }
 74 
 75         Node *pNew = new Node;
 76         pNew->data = data;
 77         pNew->next = NULL;
 78         p->next = pNew;
 79     }
 80     bool Empty()
 81     {
 82         return head->next == NULL;
 83     }
 84     //去掉首结点并返回首结点的值
 85     int ExtractDate()
 86     {
 87         if (! Empty())
 88         {
 89             DataType data = head->next->data;
 90             Node *p = head->next;
 91             Node *pFirst = p->next;
 92 
 93             delete p;
 94             p = NULL;
 95 
 96             head->next = pFirst; 
 97             return data;
 98         }
 99         return -1;
100     }
101 };
102 //冒泡排序
103 void BubbleSort(int *a, int size)
104 {
105     for(int i=0; i<size; ++i)
106     {
107         for (int j=0; j<size-1-i; ++j)
108         {
109             if (a[j] > a[j+1])
110             {
111                 int tmp = a[j];
112                 a[j] = a[j+1];
113                 a[j+1] = tmp;
114             }
115         }
116     }
117 }
118 //基于一个前提：待排序的n个元素大小是介于 0~k 之间的整数
119 //array待排序数组，result辅助数组存储排序结果，k为允许的最大整数
120 void BucketSort(int array[], int result[], int size, int k)
121 {
122     Link *Bucket = new Link[5];   //建立桶     
123     int sectionSize = k/5;        //记录区间大小
124     int index=0;            //记录区间下标
125 
126     //方法1：一般步骤
127     //按照范围把array中的每个值放入相应的桶中
128     for(int i=0; i<size; ++i)
129     {
130         index = array[i]/sectionSize;
131         Bucket[index].Insert(array[i]); //为保证稳定性，链表使用了尾插法插入
132     }
133     //遍历每个桶，取出桶中的元素,放入辅助数组result，并排序
134     int j=0 , m=0;
135     for (int i=0; i<5; ++i) 
136     {
137         m = j; //记录已排好序的数组元素大小
138         while(!Bucket[i].Empty())
139         {
140             result[j++] = Bucket[i].ExtractDate();    
141         }
142 
143         //可根据实际情况选择快速排序，堆排序等，此处简单起见选择冒泡排序
144         BubbleSort(result+m, j-m);
145     }
146      
147     //方法2：使用链表特性，在插入链表的同时排序
148     //for(int i=0; i<size; ++i)
149     //{
150     //    index = array[i]/sectionSize;
151     //    Bucket[index].SortInsert(array[i]);
152     //}
153     //int j=0;
154     //for(int i=0; i<5; ++i)
155     //{
156     //    while(!Bucket[i].Empty())
157     //    {
158     //        result[j++] = Bucket[i].ExtractDate();    
159     //    }
160     //}
161 
162     delete [] Bucket;
163 }
164 
165 void main()
166 {
167     //检测是否有内存泄露 需要加头文件#include <crtdbg.h>
168     _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
169 
170     int Array[10] = {2, 6, 5, 3, 0, 7, 2, 3, 0, 3};
171     int Result[10] = {0};
172 
173     BucketSort(Array, Result, sizeof(Array)/sizeof(Array[0]), 10);
174 
175     for (int i= 0 ; i < 10; ++i)
176     {
177         cout << Result[i] << "\n";
178     }
179 
180     system("pause");
181 }