排序算法---最快最简单的桶排序

前言

一直做客户端开发，实际上很少用到算法，但是为了即将到来的面试，还是得准备一下的。准备找书开始复习一下算法，先从最简单的排序开始做起吧。 一步一个脚印。学习，记录，积累 = 任务，打怪，升级。

桶排序的思想

如果需要对数据范围在0~n的整数进行排序，我们需要n+1个桶，来记录0~n之间每一个数字出现的次数，我们将桶按照0~n编号，然后将出现的数字放在与编号相等的桶里，并统计每个桶内数字的个数，待全部的数字装好。我们就可以按照指定的顺序，将有数字的桶输出其编号，桶内有几个数字，就输出几次。 如下图：

Java代码实现

输入n个数（0~1000），实现从小到大排序。

public class BucketSort { public static void main(String[] args) { System.out.println("输入排序的个数n："); Scanner input = new Scanner(System.in); int n = input.nextInt(); int array[] = new int[1001]; //初始化,假设在0~1000 for (int i = 0; i <= 1000; i++) { array[i] = 0; } System.out.println("请输入要排序的数字："); for (int i = 0; i < n; i++) { int a = input.nextInt(); array[a]++; } System.out.println("排序结果为："); for (int i = 0; i <= 1000; i++) { for (int j = 0; j < array[i]; j++) { System.out.print(i + " "); } } } }

测试结果

复杂度分析

初始化循环了m（表示数的范围）次。 输入循环了n次。 输出循环了m+n次。 算法的时间复杂度是O(m+n+m+n)即O(2*(m+n))。我们在说时间复杂度的时候可以忽略较小 的常数，最终桶排序的时间复杂度为O(m+n)。 还有一点，在表示时间复杂度的时候，n和m通常用大写字母即O(M+N)。