桶排序java代码 桶排序数据结构

桶排序算法java

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《数据结构与型誉算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过搏睁程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是桶排序算法：

做网站、网站制作介绍好的网站是理念、设计和技术的结合。创新互联公司拥有的网站设计理念、多方位的设计风格、经验丰富的设计团队。提供PC端+手机端网站建设，用营销思维进行网站设计、采用先进技术开源代码、注重用户体验与SEO基础，将技术与创意整合到网站之中，以契合客户的方式做到创意性的视觉化效果。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在基租岁于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

1. 什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢

当输入的数据被分配到了同一个桶中。

3. 示意图

元素分布在桶中：

然后，元素在每个桶中排序：

代码实现 JavaScript 实例 function bucketSort ( arr , bucketSize ) {

if ( arr. length === 0 ) {

  return arr ;

}

var i ;

var minValue = arr [ 0 ] ;

var maxValue = arr [ 0 ] ;

for ( i = 1 ; i nodes_space) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__); goto exit_2; } return space_mgr; exit_2: free(space_mgr); exit_1: return NULL; } BucketManager* init_buckets(int bucket_nums) { BucketManager* bucket_mgr = (BucketManager*)malloc(sizeof(BucketManager)); if (!bucket_mgr) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__); goto exit_1; } bucket_mgr-nums = bucket_nums; bucket_mgr-buckets = (Node**)calloc(bucket_mgr-nums, sizeof(Node*)); if (!bucket_mgr-buckets) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__); goto exit_2; } return bucket_mgr; exit_2: free(bucket_mgr); exit_1: return NULL; } Node* get_bucket_space(BucketSpaceManager* space_mgr) { if (space_mgr) { return space_mgr-nodes_space[space_mgr-index++]; } else { return NULL; } } void release_bucket_space(BucketSpaceManager* space_mgr) { if (space_mgr) { if (space_mgr-nodes_space) { free(space_mgr-nodes_space); } free(space_mgr); } } void release_buckets(BucketManager* buckets_mgr) { if (buckets_mgr) { if (buckets_mgr-buckets) { free(buckets_mgr-buckets); } free(buckets_mgr); } } int find_max_min(int* arr, int size, int* p_max, int* p_min) { if (size *p_max) { *p_max = arr[i]; } if (arr[i] *p_min) { *p_min = arr[i]; } } return 0; } int insert_bucket(BucketManager* bucket_mgr, int index, Node* new_node) { Node* cur, *pre; if (!bucket_mgr-buckets[index]) { bucket_mgr-buckets[index] = new_node; } else { /** 桶内使用插入排序 */ cur = bucket_mgr-buckets[index]; pre = cur; while (cur-list_next new_node-elem cur-elem) { pre = cur; cur = cur-list_next; } if (new_node-elem elem) { if (pre == cur) { new_node-list_next = cur; bucket_mgr-buckets[index] = new_node; } else { new_node-list_next = cur; pre-list_next = new_node; } } else { cur-list_next = new_node; } } return 0; } void bucket_sort(int* arr, int size) { int max, min; int ret = find_max_min(arr, size, max, min); if (ret 0) { return; } BucketSpaceManager* space_mgr = init_bucket_space(size); if (!space_mgr) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__); goto exit_1; } int bucket_nums = (max - min) / BUCKET_SIZE + 1; BucketManager* bucket_mgr = init_buckets(bucket_nums); if (!bucket_mgr) { goto exit_2; } int i; for (i = 0; i size; ++i) { int index = (arr[i] - min) / BUCKET_SIZE; Node* new_node = get_bucket_space(space_mgr); if (!new_node) { goto exit_3; } new_node-elem = arr[i]; new_node-list_next = NULL; insert_bucket(bucket_mgr, index, new_node); } for (i = 0; i bucket_mgr-nums; ++i) { Node* node = bucket_mgr-buckets[i]; while(node) { printf("%d ", node-elem); node = node-list_next; } } printf(" "); exit_3: release_buckets(bucket_mgr); exit_2: release_bucket_space(space_mgr); exit_1: return; }

下载测试代码

以上为桶排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括：

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

n：数据规模

k："桶"的个数

In-place：占用常数内存，不占用额外内存

Out-place：占用额外内存

稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

java 编写一个程序,输入3个整数,然后程序将对这三个整数按照从大到小进行排列

可以实现比较器Comparator来定制排序方案，同时使用Colletions.sort的方式进行排序，代码如下：

public void sortDesc(ListLong s){

Collections.sort(s, new ComparatorLong() {

public int compare(Long o1, Long o2) {

Long result = o2 - o1;

return result.intValue();

}

});

s.forEach(item-{

System.out.print(item +" ");

});

}

同时常用的比较排序算法主要有：型团冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

java的冒泡排序实现如下：顷租拍

public static void bubbleSort(int []arr) {        for(int i =0;iarr.length-1;i++) {            for(int j=0;jarr.length-i-1;j++) {//-1为了防止溢出                if(arr[j]arr[j+1]) {                    int temp = arr[j];                       雀羡                  arr[j]=arr[j+1];                                         arr[j+1]=temp;            }            }            }    }

还有非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

桶排序java怎么处理重复的元素

桶排序的核心思想是，将[0，1）分为n个大小相同的子漏指册区间，

* 上一个区间里的元素都逗衡比下一个区间里的元素小，然后对

* 所有区间里的元素排序，最后顺序输出所有区间里的元素，

* 达到对所有元素排序的目的。

* @author yuncong

*

*/

public class BucketSort {

public void sort(Double[] a) {

int n = a.length;

/**

* 创建链表（桶）集合并初始化返宏，集合中的链表用于存放相应的元素

*/

int bucketNum = 10; // 桶数

LinkedListLinkedListDouble buckets = new LinkedListLinkedListDouble();

for(int i = 0; i bucketNum; i++){

LinkedListDouble bucket = new LinkedListDouble();

buckets.add(bucket);