目录
前置准备
定义一个只有 sort 方法的接口
public interface SortExecutor {
/**
* 排序数组
*
* @param nums 待排序的数组
*/
void sort(int[] nums);
/**
* 校验数组是否需要排序
*
* @param nums 待校验的数组
*/
default boolean checkNumsEmpty(int[] nums) {
return nums == null || nums.length == 0;
}
}定义一个 DataHelper 用于生成随机数据和数据处理
public class DataHelper {
/**
* 生成固定大小、固定范围的随机整数数组
*
* @param generateCount 需要生成的数量
* @return 随机整数数组
*/
public static int[] generateRandomNumsByCount(int generateCount) {
int[] randomNums = new int[generateCount];
Random random = new Random();
for (int i = 0; i < generateCount; i++) {
// [0, generateCount]
randomNums[i] = random.nextInt(generateCount + 1);
}
return randomNums;
}
/**
* 交换数组中的两个索引位置的元素
*
* @param arr 数组
* @param src 来源位置
* @param dest 目的位置
*/
public static void swapTwoElementInArray(int[] arr, int src, int dest) {
int temp = arr[src];
arr[src] = arr[dest];
arr[dest] = temp;
}
}排序算法
冒泡排序版本 I
public class BubbleSortV1Executor implements SortExecutor {
/**
* 冒泡排序版本 I
* 思路：将数组中相邻元素从前往后依次进行比较，如果前一个元素比后一个元素大则交换，每一轮循环最大元素就在数组末尾。
* 时间复杂度：O(N²) 内外两层循环，N 是 nums 的长度
* 空间复杂度：O(1)
*
* @param nums 待排序的数组
*/
@Override
public void sort(int[] nums) {
if (checkNumsEmpty(nums)) {
return;
}
int numsLen = nums.length;
for (int i = 0; i < numsLen - 1; i++) {
for (int j = 0; j < numsLen - 1; j++) {
if (nums[j + 1] >= nums[j]) {
continue;
}
DataHelper.swapTwoElementInArray(nums, j, j + 1);
}
}
}
}冒泡排序版本 II
public class BubbleSortV2Executor implements SortExecutor {
/**
* 冒泡排序版本 II
* 优化点：添加一个标识用来确定内层排序是否存在交换元素的动作，没有则说明数组已经有序。
* 时间复杂度：最差为O(N²)，取决于随机数组的数据分布特点。
* 空间复杂度：O(1)
*
* @param nums 待排序的数组
*/
@Override
public void sort(int[] nums) {
if (checkNumsEmpty(nums)) {
return;
}
int numsLen = nums.length;
for (int i = 0; i < numsLen - 1; i++) {
boolean isExistSwap = false;
// 减去 i 是因为之前的循环已经排过序了
for (int j = 0; j < numsLen - 1 - i; j++) {
if (nums[j + 1] >= nums[j]) {
continue;
}
isExistSwap = true;
DataHelper.swapTwoElementInArray(nums, j, j + 1);
}
if (!isExistSwap) {
return;
}
}
}
}选择排序版本 I
public class SelectSortV1Executor implements SortExecutor {
/**
* 选择排序版本 I
* 思路：将数组分为前边已排序和后边未排序的两部分，在未排序序列中找到最小元素，存放到排序序列的末尾。
* 时间复杂度：O(N²) 内外两层循环，N 是 nums 的长度。
* 空间复杂度：O(1)
*
* @param nums 待排序的数组
*/
@Override
public void sort(int[] nums) {
if (checkNumsEmpty(nums)) {
return;
}
int numsLen = nums.length;
for (int i = 0; i < numsLen - 1; i++) {
int minNumIndex = i;
for (int j = i + 1; j < numsLen; j++) {
if (nums[j] >= nums[minNumIndex]) {
continue;
}
minNumIndex = j;
}
DataHelper.swapTwoElementInArray(nums, i, minNumIndex);
}
}
}选择排序版本 II
public class SelectSortV2Executor implements SortExecutor {
/**
* 选择排序版本 II
* 优化点：每一轮同时找出最小值和最大值，分别放在队首和队尾，理论上循环次数可减半。
* 时间复杂度：O(N²)，最坏情况为 N/2 次循环。
* 空间复杂度：O(1)
*
* @param nums 待排序的数组
*/
@Override
public void sort(int[] nums) {
if (checkNumsEmpty(nums)) {
return;
}
int numsLen = nums.length;
int leftIndex = 0;
int rightIndex = numsLen - 1;
while (leftIndex < rightIndex) {
int minNumIndex = leftIndex;
int maxNumIndex = rightIndex;
for (int i = leftIndex; i <= rightIndex; i++) {
if (nums[i] < nums[minNumIndex]) {
minNumIndex = i;
}
if (nums[i] > nums[maxNumIndex]) {
maxNumIndex = i;
}
}
DataHelper.swapTwoElementInArray(nums, maxNumIndex, rightIndex);
// 需要考虑 minNumIndex == maxNumIndex 的情况
if (minNumIndex == rightIndex) {
minNumIndex = maxNumIndex;
}
DataHelper.swapTwoElementInArray(nums, minNumIndex, leftIndex);
leftIndex++;
rightIndex--;
}
}
}插入排序版本 I
public class InsertSortV1Executor implements SortExecutor {
/**
* 插入排序版本 I
* 思路：将数组分为前边已排序和后边未排序的两部分，依次将未排序部分的元素插入到排序序列的指定位置。
* 时间复杂度：O(N²) 内外两层循环，N 是 nums 的长度。
* 空间复杂度：O(1)
*
* @param nums 待排序的数组
*/
@Override
public void sort(int[] nums) {
if (checkNumsEmpty(nums)) {
return;
}
int numsLen = nums.length;
for (int i = 1; i < numsLen; i++) {
// 未排序部分的元素在排序部分 从右往左 找到属于自己的位置
for (int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--) {
DataHelper.swapTwoElementInArray(nums, j, j + 1);
}
}
}
}插入排序版本 II
public class InsertSortV2Executor implements SortExecutor {
/**
* 插入排序版本 II
* 优化点：将比较过程改为二分法
* 时间复杂度：O(N * log N) 外层循环 * 内层二分查找，N 是 nums 的长度。
* 空间复杂度：O(1)
*
* @param nums 待排序的数组
*/
@Override
public void sort(int[] nums) {
if (checkNumsEmpty(nums)) {
return;
}
int numsLen = nums.length;
for (int i = 1; i < numsLen; i++) {
int leftIndex = 0;
int rightIndex = i - 1;
int curNum = nums[i];
while (leftIndex <= rightIndex) {
int midIndex = leftIndex + (rightIndex - leftIndex) / 2;
if (nums[midIndex] > curNum) {
rightIndex = midIndex - 1;
} else {
leftIndex = midIndex + 1;
}
}
// 需要将所有元素往右移一位
int j;
for (j = i - 1; j >= rightIndex + 1; j--) {
nums[j + 1] = nums[j];
}
nums[j + 1] = curNum;
}
}
}希尔排序版本 I
public class ShellSortV1Executor implements SortExecutor {
/**
* 希尔排序版本 I
* 思路：类似于插入排序，在此基础上设置 increment 间隔作为逻辑分组
* 时间复杂度：O(N * log N) ~ O(N²) 取决于 increment 的选取
* 空间复杂度：O(1)
*
* @param nums 待排序的数组
*/
@Override
public void sort(int[] nums) {
if (checkNumsEmpty(nums)) {
return;
}
int numsLen = nums.length;
int increment = numsLen;
while (increment > 1) {
// 自定义
increment = increment / 3 + 1;
// 对每个按增量划分后的逻辑分组，进行插入排序
for (int i = increment; i < numsLen; i++) {
if (nums[i - increment] > nums[i]) {
int curNum = nums[i];
int j = i - increment;
while (j >= 0 && nums[j] > curNum) {
nums[j + increment] = nums[j];
j -= increment;
}
nums[j + increment] = curNum;
}
}
}
}
}快速排序版本 I
public class QuickSortV1Executor implements SortExecutor {
/**
* 快速排序版本 I
* 思路：每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两部分，递归执行该过程，直到所有元素都完成排序。
* 时间复杂度：O(N * log N) N 为数组的长度
* 空间复杂度：O(N * log N) 递归调用所消耗的栈空间
*
* @param nums 待排序的数组
*/
@Override
public void sort(int[] nums) {
if (checkNumsEmpty(nums)) {
return;
}
int leftBoundary = 0;
int rightBoundary = nums.length - 1;
quickSort(nums, leftBoundary, rightBoundary);
}
private void quickSort(int[] nums, int leftBoundary, int rightBoundary) {
if (leftBoundary > rightBoundary) {
return;
}
int leftIndex = leftBoundary;
int rightIndex = rightBoundary;
// 选取一个基准值 pivot，小于 pivot 的元素在左边，大于 pivot 的元素在右边。
int pivot = nums[leftIndex];
while (leftIndex < rightIndex) {
// 从右往左找一个小于 pivot 的数
while (pivot <= nums[rightIndex] && leftIndex < rightIndex) {
rightIndex--;
}
// 从左往右找一个大于 pivot 的数
while (pivot >= nums[leftIndex] && leftIndex < rightIndex) {
leftIndex++;
}
if (leftIndex < rightIndex) {
DataHelper.swapTwoElementInArray(nums, leftIndex, rightIndex);
}
}
// 中间这个数放左边
nums[leftBoundary] = nums[leftIndex];
// pivot 放中间
nums[leftIndex] = pivot;
// 递归中间数的左右部分
quickSort(nums, leftBoundary, leftIndex - 1);
quickSort(nums, rightIndex + 1, rightBoundary);
}
}归并排序版本 I
public class MergeSortV1Executor implements SortExecutor {
/**
* 归并排序版本 I
* 思路：分而治之，拆分成最小排序单元后进行组合
* 时间复杂度：O(N * log N) N 为数组的长度
* 空间复杂度：O(N) tempNums 所占用的空间
*
* @param nums 待排序的数组
*/
@Override
public void sort(int[] nums) {
if (checkNumsEmpty(nums)) {
return;
}
int numsLen = nums.length;
int[] tempNums = new int[numsLen];
mergeSort(nums, 0, numsLen - 1, tempNums);
}
private void mergeSort(int[] nums, int leftBoundary, int rightBoundary, int[] tempNums) {
if (leftBoundary == rightBoundary) {
return;
}
int midIndex = leftBoundary + (rightBoundary - leftBoundary) / 2;
mergeSort(nums, leftBoundary, midIndex, tempNums);
mergeSort(nums, midIndex + 1, rightBoundary, tempNums);
// 如果合并完 mid 小于右边则说明当次合并已经有序
if (nums[midIndex] <= nums[midIndex + 1]) {
return;
}
for (int i = leftBoundary; i <= rightBoundary; i++) {
tempNums[i] = nums[i];
}
// 对 tempNums 进行分区 [leftBoundary, midIndex] [midIndex + 1, rightBoundary]
int leftIndex = leftBoundary;
int rightIndex = midIndex + 1;
// 分区比较
for (int i = leftBoundary; i <= rightBoundary; i++) {
if (leftIndex == midIndex + 1) {
nums[i] = tempNums[rightIndex++];
} else if (rightIndex == rightBoundary + 1) {
nums[i] = tempNums[leftIndex++];
} else if (tempNums[leftIndex] >= tempNums[rightIndex]) {
nums[i] = tempNums[rightIndex++];
} else if (tempNums[leftIndex] < tempNums[rightIndex]) {
nums[i] = tempNums[leftIndex++];
}
}
}
}堆排序版本 I
public class HeapSortV1Executor implements SortExecutor {
/**
* 堆排序版本 I
* 思路：利用大顶堆性质，每一轮将大顶堆的第一个元素放到未排序数组尾部
* 时间复杂度：O(N * log N) N 为数组的长度
* 空间复杂度：O(1)
*
* @param nums 待排序的数组
*/
@Override
public void sort(int[] nums) {
if (checkNumsEmpty(nums)) {
return;
}
int numsLen = nums.length;
// 从最后一颗子树开始往前建大顶堆
for (int i = numsLen / 2 - 1; i >= 0; i--) {
heapSort(nums, numsLen, i);
}
// 排序
for (int i = numsLen - 1; i > 0; i--) {
DataHelper.swapTwoElementInArray(nums, i, 0);
heapSort(nums, i, 0);
}
}
private void heapSort(int[] nums, int numsLen, int index) {
// 记录最大值的索引
int maxNumIndex = index;
int leftIndex = index * 2 + 1;
int rightIndex = index * 2 + 2;
// 维护大顶堆
if (leftIndex < numsLen && nums[maxNumIndex] < nums[leftIndex]) {
maxNumIndex = leftIndex;
}
if (rightIndex < numsLen && nums[maxNumIndex] < nums[rightIndex]) {
maxNumIndex = rightIndex;
}
if (maxNumIndex != index) {
DataHelper.swapTwoElementInArray(nums, index, maxNumIndex);
heapSort(nums, numsLen, maxNumIndex);
}
}
}JDK Arrays.sort()
public class JDKSortExecutor implements SortExecutor {
/**
* JDK Arrays 工具类的内置排序
*
* @param nums 待排序的数组
*/
@Override
public void sort(int[] nums) {
if (checkNumsEmpty(nums)) {
return;
}
Arrays.sort(nums);
}
}效率对比
定义执行器枚举类并在 SortExecutorManager 中完成所有 SortExecutor 实现类的注册
SortExecutorEnum
public enum SortExecutorEnum {
BUBBLE_SORT_V1("Bubble Sort Version I", new BubbleSortV1Executor()),
BUBBLE_SORT_V2("Bubble Sort Version II", new BubbleSortV2Executor()),
SELECT_SORT_V1("Select Sort Version I", new SelectSortV1Executor()),
SELECT_SORT_V2("Select Sort Version II", new SelectSortV2Executor()),
INSERT_SORT_V1("Insert Sort Version I", new InsertSortV1Executor()),
INSERT_SORT_V2("Insert Sort Version II", new InsertSortV2Executor()),
SHELL_SORT_V1("Shell Sort Version I", new ShellSortV1Executor()),
QUICK_SORT_V1("Quick Sort Version I", new QuickSortV1Executor()),
MERGE_SORT_V1("Merge Sort Version I", new MergeSortV1Executor()),
HEAP_SORT_V1("Heap Sort Version I", new HeapSortV1Executor()),
JDK_SORT("JDK Sort", new JDKSortExecutor());
private final String executorName;
private final SortExecutor executor;
SortExecutorEnum(String executorName, SortExecutor executor) {
this.executorName = executorName;
this.executor = executor;
}
public String getExecutorName() {
return this.executorName;
}
public SortExecutor getExecutor() {
return this.executor;
}
}SortExecutorManager
public class SortExecutorManager {
private static final Map<String, SortExecutor> SORT_EXECUTOR_MANAGER;
static {
// 初始化并注册所有排序执行器，使用 LinkedHashMap 保证注册顺序
SORT_EXECUTOR_MANAGER = new LinkedHashMap<>();
registerSortExecutors();
}
private static void registerSortExecutors() {
// 使用枚举类手动注册，Spring 工程可以使用依赖注入
SortExecutorEnum[] executorEnums = SortExecutorEnum.values();
for (SortExecutorEnum executorEnum : executorEnums) {
SORT_EXECUTOR_MANAGER.put(executorEnum.getExecutorName(), executorEnum.getExecutor());
}
}
public static Map<String, SortExecutor> getSortExecutorManager() {
return SORT_EXECUTOR_MANAGER;
}
}SortApplication
public class SortApplication {
public static void main(String[] args) {
Map<String, SortExecutor> sortExecutorManager = SortExecutorManager.getSortExecutorManager();
int[] randomNums = DataHelper.generateRandomNumsByCount(NUMBER_100_000);
Set<String> allSortExecutorNames = sortExecutorManager.keySet();
for (String executorName : allSortExecutorNames) {
long startTimestamp = System.currentTimeMillis();
int[] copyRandomNums = Arrays.copyOf(randomNums, randomNums.length);
sortExecutorManager.get(executorName).sort(copyRandomNums);
// System.out.println(Arrays.toString(copyRandomNums));
long endTimestamp = System.currentTimeMillis();
computeAndPrintDuration(executorName, startTimestamp, endTimestamp);
}
}
private static void computeAndPrintDuration(String executorName, long startTimestamp, long endTimestamp) {
System.out.println(executorName + " ==> " + (endTimestamp - startTimestamp) + " ms");
}
}测试机：MacBook Pro 2023 款
运行结果：
Bubble Sort Version I ==> 14636 ms
Bubble Sort Version II ==> 11860 ms
Select Sort Version I ==> 4471 ms
Select Sort Version II ==> 2363 ms
Insert Sort Version I ==> 3342 ms
Insert Sort Version II ==> 1507 ms
Shell Sort Version I ==> 11 ms
Quick Sort Version I ==> 26 ms
Merge Sort Version I ==> 21 ms
Heap Sort Version I ==> 10 ms
JDK Sort ==> 22 ms
本文含有隐藏内容，请 开通VIP 后查看