桶排序怎么实现

Question

如题所述

Answer 1

桶排序算法要求，数据的长度必须完全一样，程序过程要产生长度相同的数据，使用下面的方法：Data＝rand（）/10000＋10000上面提到的，每次下一次的扫描顺序是按照上次扫描的结果来的，所以设计上提供相同的两个桶数据结构。

前一个保存每一次扫描的结果供下次调用，另外一个临时拷贝前一次扫描的结果提供给前一个调用。

平均情况下桶排序以线性时间运行。像基数排序一样，桶排序也对输入作了某种假设，因而运行得很快。具体来说，基数排序假设输入是由一个小范围内的整数构成，而桶排序则假设输入由一个随机过程产生，该过程将元素一致地分布在区间［0，1）上。

桶排序的思想就是把区间［0，1）划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在［0，1）上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。

排序算法包含的相关内容具体如下：

冒泡排序是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢＂浮＂到数列的顶端。

选择排序是一种简单直观的排序算法，无论什么数据进去都是O（n？）的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。