桶排序

简介 桶排序是一种典型的拿空间换时间的一种算法,通过几倍于原排序数列的空间,利用不断地运算,存取操作然后完成排序
桶排序过程中存在两个关键环节:
  • 元素值域的划分,也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择,若规则设计的过于模糊、宽泛,则可能导致待排序集合中所有元素全部映射到一个桶上,则桶排序向比较性质排序算法演变。若映射规则设计的过于具体、严苛,则可能导致待排序集合中每一个元素值映射到一个桶上,则桶排序向计数排序方式演化。

  • 排序算法的选择,从待排序集合中元素映射到各个桶上的过程,并不存在元素的比较和交换操作,在对各个桶中元素进行排序时,可以自主选择合适的排序算法,桶排序算法的复杂度和稳定性,都根据选择的排序算法不同而不同。

算法过程

  1. 根据待排序集合中最大元素和最小元素的差值范围和映射规则,确定申请的桶个数;

  2. 遍历待排序集合,将每一个元素移动到对应的桶中;

  3. 对每一个桶中元素进行排序,并移动到已排序集合中。

步骤 3 中提到的已排序集合,和步骤 1、2 中的待排序集合是同一个集合。与计数排序不同,桶排序的步骤 2 完成之后,所有元素都处于桶中,并且对桶中元素排序后,移动元素过程中不再依赖原始集合,所以可以将桶中元素移动回原始集合即可。

需要注意的是由于这个算法很大程度上有浪费空间的行为发生。



下面就直接看代码吧!


import java.text.SimpleDateFormat;

import java.util.Date;


public class BucketSort {

static int counter = 0;

static int arrSize = 8000000;// 此处实测80000数据大概是1s左右


public static void main(String[] args) {

// TODO Auto-generated method stub

// 产生随机数

int arr[] = new int[arrSize];

// int arr[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };

for (int i = 0; i < arrSize; i++) {

arr[i] = (int) (Math.random() * 8000000);

}


// System.out.println(Arrays.toString(arr));

Date dateStart = new Date();

SimpleDateFormat format = new SimpleDateFormat("YYYY-MM-DD hh:mm:ss");

String start = format.format(dateStart);

System.out.println("开始时间:" + start);


// 测试数组

bucketSort(arr);


Date endStart = new Date();

String end = format.format(endStart);

System.out.println("结束时间:" + end);

// System.out.println(Arrays.toString(arr));

// TODO Auto-generated method stub


}


public static void bucketSort(int arr[]) {

int[][] bucket = new int[10][arr.length];

int bucketCounts[] = new int[10];

int max = 0, times = 1;

// 找出最大的数确定排序的次数

for (int i = 0; i < arr.length; i++) {

if (max < arr[i])

max = arr[i];

}


while (max > 0) {

// 放入数据

for (int i = 0; i < arr.length; i++) {

int temp = (arr[i] / times) % 10;

bucket[temp][bucketCounts[temp]] = arr[i];

bucketCounts[temp]++;

}

// 取出数据

for (int i = 0, index = 0; i < 10; i++) {

if (bucketCounts[i] != 0) {// 表示有数据

for (int j = 0; j < bucketCounts[i]; j++) {

arr[index] = bucket[i][j];

index++;

}

bucketCounts[i] = 0;

}

}

times *= 10;

max /= 10;

}

}

}

这个算法更接近线性时间复杂度,排序的速度是比较快的。

文章评论

Top