0%

排序算法

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 18k 阅读时长 ≈ 16 分钟

〇、对数器

对数器的作用是在没有Online Judge的情况下，我们自己实现的测试代码的工具。比如现在我们有一个要测试的方法a，我们需要：

  1. 实现一个绝对正确但是复杂度可以不好的方法b
  2. 实现一个随机样本产生器
  3. 实现比对的方法，即用来对比方法a与方法b产生的结果的比对方法
  4. 把方法a和方法b比对很多次来验证方法a是否正确
  5. 如果有一个样本使得比对出错， 打印样本分析是哪个方法出错
  6. 当样本数量很多时比对测试依然正确， 可以确定方法a已经正确

下面是用于测试数据结构为数组的排序算法的对数器代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class SortTestUtil {
    //随机样本产生器
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        //生成一个随机长度的数组，长度位于[0 - maxSize]之间
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        //为数组元素赋随机值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    //创建一个时间复杂度可以差但是绝对正确的方法
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }
    //比对方法
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

关于上述对数器的使用，可以参见下面冒泡排序的部分。

一、冒泡排序

思想：从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。
举例：
比如现在有数组[3,5,2,4,1]。开始时有指针j和j+1指向元素3和5，发现3小于5，那么不交换元素位置。指针j加1，此时j和j+1分别指向5和2，因为5大于2，所以交换元素位置。以此类推，当j指向最后第二个元素并交换元素位置之后，数组变为[3,2,4,1,5]，此时元素5已经排好序了。现在j重新指向0号位置，重新进行如上过程。因为最后一个元素5已经排好序了，所以指针j只需走到最后第三个元素即可停止。当第二大元素排好序后，第三次循环同理。

冒泡排序的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//冒泡排序算法
public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        for (int e = arr.length - 1; e > 0; e--) {
            //变量j向右走最远的坐标为 arr.length - 2
            //变量e走到坐标1即可停止
            for (int j = 0; j < e; j++) {
                if (arr[j] > arr[j + 1])
                    swap(arr, j, j + 1);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

我们可以使用对数器来验证如上冒泡排序算法的正确性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
    int testTime = 500000;
    int maxSize = 20;
    int maxValue = 100;
    boolean succeed = true;
    int[] testArr = null;
    for (int i = 0; i < testTime; i++) {
        int[] arr1 = SortTestUtil.generateRandomArray(maxSize, maxValue);
        testArr = SortTestUtil.copyArray(arr1);
        int[] arr2 = SortTestUtil.copyArray(arr1);
        BubbleSort.bubbleSort(arr1);
        SortTestUtil.comparator(arr2);
        if (!SortTestUtil.isEqual(arr1, arr2)) {
            succeed = false;
            SortTestUtil.printArray(testArr);
            SortTestUtil.printArray(arr1);
            break;
        }
    }
    System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}

冒泡排序的时间复杂度O(N^2)， 额外空间复杂度O(1)。

二、选择排序

思想：从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
举例：
现在有一数组[3,5,2,4,1]。开始时有两个指针minIndex和j分别指向3和5，然后j依次往后遍历，并分别与指针minIndex所指向的元素3进行对比，如果j所指向的元素小于minIndex所指向的元素，那么将minIndex设置为j，当j遍历完之后就得到了数组中最小元素的下标minIndex，此时将minIndex与0号元素交换位置，那么0号位置的元素就排好序了。下一次循环开始，minIndex指向1号位置元素，j指向2号位置元素，重复上述过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//选择排序
public class SelectionSort {

    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

选择排序的时间复杂度O(N^2)， 额外空间复杂度O(1)

三、插入排序

思想：每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。
举例：
现在有一数组[3,5,2,4,1]。开始时指针j指向1号元素5，将1号元素与0号元素进行对比，如果1号元素小于0号元素那么就交换位置。因为5大于3，所以不交换位置。下一次循环j指向2号元素，同样与前一个元素进行对比，因为2小于5所以交换位置，此时数组变为[3,2,5,4,1]。j减1指向1号元素2，同样的与前一个元素进行对比，因为2小于3所以交换元素位置，此时数组变为[2,3,5,4,1]。下一次循环j指向3号元素，然后进行上述过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//插入排序
public class InsertSort {

    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j-1])
                    swap(arr, j, j-1);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

插入排序的时间复杂度O(N^2)， 额外空间复杂度O(1)

四、希尔排序

希尔排序是希尔（Donald Shell） 于 1959 年提出的一种排序算法。 希尔排序也是一种插入排序， 它是简单插入排序经过改进之后的一个更高效的版本， 也称为缩小增量排序。

思想：希尔排序是把记录按下标的一定增量分组， 对每组使用直接插入排序算法排序； 随着增量逐渐减少， 每组包含的关键词越来越多， 当增量减至 1 时， 整个文件恰被分成一组， 算法便终止。

上面的算法思想阐述得可能不是很明了，下面就一个例子来讲解该算法的排序过程：

观察如下数组，以下数据元素颜色相同为一组：

初始增量gap = length / 2 = 5，意味着整个数组被分为5组：

对这5组分别进行直接插入排序，结果如下。可以看到，像3，5，6，0这些小元素都被调到前面了。

然后缩小增量 gap = 5 / 2 = 2，数组被分为2组，如下所示：

对以上2组再分别进行直接插入排序，结果如下。可以看到，此时整个数组的有序程度更近了一步。

再缩小增量gap = 2 / 2 = 1，此时，整个数组为1组，如下：

此时，仅仅需要对以上数组进行最后一次直接插入排序，即可完成整个数组的排序：

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ShellSort {

    public static void shellSort(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                while (j - gap >= 0 && arr[j] < arr[j - gap]) {
                    swap(arr, j, j - gap);
                    j -= gap;
                }
            }
        }// for
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

五、归并排序

思想：归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。
举例：
有一数组[3,5,2,4,1]，其归并排序中将数组以递归地方式分成两部分的过程如下图所示：
递归拆分过程
上图中仅涉及数组的拆分过程，并未涉及数组元素的排序和归并过程。观察上图左下角部分，数组[3,5]被拆分为子数组[3]和子数组[5]，此时我们需要将两个子数组进行排序然后并归并到原数组中的对应位置上(这里是0号和1号元素位置)。排序和归并的过程以下图的排序状态为例：

假设现在有一个指针i指向前半部分的首个元素位置，j指针指向后半部分的第一个元素位置。比较i和j所指向的元素，并将较小值拷贝到一个临时数组中，较小值所对应的指针往后移动一位，另一个指针不变。比如上图，j所指向的元素2小于i所指向的元素3,那么元素2会拷贝到临时数组中，指针j往后移动，如果元素2后还有一个元素4，那么显然i所指向的元素3会被拷贝到临时数组，i然后向后移动一位。进行上述过程中，i和j会向后移动，当其中一个指针数组越界后，即可结束上述过程。
如上图，j指针会先数组越界，那么将i指针及其后的所有元素拷贝进临时数组中。如果i先越界也同理。
以上过程即完成了数组元素的排序过程，然后将临时数组中排好序的元素拷贝回原数组中的对应位置中，便完成了归并过程。即在完成了上述步骤后，原数组变为[2,3,5,4,1]。
当递归完数组的后半部分[4,1]后，原数组会变为[2,3,5,1,4]。最后进行前后各半部分的排序和归并过程便得出最后的排序数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//归并排序
public class MergeSort {

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        mergeSortCore(arr, 0, arr.length - 1);
    }

    private static void mergeSortCore(int[] arr, int L, int R) {
        if (L == R)
            return;
        // 相比于(L + R) / 2，下面的更快且避免整型溢出
        int mid = L + ((R - L) >> 1);
        mergeSortCore(arr, L, mid);
        mergeSortCore(arr, mid + 1, R);
        merge(arr, L, R, mid);
    }

    private static void merge(int[] arr, int L, int R, int mid) {
        int[] help = new int[R - L + 1];
        int k = 0;// 指向数组help的指针
        int i = L;
        int j = mid + 1;
        while (i <= mid && j <= R)
            help[k++] = arr[j] <= arr[i] ? arr[j++] : arr[i++];

        while (i <= mid)
            help[k++] = arr[i++];

        while (j <= R)
            help[k++] = arr[j++];

        for (int u = 0; u < help.length; u++)
            arr[L + u] = help[u];
    }
}

归并排序的时间复杂度O(N*logN)， 额外空间复杂度O(N)

【补充】：
递归行为和递归行为时间复杂度的估算遵循如下master公式：
T(N) = a*T(N/b) + O(N^d)

1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b,a) = d -> 复杂度为O(N^d * logN)
3) log(b,a) < d -> 复杂度为O(N^d)

对于归并排序，长度为N的数组分为两次的T(N/2)时间复杂度的排序和O(N)的归并过程，所以a = b = 2，d = 1，即符合第2点log(b,a) = d，故时间复杂度为O(N*logN)。因为总的情况下需要长度为N的临时数组空间，故额外空间复杂度为O(N)。

六、随机快速排序

在讲随机快速排序前，有必要了解一下两个问题：

问题一

给定一个数组arr， 和一个数num， 请把小于等于num的数放在数组的左边， 大于num的数放在数组的右边。要求额外空间复杂度O(1)， 时间复杂度O(N)

分析：假设现在有一数组[4,5,1,2,9]。我们可以使用指针less指向数组的-1处，然后指针i从0号位往后遍历数组。如果i指向的元素大于num，那么i向右移动一位。如果小于等于num那么将i指向的元素与less + 1位置的元素交换位置，然后less和i向右移动一位。
由此less其左边的小于num的区域逐渐向右扩张，从而就把小于等于num的数放在数组的左边， 大于num的数放在数组的右边。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeftSmallNum {

    public static void leftSmallNum(int[] arr, int num) {
        if (arr == null || arr.length < 1)
            return;
        int less = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <= num)
                swap(arr, ++less, i);
        }
    }

    private static void swap(int[] arr, int less, int i) {
        int temp = arr[less];
        arr[less] = arr[i];
        arr[i] = temp;
    }
}

问题二

荷兰国旗问题：给定一个数组arr， 和一个数num， 请把小于num的数放在数组的左边， 等于num的数放在数组的中间， 大于num的数放在数组的右边。要求额外空间复杂度O(1)， 时间复杂度O(N)

与问题一类似，假设现在需要将小于2的数放在数组的左边，大于2的数放在数组的右边，等于2的数放在数组中间。

初始时有指针less指向-1，more指向arr.length。如果当前指针i所指向的元素大于num，那么与more - 1的元素交换位置，more向左移动一位，i指针不移动并继续判断。如果当前指针i所指向的元素小于num，那么与less + 1的元素交换位置，less向右移动一位，i指针也向右移动一位。如果当前指针i所指向的元素等于num，i指针向右移动一位。当i大于等于more时，即可结束上述过程。

下面代码，实现了自定义边界L和R，而不再是简单的指向-1和数组的长度arr.length。其能够实现指定范围内的荷兰国旗问题的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class NetherLandsFlag {

    // 返回值为数组中等于num的左右边界（包含）
    public static int[] netherLandsFlag(int[] arr, int L, int R, int num) {
        int less = L - 1;
        int more = R + 1;
        int cur = L;
        while (cur < more) {
            if (arr[cur] > num)
                swap(arr, cur, --more);
            else if (arr[cur] < num)
                swap(arr, cur++, ++less);
            else
                cur++;
        }
        return new int[] { less + 1, more - 1 };
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

我们可以用荷兰国旗问题来改进快速排序。由于荷兰国旗问题实现了数组中等于num的元素的上下边界值，然后我们通过上下边界值可以递归地实现数组前半部分和后半部分，最后实现了数组的整体有序。需要注意的是：不同于荷兰国旗问题中num的值是自己给定的，随机快速排序算法中的num值是当前数组的最后一个元素。

实现代码

我们看一下随机排序算法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//随机快速排序
public class QuickSort {

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int L, int R) {
        if (L < R) {
            // 随机将数组L ~ R - 1内的某个元素与R位置的元素交换位置
            swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
            int[] p = partition(arr, L, R, arr[R]);
            quickSort(arr, L, p[0] - 1);//前半部分
            quickSort(arr, p[1] + 1, R);//后半部分
        }
    }

    private static int[] partition(int[] arr, int L, int R, int num) {
        int less = L - 1;
        int more = R;// more指向R
        int cur = L;
        while (cur < more) {
            if (arr[cur] > num)
                swap(arr, cur, --more);
            else if (arr[cur] < num)
                swap(arr, cur++, ++less);
            else
                cur++;
        }
        swap(arr, more, R);//交换元素
        return new int[] { less + 1, more };
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

我们观察以下代码：

1
2
// 随机将数组L ~ R - 1内的某个元素与R位置的元素交换位置
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);

为什么要随机从数组中选取一个元素然后与R位置的元素交换位置，然后将其作为num呢？我们下面来分析一下为什么需要随机的选择。

假设现在有一个数组[5,4,3,2,1]。如果我们不随机选择，而是每次将最右边的元素（第一次递归时是元素1）作为num，那么我们会发现大于1的元素占了4个，快速排序算法最终会退化为时间复杂度为O（n * n）的算法。如果是随机选择的，那么在期望上随机选择排序的时间复杂度是O(N * logN)。

随机快速排序的时间复杂度是O(N*logN)， 额外空间复杂度是O(logN)。

七、堆排序

堆即为完全二叉树。下面我们使用数组来实现大根堆，所谓大根堆就是符合树中的所有子树的根大于其所有子节点的完全二叉树。比如下面即为一个大根堆：
大根堆
其物理存储结构为数组，如下所示：
物理数组结构
我们可以通过如下公式来求得当前节点的左孩子、右孩子和父节点的位置，假设节点的位置为index：

  1. 左孩子：2 * index + 1
  2. 右孩子：2 * index + 2
  3. 父节点：(index - 1) / 2

heapInsert

当一个元素加入大根堆时，可以使用heapInsert方法对该元素进行调整，即若该元素大于其父节点的值，那么就往上浮。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 大值往上浮
//index为该元素在数组中的下标
public static void heapInsert(int[] arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

heapify

当大根堆中的顶部某元素的值变小了，就比如当元素5变为0时，即：

为了符合大根堆的特性，我们需调整大根堆，将0往下沉，最后符合如下图示：

上述过程的代码具体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 小值往下沉
 public static void heapify(int[] arr, int parent, int size) {
        // arr[parent]往下沉的过程
        int left = (parent << 1) + 1;
        // 假设left为最大值
        int largest = left;
        // left < size说明左孩子存在
        while (left < size) {
            // 在右孩子存在的情况下，将左右孩子较大者的下标赋给largest，其中left + 1为右孩子
            largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            // 左右孩子较大者与父节点比较，将较大者赋给largest
            largest = arr[largest] > arr[parent] ? largest : parent;
            // 如果父节点最大，则说明不再需要进行下沉过程
            if (largest == parent)
                break;
            // 父节点下沉
            swap(arr, parent, largest);
            parent = largest;
            left = (parent << 1) + 1;
        }
    }

理解了上述两个方法后，我们就可以使用如下方法完成堆排序的过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return;
    int size = arr.length;
    //构建大根堆，即往大根堆插入数据的过程
    for (int i = 0; i < size; i++)
        heapInsert(arr, i);
    //从大根堆中删除元素，并达到排序效果
    while (size > 1) {
        // 堆顶最大元素移动数组最后位置
        swap(arr, 0, size - 1);
        // 逻辑上删除堆的最后一个元素
        heapify(arr, 0, --size);
    }
}

堆排序的时间复杂度O(N*logN)， 额外空间复杂度O(1)

八、计数排序

计数排序属于桶排序的一种，是非基于比较的排序， 与被排序的样本的实际数据状况很有关系， 所以实际中并不经常使用。

为什么说计数排序与被排序的样本的实际数据状况很有关系呢？先看下面的例子，我们可以实现对以下数组进行排序，另外假设数组中的元素大小需满足[0 ~ length] 。

我们可以创建一个长度为length + 1的数组作为桶数组，每个桶用于保存原数组中的某元素出现的次数。其中元素值对应于桶数组中元素的下标。比如上面的数组经过元素个数统计后，其桶数组如下：

其表示元素0出现的次数为1，元素1出现的次数为2，其他同理。得到桶数组后，我们可以依靠该数组的信息将数据以有序的方式拷贝回原数组中。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//计数排序
public class CountSort {

    // 规定arr的元素符合0 ~ arr.length
    public static void countSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        int[] bucket = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        int index = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0)
                arr[index++] = j;
        }
    }
}

我们可以规定数组arr中的元素需满足0 到该数组中的最大值max，此时我们就需要创建一个长度为max + 1为的桶数组。当max很大时，我们不得不创建很大的桶数组，这就是我们上面说计数排序与被排序的样本的实际数据状况很有关系的原因。更改的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//计数排序
public class CountSort {

    // 规定arr的元素符合0 ~ max
    public static void countSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++)
            max = Math.max(arr[i], max);
        int[] bucket = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        int index = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0)
                arr[index++] = j;
        }
    }
}

计数排序的时间复杂度为O(N)， 额外空间复杂度为O(N)。

补充问题

给定一个数组， 求如果排序之后， 相邻两数的最大差值， 要求时间复杂度O(N)， 且要求不能用非基于比较的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class MaxGap {

    public static int maxGap(int[] arr) {
        if (arr == null || arr.length < 2)
            return 0;
        int size = arr.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        // 获取数组中的最大最小值
        for (int i = 0; i < size; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
        }
        if (max == min)
            return 0;
        // 创建桶，每个桶包含boolean， min，max三个值
        boolean[] hasNum = new boolean[size + 1];
        int[] mins = new int[size + 1];
        int[] maxs = new int[size + 1];
        // 获取每个桶中的最小和最大值，以及是否同中是否有值
        int bid = 0;
        for (int i = 0; i < size; i++) {
            bid = bucket(arr[i], size, max, min);
            mins[bid] = hasNum[bid] ? Math.min(mins[bid], arr[i]) : arr[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], arr[i]) : arr[i];
            hasNum[bid] = true;
        }
        // 获取桶之间的最大差值
        int res = 0;
        int lastMax = maxs[0];
        for (int i = 1; i <= size; i++) {
            if (hasNum[i]) {
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }

    // 获取当前num所对应的桶号
    public static int bucket(long num, long size, long max, long min) {
        return (int) ((num - min) * size / (max - min));
    }
}
------ 本文结束------