利用桶排序进行过河处理
接上一篇的过河问题，题目尾出了一个关于桶排序的问题，在这里跟大家讲一讲桶排序，
何为桶排序。
桶排序为利用一个数组下标存储相应数据，进行直接排序。比如 10分制评分情况，评委打分 2 9 1 8 6 此时利用桶排序申请11个数组位置arr[0 ~ 10] 相应分数存储到相应下标。arr[n]存储的是出现了多少次（arr[3] = 4, 则表示3分的情况下出现了4次）。
优点、缺点
优点有：简单，直观，相对稳定，业务场景合适即数据相对密集，离散度不高，桶排序的速度甚至比快速排序还快
缺点有：离散情况下超级耗内存(敲重点)，相对业务场景较局限。如果出现超大数时，反而浪费更多时间循环空数据。
复杂度
O（M+C）其中C=N*(logN-logM)
综上所述，上题 过河问题，体重的数据类型为 int ，且体重200KG以内完全够(以船的极限重量作为 桶的最大index也是满足的)，所以此场景优选桶排序是一个很好的解法(可能还有更好的 ,说话留一线).
代码如下
public int numRescueBoats(int[] people, int limit) {if(people.length == 1){return 1;}//计数桶排序int[] bucket = new int[limit+1];for (int i = 0; i < people.length; i++) {bucket[people[i]]++;}int L = 0;int R = bucket.length - 1;int res = 0;while(L <= R){if(bucket[R] == 0 || bucket[L] == 0){bucket[R] == 0 && R--;bucket[L] == 0 && L++;continue;}if(R + L <= limit){if(L == R){res += Math.ceil(bucket[L] / 2);break;}else{//取出两个最小的数，保证2个配对，调整次数小的指向下一位int min = Math.min(bucket[R], bucket[L]);res += min;bucket[R] -= min;bucket[L] -= min;}}else{res += bucket[R];R--;}}return res;};
关于Array.sort( )，知识讲解见后期文章讲解，在此先明白合为桶排序，理解好桶排序。