桶排序
程序员文章站
2022-05-24 12:48:54
...
桶排序适用于数据量大, 且分布均匀的情况.
程序代码:
package rickgong.algorithm.sort; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; /** * Created by rick on 2015/3/8. */ public class BucketSortTest { public static void main(String[] args) { BucketSortTest sortTest = new BucketSortTest(); int[] array = {84, 32, 87, 24, 67, 52, 85, 13, 53, 48, 21, 95, 98, 21, 45, 12, 75, 72, 54, 62}; sortTest.printArray(array); System.out.println("begin:"); sortTest.bucketSort(array, 20); } private void bucketSort(int[] array, int bucketCapacity) { //init buckets int maxValue = array[0]; int minValue = array[0]; for (int i = 0; i < array.length; i++) { if (array[i] > maxValue) { maxValue = array[i]; } if (array[i] < minValue) { minValue = array[i]; } } int bucketCount = (int) Math.ceil((maxValue - minValue + 1) * 1.0 / bucketCapacity); List<List<Integer>> buckets = new ArrayList<List<Integer>>(bucketCount); for (int i = 0; i < bucketCount; i++) { buckets.add(i, new ArrayList<Integer>()); } //fill buckets System.out.println("fill each bucket"); for (int i = 0; i < array.length; i++) { int bucketIndex = (array[i] - minValue) / bucketCapacity; buckets.get(bucketIndex).add(array[i]); printBuckets(buckets); System.out.println(); } //sort each bucket System.out.println("sort each bucket"); for (int i = 0; i < buckets.size(); i++) { Collections.sort(buckets.get(i)); } printBuckets(buckets); } private void printBuckets(List<List<Integer>> buckets) { for (int i = 0; i < buckets.size(); i++) { System.out.print("{"); List<Integer> bkt = buckets.get(i); for (int j = 0; j < bkt.size(); j++) { System.out.print(bkt.get(j) + "\t"); } System.out.print("}"); } } private void printArray(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i] + "\t"); } System.out.println(); } private void assertSorted(int[] array) { boolean sorted = true; for (int i = 0; i < array.length - 1; i++) { if (array[i] > array[i + 1]) { sorted = false; break; } } if (!sorted) { throw new RuntimeException("Not sorted"); } } }
输出结果:
84 32 87 24 67 52 85 13 53 48 21 95 98 21 45 12 75 72 54 62
begin:
fill each bucket
{}{}{}{84 }{}
{}{32 }{}{84 }{}
{}{32 }{}{84 87 }{}
{24 }{32 }{}{84 87 }{}
{24 }{32 }{67 }{84 87 }{}
{24 }{32 }{67 52 }{84 87 }{}
{24 }{32 }{67 52 }{84 87 85 }{}
{24 13 }{32 }{67 52 }{84 87 85 }{}
{24 13 }{32 }{67 52 53 }{84 87 85 }{}
{24 13 }{32 48 }{67 52 53 }{84 87 85 }{}
{24 13 21 }{32 48 }{67 52 53 }{84 87 85 }{}
{24 13 21 }{32 48 }{67 52 53 }{84 87 85 }{95 }
{24 13 21 }{32 48 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 }{32 48 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 }{32 48 45 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 }{84 87 85 75 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 }{84 87 85 75 72 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 54 }{84 87 85 75 72 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 54 62 }{84 87 85 75 72 }{95 98 }
sort each bucket
{12 13 21 21 24 }{32 45 48 }{52 53 54 62 67 }{72 75 84 85 87 }{95 98 }
begin:
fill each bucket
{}{}{}{84 }{}
{}{32 }{}{84 }{}
{}{32 }{}{84 87 }{}
{24 }{32 }{}{84 87 }{}
{24 }{32 }{67 }{84 87 }{}
{24 }{32 }{67 52 }{84 87 }{}
{24 }{32 }{67 52 }{84 87 85 }{}
{24 13 }{32 }{67 52 }{84 87 85 }{}
{24 13 }{32 }{67 52 53 }{84 87 85 }{}
{24 13 }{32 48 }{67 52 53 }{84 87 85 }{}
{24 13 21 }{32 48 }{67 52 53 }{84 87 85 }{}
{24 13 21 }{32 48 }{67 52 53 }{84 87 85 }{95 }
{24 13 21 }{32 48 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 }{32 48 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 }{32 48 45 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 }{84 87 85 75 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 }{84 87 85 75 72 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 54 }{84 87 85 75 72 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 54 62 }{84 87 85 75 72 }{95 98 }
sort each bucket
{12 13 21 21 24 }{32 45 48 }{52 53 54 62 67 }{72 75 84 85 87 }{95 98 }
上一篇: 两套mysql备份脚本