【十大经典排序算法】：桶排序及其JAVA代码实现

对于排序算法，相信每一个接触过编程的人都不会陌生，从最初在大学学习的冒泡排序、快速排序、选择排序到后来接触的归并排序、基数排序、桶排序...排序算法应该是实际编程中用得最多的算法之一。

原理

示意图

【十大经典排序算法】：桶排序示意图

1. 取最大值最小值
2. 定义桶
3. 将待排序的数分别放入桶中
4. 对每个桶分别排序
5. 依次将数从桶中取出

注意

1. 在空间允许的情况下尽量加大桶数目
2. 尽量保证数据均匀分配到桶中

java代码

public class BucketSort implements IArraySort {
<span class="hljs-comment">// 这里引用插入排序，用于对每个桶内元素进行单独排序</span>
purivate <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> InsertSort insertSort = <span class="hljs-keyword">new</span> InsertSort();

<span class="hljs-meta">@Override</span>
<span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span>[] sort(<span class="hljs-keyword">int</span>[] sourceArray) <span class="hljs-keyword">throws</span> Exception {
    <span class="hljs-comment">// 对 arr 进行拷贝，不改变参数内容</span>
    <span class="hljs-keyword">int</span>[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    <span class="hljs-keyword">return</span> bucketSort(arr, <span class="hljs-number">5</span>);
}

<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span>[] bucketSort(<span class="hljs-keyword">int</span>[] arr, <span class="hljs-keyword">int</span> bucketSize) <span class="hljs-keyword">throws</span> Exception {
    <span class="hljs-keyword">if</span> (arr.length == <span class="hljs-number">0</span>) {
        <span class="hljs-keyword">return</span> arr;
    }

    <span class="hljs-keyword">int</span> minValue = arr[<span class="hljs-number">0</span>];
    <span class="hljs-keyword">int</span> maxValue = arr[<span class="hljs-number">0</span>];
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> value : arr) {
        <span class="hljs-keyword">if</span> (value &lt; minValue) {
            minValue = value;
        } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (value &gt; maxValue) {
            maxValue = value;
        }
    }

    <span class="hljs-keyword">int</span> bucketCount = (<span class="hljs-keyword">int</span>) Math.floor((maxValue - minValue) / bucketSize) + <span class="hljs-number">1</span>;
    <span class="hljs-keyword">int</span>[][] buckets = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[bucketCount][<span class="hljs-number">0</span>];

    <span class="hljs-comment">// 利用映射函数将数据分配到各个桶中</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; arr.length; i++) {
        <span class="hljs-keyword">int</span> index = (<span class="hljs-keyword">int</span>) Math.floor((arr[i] - minValue) / bucketSize);
        buckets[index] = arrAppend(buckets[index], arr[i]);
    }

    <span class="hljs-keyword">int</span> arrIndex = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span>[] bucket : buckets) {
        <span class="hljs-keyword">if</span> (bucket.length &lt;= <span class="hljs-number">0</span>) {
            <span class="hljs-keyword">continue</span>;
        }
        <span class="hljs-comment">// 对每个桶进行排序，这里使用了插入排序</span>
        bucket = insertSort.sort(bucket);
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> value : bucket) {
            arr[arrIndex++] = value;
        }
    }
    <span class="hljs-keyword">return</span> arr;
}

<span class="hljs-comment">/**
* 自动扩容，并保存数据
*
* <span class="hljs-doctag">@param</span> arr
* <span class="hljs-doctag">@param</span> value
*/</span>
<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span>[] arrAppend(<span class="hljs-keyword">int</span>[] arr, <span class="hljs-keyword">int</span> value) {
    arr = Arrays.copyOf(arr, arr.length + <span class="hljs-number">1</span>);
    arr[arr.length - <span class="hljs-number">1</span>] = value;
    <span class="hljs-keyword">return</span> arr;
}

}