添加桶排序算法

wangzheng0822 · Jun 1, 2019 · 102edb3 · 102edb3
1 parent 3550204
commit 102edb3
Showing 1 changed file with 130 additions and 0 deletions.
diff --git a/java/13_sorts/BucketSort.java b/java/13_sorts/BucketSort.java
@@ -0,0 +1,130 @@
+/**
+ * @Description:桶排序算法
+ * @Author: Hoda
+ * @Date: Create in 2019-06-01
+ * @Modified By:
+ * @Modified Date:
+ */
+public class BucketSort {
+
+    /**
+     * 桶排序
+     *
+     * @param arr 数组
+     * @param bucketSize 桶容量
+     */
+    public static void bucketSort(int[] arr, int bucketSize) {
+        if (arr.length == 0) {
+            return;
+        }
+
+        // 数组最小值
+        int minValue = arr[0];
+        // 数组最大值
+        int maxValue = arr[1];
+        for (int i = 0; i < arr.length; i++) {
+            if (arr[i] < minValue) {
+                minValue = arr[i];
+            } else if (arr[i] > maxValue) {
+                maxValue = arr[i];
+            }
+        }
+
+        // 桶数量
+        int bucketCount = (maxValue - minValue) / bucketSize + 1;
+        int[][] buckets = new int[bucketCount][bucketSize];
+        int[] indexArr = new int[bucketCount];
+
+        // 将数组中值分配到各个桶里
+        for (int i = 0; i < arr.length; i++) {
+            int bucketIndex = (arr[i] - minValue) / bucketSize;
+            if (indexArr[bucketIndex] == buckets[bucketIndex].length) {
+                ensureCapacity(buckets, bucketIndex);
+            }
+            buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i];
+        }
+
+        // 对每个桶进行排序，这里使用了快速排序
+        int k = 0;
+        for (int i = 0; i < buckets.length; i++) {
+            if (indexArr[i] == 0) {
+                continue;
+            }
+            quickSortC(buckets[i], 0, indexArr[i] - 1);
+            for (int j = 0; j < indexArr[i]; j++) {
+                arr[k++] = buckets[i][j];
+            }
+        }
+    }
+
+    /**
+     * 数组扩容
+     *
+     * @param buckets
+     * @param bucketIndex
+     */
+    private static void ensureCapacity(int[][] buckets, int bucketIndex) {
+        int[] tempArr = buckets[bucketIndex];
+        int[] newArr = new int[tempArr.length * 2];
+        for (int j = 0; j < tempArr.length; j++) {
+            newArr[j] = tempArr[j];
+        }
+        buckets[bucketIndex] = newArr;
+    }
+
+    /**
+     * 快速排序递归函数
+     *
+     * @param arr
+     * @param p
+     * @param r
+     */
+    private static void quickSortC(int[] arr, int p, int r) {
+        if (p >= r) {
+            return;
+        }
+
+        int q = partition(arr, p, r);
+        quickSortC(arr, p, q - 1);
+        quickSortC(arr, q + 1, r);
+    }
+
+    /**
+     * 分区函数
+     *
+     * @param arr
+     * @param p
+     * @param r
+     * @return 分区点位置
+     */
+    private static int partition(int[] arr, int p, int r) {
+        int pivot = arr[r];
+        int i = p;
+        for (int j = p; j < r; j++) {
+            if (arr[j] <= pivot) {
+                swap(arr, i, j);
+                i++;
+            }
+        }
+
+        swap(arr, i, r);
+        return i;
+    }
+
+    /**
+     * 交换
+     *
+     * @param arr
+     * @param i
+     * @param j
+     */
+    private static void swap(int[] arr, int i, int j) {
+        if (i == j) {
+            return;
+        }
+
+        int tmp = arr[i];
+        arr[i] = arr[j];
+        arr[j] = tmp;
+    }
+}