`

桶排序

阅读更多
/**
 * 桶排序
 * <ul>
 * <li>平均情况:O(N+C)</li>
 * <li>最好情况:O(N)</li>
 * <li>最坏情况:O(N+C)</li>
 * <li>辅助存储:O(N+C)</li>
 * <li>稳定</li>
 * <ul>
 * 
 * @timestamp Mar 13, 2016 7:53:03 PM
 * @author smallbug
 */
public class BucketSort {
	public static void main(String[] args) {
		int[] data = DataUtil.getData(1000);
		System.out.println(Arrays.toString(data));
		long time = System.currentTimeMillis();
		data = bucketSort(data);
		System.out.println(Arrays.toString(data));
		System.out.println("speed " + (System.currentTimeMillis() - time) + " ms");
		System.out.println("排序是否成功:" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否"));
	}

	private static int[] bucketSort(int[] data) {
		int[] count = new int[data.length];// 计数数组
		int[] result = new int[data.length];// 结果数组
		for (int i = 0; i < data.length; i++) {
			count[data[i]]++;// 建立计数表
		}
		for (int i = 1; i < count.length; i++) {
			count[i] = count[i] + count[i - 1];// 格式化计数表
		}
		for (int i = data.length - 1; i >= 0; i--) {
			result[--count[data[i]]] = data[i];// 根据计数表排序

		}
		return result;
	}
}

 

0
3
分享到:
评论

相关推荐

    算法桶式排序法桶式排序法

    桶式排序法桶式排序法桶式排序法桶式排序法

    iOS桶排序算法

    桶排序(Bucket Sort)是一种分布式排序算法,它将要排序的数据分布到多个“桶”中,每个桶再分别进行排序,最后将所有桶中的数据合并,得到全局有序的结果。在iOS开发中,桶排序可以被用于优化大规模数据的排序过程...

    桶排序 c++实现

    桶排序(Bucket Sort)是一种分布式排序算法,它将待排序的数据分布到多个“桶”中,每个桶再分别进行排序,最后将所有桶中的数据合并,得到全局有序的结果。这个算法通常适用于数据分布均匀的情况,如果数据在一定...

    桶排序算法的实现与比较

    桶排序(Bucket Sort)是一种分布式排序算法,它将要排序的数据分布到多个“桶”中,每个桶再分别进行排序,最后将所有桶中的数据合并,得到全局有序的结果。桶排序算法的时间复杂度在最理想情况下可以达到线性的O(n...

    桶排序的时间复杂度的计算公式.docx

    桶排序(Bucket Sort)是一种分布式排序算法,它将要排序的数据分布到有限数量的桶里,每个桶再分别进行排序,最后将所有桶中的数据合并,得到全局有序的结果。桶排序的时间复杂度分析是理解其效率的关键部分。下面...

    第3课 桶排序.pdf--

    桶排序是一种基于分配和收集的排序算法,特别适合于数据分布均匀且数据范围已知的情况。在C++编程中,桶排序能够高效地对一系列元素进行排序。根据提供的文件内容,我们可以总结以下知识点: 1. **桶排序的基本原理...

    用Java实现桶排序

    ### 使用Java实现桶排序 #### 知识点概述 桶排序是一种分布式的排序算法,它将数组分到有限数量的“桶”里,然后分别对每个桶进行排序(通常是使用其他排序算法)。最后,将各个桶的数据按顺序合并起来得到最终...

    桶排序-解决排序问题

    桶排序(Bucket Sort)是一种分布式排序算法,常用于大数据处理和流式计算中。它将待排序的数据分布到多个“桶”中,每个桶再独立地进行排序,最后按照桶的顺序依次取出桶中的元素,形成有序序列。桶排序的核心思想...

    第4课 桶排序训练.pdf

    【桶排序】是一种排序算法,它的基本思想是将待排序的数据分布到若干个“桶”中,每个桶内部再进行排序,最后按照每个桶内排序好的数据顺序依次合并,从而得到整个序列的有序排列。在C++编程中,桶排序可以用于解决...

    C++写的希尔排序 归并排序 桶排序 堆排序 3种快速排序 插入排序等

    希尔排序、归并排序、桶排序、堆排序和快速排序都是经典的计算机算法,主要用于对数据进行排序。在C++编程语言中,这些排序算法的实现是程序员必须掌握的基础技能之一。接下来,我们将深入探讨这些排序算法的工作...

    桶排序算法(C++版)

    桶排序(Bucket Sort)是一种分布式排序算法,它将要排序的数据分到几个有序的桶里,每个桶再分别排序,最后按照每个桶内元素的顺序依次取出,组合成整体的有序序列。这种算法适用于数据分布相对均匀的情况。下面...

    桶排序算法的c++实现

    经典的桶排序算法实现,在vs2008上调试通过。 算法介绍: 假定:输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数基本思想将区间[0, 1)划分为n个大小相等的子区间(桶),每桶大小1/n:[0, 1/n), [1/n, 2/n)...

    java版冒泡排序,插入排序,堆排序,快速排序,归并排序,希尔排序,桶排序

    归并排序和希尔排序在稳定性上有优势,而桶排序则对输入数据分布有特定要求。在实际应用中,根据数据特性选择合适的排序算法至关重要。在Java编程中,理解这些排序算法的实现和性能特点,有助于写出高效、适应性强的...

    桶排序代码

    桶排序(Bucket Sort)是一种分布式排序算法,它将要排序的数据分布到多个“桶”中,每个桶再分别独立地进行排序,最后再按照每个桶内元素的顺序依次取出,组合成完全排序的序列。这种算法适用于数据在一定范围内...

    桶排序c编程附加队列

    桶排序 c编程 附加链队列 和顺队列 1)设置10个桶,也即一个有10个元素的队列数组,每个队列的成员有一个整形数组; 2)从键盘输入30个非负整数;3)找出这30个数中大的数,并计算出它的位数; 4)按照桶排序步骤,...

    桶排序算法

    桶排序(Bucket Sort)是一种分布式排序算法,它将要排序的数据分布到多个“桶”中,每个桶再分别进行排序,最后将所有桶中的数据合并,得到全局有序的结果。桶排序算法基于分治策略,其核心思想是将待排序序列均匀...

    排序算法之简单桶排序

    数组应用之桶排序课件,用于信息学奥赛基础算法上课应用。课件内容讲解了桶排序的基本思想,问题应用,知识扩展及多维桶等。

    C语言桶排序

    桶排序(Bucket Sort)是一种分布式的排序算法,它将元素分布到多个“桶”中,然后对每个桶分别进行排序,最后再将所有桶中的元素合并成一个有序序列。桶排序的基本思想是假设输入数据服从均匀分布,通过将数据分到...

    java算法——基数排序/桶排序

    基数排序/桶排序 *统计将数组中的数字分配到桶中后,各个桶中的数字个数 *数组中每个数的每一位数根据大小分配到对应大小为0~9的桶 *将各个桶中的数字个数,转化成各个桶中最后一个数字的下标索引

    C++排序算法对比(桶排序等)

    本文将深入探讨在C++中实现的几种主要排序算法,包括归并排序、插入排序、冒泡排序、希尔排序、快速排序以及桶排序,并对它们的原理、优缺点和适用场景进行比较。 首先,让我们逐一了解这些排序算法。 1. **归并...

Global site tag (gtag.js) - Google Analytics