桶排序-白红宇

桶排序

阅读量：7210 次

发布时间：2019-06-29

本文共 2322 字，大约阅读时间需要 7 分钟。

1 package blog; 2  3 import java.util.Scanner; 4  5 /** 6  * 个人理解： 1、桶排序是稳定的 2、桶排序是非常快的 3、桶排序是一种比较耗空间的算法，因为它是建立在已知数据上来 确定桶的个数。 7  *  8  * @author 霍礼平 2017年8月10日 9  *10  */11 public class 桶排序 {12 13     /**14      * 如果一组确定的数据中最大的数是10，最小的数是015      */16     // 首先申请大小为11的数组17     static int barrel[] = new int[11];18 19     // 初始化20     public static void init() {21         // 初始化数组各个元素都为022         for (int i = 0; i <= 10; i++) {23             barrel[i] = 0;24         }25     }26 27     public static void method1() {28         System.out.print("第一种方式从小到大");29         // 依次判断barrel[0]~barrel[10]各个元素出现的次数，总共打印10个下标，0次不打印30         for (int i = 0; i < 10; i++) {31             for (int j = 1; j <= barrel[i]; j++) {32                 System.out.print(i + " ");33             }34         }35         System.out.println();36         System.out.print("从大到小");37         for (int i = 10; i>=0; i--) {38             for (int j = 1; j <= barrel[i]; j++) {39                 System.out.print(i + " ");40             }41         }42     }43 44     // 或者用这种方法，但是barrel[i]--会使每个桶内的元素个数降到0，既桶被清空45     public static void method2() {    46         System.out.print("第二种方式从小到大");47         // 依次判断barrel[0]~barrel[10]各个元素出现的次数，总共打印10个下标，0次不打印48         for (int i = 0; i < 10; i++) {49             for (int j = 1; j <= barrel[i]; barrel[i]--) {50                 System.out.print(i + " ");51             }52         }53     }54 55     public static void main(String[] args) {56         while (true) {57             init();58             // 读入5个整数,最大数不能超过1059             Scanner a = new Scanner(System.in);60             System.out.println();61             System.out.println("请输入要排序的个数，最大数不能超过10");62             int sum = a.nextInt();63             System.out.println("这"+sum+"个数一次为：");64             for (int i = 0; i < sum; i++) {65                 int input = a.nextInt();66                 if(input>10){67                     System.out.println("最大数不能超过10");68                     break;69                 }70                 // 核心，输入的数和对应的数组下标一致时，对应的数组加一，出现几次就加几次71                 barrel[input]++;72             }73             method1();74             System.out.println();75             method2();76         77         }78     }79 80 }

运行结果：