冒泡排序
每轮冒泡不断地比较相邻的两个元素，如果它们是逆序的，则交换它们的位置
下一轮冒泡，可以调整未排序的右边界，减少不必要比较每一轮选择，找出最大（最小）的元素，并把它交换到合适的位置
private static void bubble(int[] a) {// 初始化 j 为数组的最后一个索引int j = a.length - 1;// 外层循环：持续遍历直到没有需要交换的元素为止while (true) {// 初始化 x 为 0，用于记录最后一次交换的位置int x = 0;// 内层循环：从头到 j 索引位置进行比较和交换for (int i = 0; i < j; i++) {// 如果当前元素大于下一个元素，则交换它们if (a[i] > a[i + 1]) {// 交换 a[i] 和 a[i + 1]int t = a[i];a[i] = a[i + 1];a[i + 1] = t;// 更新 x 为最后一次交换的位置x = i;}}// 更新 j 为最后一次交换的位置j = x;// 如果 j 已经变为 0，说明没有更多的元素需要排序，退出循环if (j == 0) {break;}}
}选择排序
每一轮选择，找出最大（最小）的元素，并把它交换到合适的位置
public static void sort(int[] a) {// 1. 选择轮数为数组长度减1 (a.length - 1)// 2. 每一轮将当前未排序部分的最大值放到正确的位置上// 初始时 right 指向数组的最后一个索引，每一轮递减// 外层循环：控制需要排序的轮数for (int right = a.length - 1; right > 0; right--) {// 初始化 max 为当前未排序部分的最后一个索引int max = right;// 内层循环：遍历当前未排序部分，找到最大值的索引for (int i = 0; i < right; i++) {// 如果当前元素大于已知的最大值，则更新 max 的值if (a[i] > a[max]) {max = i;}}// 如果最大值的索引不是当前未排序部分的最后一个索引，则交换它们if (max != right) {swap(a, max, right);}}
}// 辅助方法：交换数组中两个指定索引处的元素
private static void swap(int[] a, int i, int j) {// 使用临时变量 t 来交换 a[i] 和 a[j]int t = a[i];a[i] = a[j];a[j] = t;
}堆排序
建立大顶堆
每次将堆顶元素（最大值）交换到末尾，调整堆顶元素，让它重新符合大顶堆特性
public class HeapSort {/*** 对数组进行堆排序** @param a 待排序的数组*/public static void sort(int[] a) {// 第一步：将数组转换为最大堆（建堆）heapify(a, a.length);// 第二步：逐步将堆顶元素（最大值）与当前未排序部分的最后一个元素交换，并调整堆for (int right = a.length - 1; right > 0; right--) {// 将堆顶元素（最大值）与当前未排序部分的最后一个元素交换swap(a, 0, right);// 调整堆，使其重新满足最大堆的性质down(a, 0, right);}}/*** 建堆操作：将数组转换为最大堆** @param array 数组* @param size 数组的有效大小*/private static void heapify(int[] array, int size) {// 从最后一个非叶子节点开始，依次向上调整每个节点for (int i = size / 2 - 1; i >= 0; i--) {// 对每个非叶子节点进行下沉操作down(array, i, size);}}/*** 下沉操作：确保某个节点及其子树满足最大堆的性质** @param array 数组* @param parent 当前需要调整的父节点索引* @param size 数组的有效大小*/private static void down(int[] array, int parent, int size) {while (true) {// 计算左孩子和右孩子的索引int left = parent * 2 + 1;int right = left + 1;int max = parent;// 如果左孩子存在且大于当前最大值，则更新最大值索引if (left < size && array[left] > array[max]) {max = left;}// 如果右孩子存在且大于当前最大值，则更新最大值索引if (right < size && array[right] > array[max]) {max = right;}// 如果最大值索引没有变化，说明当前节点已经满足最大堆的性质，退出循环if (max == parent) {break;}// 交换父节点和最大值节点swap(array, max, parent);// 更新父节点索引为最大值节点索引，继续向下调整parent = max;}}/*** 交换数组中两个指定索引处的元素** @param a 数组* @param i 索引 i* @param j 索引 j*/private static void swap(int[] a, int i, int j) {// 使用临时变量 t 来交换 a[i] 和 a[j]int t = a[i];a[i] = a[j];a[j] = t;}
}插入排序
将数组分为两部分 [0 .. low-1] [low .. a.length-1]，左边 [0 .. low-1] 是已排序部分 ，右边 [low .. a.length-1] 是未排序部分 ，每次从未排序区域取出 low 位置的元素, 插入到已排序区域
public static void sort(int[] a) {// 遍历数组中的每个元素，从第二个元素开始（索引为1）for (int low = 1; low < a.length; low++) {// 将 low 位置的元素存储在临时变量 t 中int t = a[low];// 初始化 i 为已排序区域的最后一个索引（即 low - 1）int i = low - 1; // 已排序区域指针// 在已排序区域中从后向前扫描，寻找插入位置while (i >= 0 && t < a[i]) { // 没有找到插入位置// 将大于 t 的元素向右移动一位，空出插入位置a[i + 1] = a[i]; i--;}// 找到插入位置if (i != low - 1) { // 如果 i 没有变化，说明 t 应该放在原位a[i + 1] = t;}}
}希尔排序
简单的说，就是分组实现插入，每组元素间隙称为 gap，每轮排序后 gap 逐渐变小，直至 gap 为 1 完成排序，对插入排序的优化，让元素更快速地交换到最终位置
public static void sort(int[] a) {// 初始间隔 gap 设为数组长度的一半 (a.length >> 1 等价于 a.length / 2)for (int gap = a.length >> 1; gap > 0; gap = gap >> 1) {// 对每个间隔 gap 进行插入排序for (int low = gap; low < a.length; low++) {// 将 low 位置的元素存储在临时变量 t 中int t = a[low];// 初始化 i 为已排序区域的指针（相对于 low 向前 gap 个位置）int i = low - gap;// 在已排序区域中从后向前扫描，寻找插入位置while (i >= 0 && t < a[i]) { // 没有找到插入位置// 将大于 t 的元素向右移动 gap 位，空出插入位置a[i + gap] = a[i];i -= gap; // 更新 i 为前一个间隔位置}// 找到插入位置if (i != low - gap) {// 插入 t 到正确的位置a[i + gap] = t;}}}
}归并排序
每次从中间切一刀，处理的数据少一半，当数据仅剩一个时可以认为有序，当数据仅剩一个时可以认为有序
import java.util.Arrays;public class MergeSort {/*** 合并两个已排序的子数组** @param a1 原始数组* @param i 左子数组的起始索引* @param iEnd 左子数组的结束索引* @param j 右子数组的起始索引* @param jEnd 右子数组的结束索引* @param a2 辅助数组*/public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {int k = i; // 初始化目标数组的索引 k 为起始位置 i// 当两个子数组都没有处理完时，比较并合并它们while (i <= iEnd && j <= jEnd) {if (a1[i] < a1[j]) {a2[k] = a1[i]; // 将较小的元素放入目标数组 a2i++; // 移动指针 i} else {a2[k] = a1[j]; // 将较小的元素放入目标数组 a2j++; // 移动指针 j}k++; // 移动目标数组的索引 k}// 如果左子数组还有剩余元素，复制到目标数组 a2if (i > iEnd) {System.arraycopy(a1, j, a2, k, jEnd - j + 1);}// 如果右子数组还有剩余元素，复制到目标数组 a2if (j > jEnd) {System.arraycopy(a1, i, a2, k, iEnd - i + 1);}}/*** 归并排序的入口函数** @param a1 待排序的数组*/public static void sort(int[] a1) {int[] a2 = new int[a1.length]; // 初始化辅助数组 a2split(a1, 0, a1.length - 1, a2); // 调用 split 方法进行递归排序}/*** 递归地分割数组并进行排序** @param a1 原始数组* @param left 子数组的起始索引* @param right 子数组的结束索引* @param a2 辅助数组*/private static void split(int[] a1, int left, int right, int[] a2) {// 基本情况：如果子数组只有一个元素，则不需要进一步排序if (left == right) {return;}// 分割点 m，将数组分成两部分int m = (left + right) >>> 1;// 递归调用 split 方法对左半部分进行排序split(a1, left, m, a2);// 递归调用 split 方法对右半部分进行排序split(a1, m + 1, right, a2);// 合并两个已排序的子数组merge(a1, left, m, m + 1, right, a2);// 将合并后的结果从辅助数组 a2 复制回原数组 a1System.arraycopy(a2, left, a1, left, right - left + 1);}public static void main(String[] args) {int[] array = {5, 2, 4, 6, 1, 3};System.out.println("Before sorting: " + Arrays.toString(array));sort(array);System.out.println("After sorting: " + Arrays.toString(array));}
}非递归实现：
public class BottomUpMergeSort {/*** 合并两个已排序的子数组** @param a1 原始数组* @param i 左子数组的起始索引* @param iEnd 左子数组的结束索引* @param j 右子数组的起始索引* @param jEnd 右子数组的结束索引* @param a2 辅助数组*/public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {int k = i; // 初始化目标数组的索引 k 为起始位置 i// 当两个子数组都没有处理完时，比较并合并它们while (i <= iEnd && j <= jEnd) {if (a1[i] < a1[j]) {a2[k] = a1[i]; // 将较小的元素放入目标数组 a2i++; // 移动指针 i} else {a2[k] = a1[j]; // 将较小的元素放入目标数组 a2j++; // 移动指针 j}k++; // 移动目标数组的索引 k}// 如果左子数组还有剩余元素，复制到目标数组 a2if (i > iEnd) {System.arraycopy(a1, j, a2, k, jEnd - j + 1);}// 如果右子数组还有剩余元素，复制到目标数组 a2if (j > jEnd) {System.arraycopy(a1, i, a2, k, iEnd - i + 1);}}/*** 自底向上的归并排序入口函数** @param a1 待排序的数组*/public static void sort(int[] a1) {int n = a1.length;int[] a2 = new int[n]; // 初始化辅助数组 a2// 从宽度为1开始，逐步增加宽度，直到覆盖整个数组for (int width = 1; width < n; width *= 2) {// 对每个宽度为 width 的子数组进行合并for (int i = 0; i < n; i += 2 * width) {// 计算左子数组的结束索引 m 和右子数组的结束索引 jint m = Integer.min(i + width - 1, n - 1);int j = Integer.min(i + 2 * width - 1, n - 1);// 打印当前合并的子数组范围（调试信息）System.out.println("Merging subarrays from index " + i + " to " + m + " and from " + (m + 1) + " to " + j);// 合并两个子数组并将结果存入辅助数组 a2merge(a1, i, m, m + 1, j, a2);}// 将辅助数组 a2 中的结果复制回原数组 a1System.arraycopy(a2, 0, a1, 0, n);}}public static void main(String[] args) {int[] array = {5, 2, 4, 6, 1, 3};System.out.println("Before sorting: " + java.util.Arrays.toString(array));sort(array);System.out.println("After sorting: " + java.util.Arrays.toString(array));}
}归并+插入
import java.util.Arrays;public class HybridSort {/*** 插入算法>排序算法** @param a 待排序的数组* @param left 子数组的起始索引* @param right 子数组的结束索引*/public static void insertion(int[] a, int left, int right) {// 从 left + 1 开始遍历到 rightfor (int low = left + 1; low <= right; low++) {int t = a[low]; // 当前要插入的元素int i = low - 1; // 比较指针，从当前元素的前一个位置开始// 将大于 t 的元素向右移动一位while (i >= left && t < a[i]) {a[i + 1] = a[i];i--;}// 如果 i != low - 1，说明 t 需要插入到正确的位置if (i != low - 1) {a[i + 1] = t;}}}/*** 合并两个已排序的子数组** @param a1 原始数组* @param i 左子数组的起始索引* @param iEnd 左子数组的结束索引* @param j 右子数组的起始索引* @param jEnd 右子数组的结束索引* @param a2 辅助数组*/public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {int k = i; // 初始化目标数组的索引 k 为起始位置 i// 当两个子数组都没有处理完时，比较并合并它们while (i <= iEnd && j <= jEnd) {if (a1[i] < a1[j]) {a2[k] = a1[i]; // 将较小的元素放入目标数组 a2i++; // 移动指针 i} else {a2[k] = a1[j]; // 将较小的元素放入目标数组 a2j++; // 移动指针 j}k++; // 移动目标数组的索引 k}// 如果左子数组还有剩余元素，复制到目标数组 a2if (i > iEnd) {System.arraycopy(a1, j, a2, k, jEnd - j + 1);}// 如果右子数组还有剩余元素，复制到目标数组 a2if (j > jEnd) {System.arraycopy(a1, i, a2, k, iEnd - i + 1);}}/*** 算法>排序算法的入口函数** @param a1 待排序的数组*/public static void sort(int[] a1) {int[] a2 = new int[a1.length]; // 初始化辅助数组 a2split(a1, 0, a1.length - 1, a2); // 调用 split 方法进行递归排序}/*** 递归地分割数组并进行排序** @param a1 原始数组* @param left 子数组的起始索引* @param right 子数组的结束索引* @param a2 辅助数组*/private static void split(int[] a1, int left, int right, int[] a2) {// 基本情况：如果子数组只有一个元素，则不需要进一步排序if (right == left) {return;}// 如果子数组长度小于或等于32，使用插入排序if (right - left <= 32) {insertion(a1, left, right);return;}// 分割点 m，将数组分成两部分int m = (left + right) >>> 1;// 递归调用 split 方法对左半部分进行排序split(a1, left, m, a2);// 递归调用 split 方法对右半部分进行排序split(a1, m + 1, right, a2);// 打印调试信息System.out.println(left + " " + right + " " + Arrays.toString(a1));// 合并两个已排序的子数组merge(a1, left, m, m + 1, right, a2);// 将合并后的结果从辅助数组 a2 复制回原数组 a1System.arraycopy(a2, left, a1, left, right - left + 1);}public static void main(String[] args) {int[] array = {5, 2, 4, 6, 1, 3, 9, 8, 7, 0};System.out.println("Before sorting: " + Arrays.toString(array));sort(array);System.out.println("After sorting: " + Arrays.toString(array));}
}快速排序
单边循环
选择最右侧元素作为基准点，j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换，
交换时机：j 找到小的，且与 i 不相等，i 找到 >= 基准点元素后，不应自增，最后基准点与 i 交换，i 即为基准点最终索引
public class QuickSort {/*** 快速排序的入口函数** @param a 待排序的数组*/public static void sort(int[] a) {quick(a, 0, a.length - 1); // 调用 quick 方法进行递归排序}/*** 快速排序的核心逻辑** @param a 待排序的数组* @param left 子数组的起始索引* @param right 子数组的结束索引*/private static void quick(int[] a, int left, int right) {if (left >= right) { // 基本情况：如果子数组长度小于等于1，则不需要进一步排序return;}int p = partition(a, left, right); // 对数组进行分区，并返回基准点元素索引quick(a, left, p - 1); // 递归排序左子数组quick(a, p + 1, right); // 递归排序右子数组}/*** 分区操作，将数组分成两部分，并返回基准点元素的最终位置** @param a 待排序的数组* @param left 子数组的起始索引* @param right 子数组的结束索引* @return 基准点元素的最终位置*/private static int partition(int[] a, int left, int right) {int pv = a[right]; // 基准点元素值，选择数组最后一个元素作为基准点int i = left; // i 指向当前已找到的小于基准点的元素的最后一个位置int j = left; // j 用于遍历数组，寻找小于基准点的元素while (j < right) { // 遍历数组直到 j 到达基准点前一个位置if (a[j] < pv) { // 如果当前元素小于基准点if (i != j) { // 如果 i 和 j 不相等，交换它们指向的元素swap(a, i, j);}i++; // 移动 i 指针}j++; // 移动 j 指针}swap(a, i, right); // 将基准点元素放到正确的位置return i; // 返回基准点元素的最终位置}/*** 交换数组中两个元素的位置** @param a 数组* @param i 第一个元素的索引* @param j 第二个元素的索引*/private static void swap(int[] a, int i, int j) {int t = a[i]; // 临时保存 a[i]a[i] = a[j]; // 将 a[j] 的值赋给 a[i]a[j] = t; // 将临时保存的值赋给 a[j]}public static void main(String[] args) {int[] array = {5, 2, 4, 6, 1, 3, 9, 8, 7, 0};System.out.println("Before sorting: " + java.util.Arrays.toString(array));sort(array);System.out.println("After sorting: " + java.util.Arrays.toString(array));}
}双边循环
选择最左侧元素作为基准点，j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换，
i 从左向右，j 从右向左，最后基准点与 i 交换，i 即为基准点最终索引
public class QuickSort {/*** 快速排序的入口函数** @param a 待排序的数组*/public static void sort(int[] a) {quick(a, 0, a.length - 1); // 调用 quick 方法进行递归排序}/*** 快速排序的核心逻辑** @param a 待排序的数组* @param left 子数组的起始索引* @param right 子数组的结束索引*/private static void quick(int[] a, int left, int right) {if (left >= right) { // 基本情况：如果子数组长度小于等于1，则不需要进一步排序return;}int p = partition(a, left, right); // 对数组进行分区，并返回基准点元素索引quick(a, left, p - 1); // 递归排序左子数组quick(a, p + 1, right); // 递归排序右子数组}/*** 分区操作，将数组分成两部分，并返回基准点元素的最终位置** @param a 待排序的数组* @param left 子数组的起始索引* @param right 子数组的结束索引* @return 基准点元素的最终位置*/private static int partition(int[] a, int left, int right) {int i = left; // 初始化指针 i 指向左边界int j = right; // 初始化指针 j 指向右边界int pv = a[left]; // 基准点元素值，选择数组第一个元素作为基准点while (i < j) { // 当 i 和 j 不相遇时继续循环// 从右向左寻找比基准点小的元素while (i < j && a[j] > pv) {j--; // 如果当前元素大于基准点，继续向左移动 j}// 从左向右寻找比基准点大的元素while (i < j && pv >= a[i]) {i++; // 如果当前元素小于或等于基准点，继续向右移动 i}// 交换找到的两个元素swap(a, i, j);}// 将基准点元素放到正确的位置swap(a, left, j);// 返回基准点元素的最终位置return j;}/*** 交换数组中两个元素的位置** @param a 数组* @param i 第一个元素的索引* @param j 第二个元素的索引*/private static void swap(int[] a, int i, int j) {int t = a[i]; // 临时保存 a[i]a[i] = a[j]; // 将 a[j] 的值赋给 a[i]a[j] = t; // 将临时保存的值赋给 a[j]}public static void main(String[] args) {int[] array = {5, 2, 4, 6, 1, 3, 9, 8, 7, 0};System.out.println("Before sorting: " + java.util.Arrays.toString(array));sort(array);System.out.println("After sorting: " + java.util.Arrays.toString(array));}
}计数排序
public static void sort2(int[] a) {// 初始化最小值和最大值int min = a[0];int max = a[0];// 找到数组中的最小值和最大值for (int i : a) {if (i > max) {max = i;} else if (i < min) {min = i;}}// 创建计数数组，大小为 max - min + 1int[] counting = new int[max - min + 1];// 统计每个元素出现的次数for (int i : a) {counting[i - min]++;}// 计算累积频率，使得 counting[i] 表示小于或等于 i 的所有元素的数量for (int i = 1; i < counting.length; i++) {counting[i] = counting[i] + counting[i - 1];}// 创建输出数组int[] b = new int[a.length];// 根据累积频率构建输出数组for (int i = a.length - 1; i >= 0; i--) {int j = a[i] - min; // 计算当前元素在计数数组中的索引counting[j]--; // 减少当前元素的计数b[counting[j]] = a[i]; // 将当前元素放入输出数组的正确位置}// 将输出数组复制回原数组System.arraycopy(b, 0, a, 0, a.length);
}桶排序
public class BucketSort {/*** 实现桶算法>排序算法** @param a 输入的整数数组* @param range 每个桶覆盖的数值范围*/public static void sort(int[] a, int range) {if (a == null || a.length <= 1) {return; // 如果数组为空或只有一个元素，则无需排序}// 找到数组中的最小值和最大值int max = a[0];int min = a[0];for (int i : a) {if (i > max) {max = i;}if (i < min) {min = i;}}// 计算需要多少个桶// 每个桶覆盖的范围是 `range`DynamicArray[] buckets = new DynamicArray[(max - min) / range + 1];System.out.println("Bucket count: " + buckets.length);// 初始化每个桶for (int i = 0; i < buckets.length; i++) {buckets[i] = new DynamicArray();}// 将输入数组中的每个元素分配到相应的桶中for (int v : a) {DynamicArray bucket = buckets[(v - min) / range];bucket.addLast(v);}int k = 0; // 用于记录排序后数组的下标for (DynamicArray bucket : buckets) {// 对每个桶内的元素进行插入排序int[] array = bucket.array(); // 获取桶中的数据InsertionSort.sort(array);System.out.println(Arrays.toString(array)); // 输出排序后的桶内容// 将排序后的桶内容放回原数组for (int v : array) {a[k++] = v;}}}
}基数排序
public static void radixSort(String[] a, int length) {// 创建128个桶，对应ASCII字符集中的每个可能字符（0-127）ArrayList<String>[] buckets = new ArrayList[128];for (int i = 0; i < buckets.length; i++) {buckets[i] = new ArrayList<>();}// 从最低有效位（最右边的字符）开始处理for (int i = length - 1; i >= 0 ; i--) {// 将每个字符串放入对应的桶中for (String s : a) {// 根据当前字符的ASCII值选择桶buckets[s.charAt(i)].add(s);}// 将所有桶中的字符串重新合并回原数组int k = 0;for (ArrayList<String> bucket : buckets) {for (String s : bucket) {a[k++] = s;}// 清空桶以供下一轮使用bucket.clear();}}
}根据另一个数组次序排序-Leetcode 1122
给你两个数组，
arr1和arr2，arr2中的元素各不相同，arr2中的每个元素都出现在arr1中。对
arr1中的元素进行排序，使arr1中项的相对顺序和arr2中的相对顺序相同。未在arr2中出现过的元素需要按照升序放在arr1的末尾。示例 1：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 输出：[2,2,2,1,4,3,3,9,6,7,19]示例 2:
输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6] 输出：[22,28,8,6,17,44]
public int[] relativeSortArray(int[] arr1, int[] arr2) {int[] count=new int[1001];for(int i:arr1) {count[i]++;}int[] result=new int[arr1.length];int k=0;for(int i:arr2) {while(count[i]>0) {result[k++]=i;count[i]--;}}for (int i = 0; i < count.length; i++) {while(count[i]>0) {result[k++]=i;count[i]--;}}return result;}按出现频率排序-Leetcode 1636
给你一个整数数组
nums，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。请你返回排序后的数组。
示例 1：
输入：nums = [1,1,2,2,2,3] 输出：[3,1,1,2,2,2] 解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。示例 2：
输入：nums = [2,3,1,3,2] 输出：[1,3,3,2,2] 解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。示例 3：
输入：nums = [-1,1,-6,4,5,-6,1,4,1] 输出：[5,-1,4,4,-6,-6,1,1,1]
public int[] frequencySort(int[] nums) {int[] count = new int[201];for (int i : nums) {count[i + 100]++;}return Arrays.stream(nums).boxed().sorted((a, b) -> {int fa = count[a + 100];int fb = count[b + 100];if (fa == fb) {return Integer.compare(b, a);} else {return fa - fb;}}).mapToInt(Integer::intValue).toArray();}最大间距-Leetcode 164
给定一个无序的数组
nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回0。您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。
示例 1:
输入: nums = [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。示例 2:
输入: nums = [10] 输出: 0 解释: 数组元素个数小于 2，因此返回 0。
public int maximumGap(int[] nums) {// 1. 处理特殊情况if (nums.length < 2) {return 0;}// 2. 桶排序int max = nums[0];int min = nums[0];for (int i1 = 1; i1 < nums.length; i1++) {if (nums[i1] > max) {max = nums[i1];}if (nums[i1] < min) {min = nums[i1];}}// 2.1 准备桶/*计算桶个数 期望桶个数(max - min) / range + 1 = nums.length(max - min) / (nums.length - 1) = range*/int range = Math.max((max - min) / (nums.length - 1), 1);DynamicArray[] buckets = new DynamicArray[(max - min) / range + 1];for (int i1 = 0; i1 < buckets.length; i1++) {buckets[i1] = new DynamicArray();}// 2.2 放入数据for (int age : nums) {buckets[(age - min) / range].addLast(age);}int k = 0;for (DynamicArray bucket : buckets) {// 2.3 排序桶内元素int[] array = bucket.array();InsertionSort.sort(array);System.out.println(Arrays.toString(array));// 2.4 把每个桶排序好的内容，依次放入原始数组for (int v : array) {nums[k++] = v;}}// 3. 寻找最大差值int r = 0;for (int i = 1; i < nums.length; i++) {r = Math.max(r, nums[i] - nums[i - 1]);}return r;}
