桶排序算法java

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

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

在额外空间充足的情况下，尽量增大桶的数量 使用的映射函数能够将输入的 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 = 0i 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 = 0i 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 个相等键值的顺序和排序之前它们的顺序相同

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

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

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

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

* @author yuncong

*

*/

public class BucketSort {

public void sort(Double[] a) {

int n = a.length

/**

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

*/

int bucketNum = 10// 桶数

LinkedList<LinkedList<Double>>buckets = new LinkedList<LinkedList<Double>>()

for(int i = 0i <bucketNumi++){

LinkedList<Double>bucket = new LinkedList<Double>()

buckets.add(bucket)

import java.util.Scanner

public class Help {

public static void main(String[] 穗丛晌args) {

Scanner sc=new Scanner(System.in)

int size=sc.nextInt()//记录次数n

int[] s=new int[size]//储存数字的数组

for(int i=0i<sizei++){

int p=sc.nextInt()

if(0<p&&p<1000){//进行判断

s[i]=p

}

else{

System.out.println("您输入的数郑扒字非法！"猜锋)}

}

Arrays.sort(s)//从小到大排序

for(int i=0i<=(int)size/2i++){//再将顺序倒过来

int l=s.length

int ss=s[i]

s[i]=s[l-1-i]

s[l-1-i]=ss

}

for(int i=0i<sizei++) {

System.out.println(s[i])

}

}

}

不懂再问哦~~~

---