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

1.计数排序

定义

简而言之，就是对出现的数据，用一个一维有序数组，存放每个数据出现的次数，然后按照顺序打印出现的数据

算法描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，并且打印。

Java代码

这里有五个数5,2,5,3,8需要用计数排序进行排序，首先确定最大的数为10（假设），然后创建一个一维数组用做桶，注意桶的数量应该是10+1，然后对这五个数进行分别入桶，5进入bucket[5]两次，所以bucket[5]=2，同理可得bucket[2]=1,bucket[3]=1,bucket[8]=1，接下来就是打印，对所有的桶进行遍历，bucket[2]只有一个值，打印2，bucket[3]只有一个值1，打印3，同理可得，如图所示

public static int[] sort(int[] nums){        int max_num = 10;        int[] bucket = new int[max_num+1];        for(int i = 0;i

空间复杂度

M表示桶的数量，N表示要排序的数的个数

• 时间复杂度O(M+N)
• 空间复杂度也是O(M+N)
• 其排序速度快于任何比较排序算法

2.桶排序

定义

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）,利用了空间换时间的方法.

算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

Java代码

代码首先定义有10个桶，然后随机生成10000个数字，将这10000个均匀分布的数，要分别放入到10个桶，0桶存放0-1000,1桶存放1001-2000，同理可得，如图显示就是0-100的数，然后放进10个桶，桶里面的数据然后在进行排序

//桶排序：将N个数，分成m个桶，桶之间的元素递增，然后对桶内的元素进行排序，最后输出所有元素        int bucketSize = 10;        int arraySize = 10000;        public static void main(String[] args) {            BucketSortAdvanced bs = new BucketSortAdvanced();            int[] array = bs.getArray();            bs.bucketSort(array);        }        public int[] getArray() {            int[] arr = new int[arraySize];            Random r = new Random();            for (int i = 0; i < arraySize; i++) {                arr[i] = r.nextInt(100000);            }            return arr;        }        public void bucketSort(int[] a) {            @SuppressWarnings("unchecked")            List
   
     bucket[] = new ArrayList[bucketSize];            for (int i = 0; i < a.length; i++) {                int temp = a[i] / 10000;                if (bucket[temp] == null) {                    bucket[temp] = new ArrayList
    
     ();                }                bucket[temp].add(a[i]);            }            // 对各个桶内的list中的元素进行排序            for (int j = 0; j < bucketSize; j++) {                insertSort(bucket[j]);// 对桶内的元素进行排序                printList(bucket[j]);// 输出桶中的元素            }        }        public void printList(List
     
       list) {            while (list.size() > 0) {                System.out.print(list.remove(0) + "\t");            }        }        public void insertSort(List
      
        list) {// 对每个list进行排序            Collections.sort(list);    }
      
     
    
   

时间复杂度 空间复杂度

M表示数组的个数，也就是待排序的数目，N 表示桶的数目

• 时间复杂度O(M+N）
• 空间复杂度O(M+N)

转载地址：http://lzcii.baihongyu.com/