2025-07-31-排序

本文章默认是从小到大排序

排序的概念

稳定性： 排完序后，位置会不会乱。比如 $%5B8%2C%205_a%2C%205_b%5D$ 这个数组（a,b 仅仅用来标记）
稳定的排完序后是 $%5B5_a%2C%205_b%2C%208%5D$
不稳定的排完序后可能是 $%5B5_b%2C%205_a%2C%208%5D$
内部排序：在内存上的排序，适用于数据比较少的情况
外部排序：在外存（硬盘）上的排序，适用于数据比较多的情况

排序的类型

基于比较排序
1. 插入排序
  1. 直接插入排序
  2. 希尔排序
2. 选择排序
  1. 选择排序
  2. 堆排序
3. 交换排序
  1. 冒泡排序
  2. 快速排序
4. 归并排序
非基于比较排序（了解即可）
1. 计数排序
2. 基数排序
3. 桶排序

排序的实现

直接插入排序

思想：
从第 2 个元素开始，获取到这个元素的值，并用临时变量存储
如果这个元素比前一个元素大，那么就不需要覆盖，直接跳出这个循环
如果比前一个元素小，那么就要前一个元素的内容就要覆盖后一个元素的内容，然后继续判断，直到遍历完或者条件不满足
在 2/3 这两步循环完后，就可以把之前临时存储的元素放入最后一个覆盖元素的原位置上
1/2/3/4 是一次循环，按照这样的步骤，遍历完整个数组后即可完成循环
性质：
时间复杂度： $O(N%20%5E%202)$
空间复杂度： $O(1)$
稳定性：稳定

用例 1/1

步骤： 0 / 0

temp (临时变量)

空

当前动作：等待输入...

Java

public static void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int j = i - 1;
        int tmp = array[i];
        for( ; j >= 0; j--) {
            // 不要写为 >= 不然就是不稳定的
            if (array[j] > tmp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        // j + 1 是最后一个元素的下标
        array[j + 1] = tmp;
    }
}

希尔排序

希尔排序是直接插入排序的优化
思想：
它是分组排序，分为 array.length / gap 组，通过让每组元素的个数变小从而让排序次数变小
内部排序（shell() 执行的过程）的思路与直接插入排序基本相同，只是从相隔 1 之间排序变为相隔 gap
外部排序只需要保证 gap 最后为 1 的时候在执行一次内部排序即可
性质：
时间复杂度： $O(N%20%5E%20%7B1.3%7D)%20%5Csim%20O(N%20%5E%20%7B1.5%7D)$
由于 gap 不确定什么时候最优解，所以目前来说，这个时间复杂度还没有确定的值
空间复杂度： $O(1)$
稳定性：不稳定

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

Java

public static void shellSort(int[] array) {
    int gap = array.length / 2; // gap 变化逻辑可以自己定义，但是最终必须为 1
    while (gap >= 1) {
        shell(array, gap);
        gap /= 2;
    }
}

private static void shell(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int j = i - gap; // 同一个组的前一个元素的下标
        int tmp = array[i];
        for( ; j >= 0; j -= gap) {
            // 希尔排序是不稳定的
            if (array[j] > tmp) {
                array[j + gap] = array[j];
            } else {
                break;
            }
        }
        // j + 1 是最后一个元素的下标
        array[j + gap] = tmp;
    }
}

选择排序

由于时间复杂度/稳定性都没有优势，所以通常不使用这个排序
思想：
先遍历一次数组获取最小值的下标
接着把第一个元素与最小值交换，把第一个元素变为最小值
然后遍历第二个，第三个元素，直到遍历完数组为止
性质：
时间复杂度： $O(N%20%5E%202)$
空间复杂度： $O(1)$
稳定性：不稳定

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

Java

public static void selectSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[minIndex] > array[j]) {
                minIndex = j;
            }
        }
        // minIndex 存储最小值的下标
        swap(array, i, minIndex);
    }
}

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

堆排序

详情见：通过优先级队列这篇文章，里面有堆的 创建+排序
性质：
时间复杂度： $O(N%20%5Ctimes%20%5Clog_2%7BN%7D)$
空间复杂度： $O(1)$
稳定性：不稳定

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

Java

public static void heapSort(int[] array) {
    // 建大根堆 O(N)
    createHeap(array);

    // 排序 O(N * logN)
    int end = array.length - 1;
    while (end > 0) {
        swap(array, 0, end);
        siftDown(array, 0, end);
        end--;
    }
}

private static void createHeap(int[] array) {
    for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
        siftDown(array, parent, array.length);
    }
}

private static void siftDown(int[] array, int parent, int useSize) {
    int child = parent * 2 + 1;
    while (child < useSize) {
        if (child + 1 < useSize && array[child] < array[child + 1]) {
            child++;
        }
        // 此时 child 指向的下标是孩子节点的最大值
        if (array[child] > array[parent]) {
            swap(array, child, parent);
            parent = child;
            child = parent * 2 + 1;
        } else {
            // 剩下的都是大根堆
            break;
        }
    }
}

冒泡排序

思路：
如果第一个数据比第二个数据大，那么就交换
一直执行上诉步骤，直到遍历完一次，此时最后一个元素一定是最大值
接着排除最后一个，反复循环1/2两个步骤，即可排完序
性质：
时间复杂度： $O(N%20%5E%202)$
空间复杂度： $O(1)$
稳定性：稳定

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

Java

public static void bubbleSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        boolean isSwap = false;
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] >= array[j + 1]) {
                swap(array, j, j + 1);
                isSwap = true;
            }
        }
        if (!isSwap) {
            break;
        }
    }
}

快速排序

快速排序类型分为 Hoare法，挖坑法，前后指针法
思路：
找到一个中间值，通过 partition 这个方法后，保证这个中间值的左边比这个值小，右边比这个值大
partition 返回这个中间值的下标 pivot，通过递归，排序完左边与右边的那一部分
parition 由于类型不同，思路也有所不同，所以在具体的内部在解析
partition 是在具体的方法内部实现 完整代码是框架内容+具体类型的partition实现 性质：
时间复杂度：最好： $O(N%20*%20%5Clog_2%7BN%7D)$ ，最坏： $O(N%20*%202)$
空间复杂度：最好： $O(%5Clog_2%7BN%7D)$ ，最坏： $O(N)$
稳定性：不稳定

思考

为什么是先从右边开始，而不是从左边开始？
排序的结果从小到大，从左边开始，最后一次就会获取到较大值，与 tmp 交换，导致较大值换到左边
获取较大值/较小值的下标时候，能不能省略等号？为什么？
比如 left < right && array[right] >= tmp 能不能变为 left < right && array[right] > tmp
不取等号会有死循环这个可能，比如 [5,5,5] 这个数组就有这个问题

Java

// 框架的内容
public static void quickSort(int[] array) {
    quick(array, 0, array.length - 1);
}

private static void quick(int[] array, int start, int end) {
    // start >= end 就结束了
    if (start >= end) {
        return;
    }

    // 排序，然后返回中间值的下标
    int pivot = partition(array, start, end);

    // 遍历左边与右边
    quick(array, start, pivot - 1);
    quick(array, pivot + 1, end);
}

快速排序类型实现

Hoare法

思路：
获取左边第一个元素 tmp 作为基准，并记录下此时的下标 i
先从右开始，获取到比 tmp 小的下标 right
然后从左边开始，获取到比 tmp 大的下标 left
使用 swap() 这个方法交换 right 与 left 所对应的值
直到循环结束，最后使用 swap() 交换 i 与 left 所对应的值 这个下标并返回 left

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

Java

private static int partition(int[] array, int left, int right) {
    int tmp = array[left];
    int i = left; // 用来存储 left

    while (left < right) {
        while (left < right && array[right] >= tmp) {
            right--;
        }

        while (left < right && array[left] <= tmp) {
            left++;
        }

        swap(array, left, right);
    }
    // 与开始的交换
    swap(array, i, left);
    return left;
}

挖坑法

思路：
获取左边第一个元素 tmp 作为基准，用 tmp 存储
先从右开始，获取到比 tmp 小的下标 right，循环结束后，用 right 这个值覆盖掉 left 对应的值
然后从左边开始，获取到比 tmp 大的下标 left，循环结束后，用 left 这个值覆盖掉 right 对应的值
直到循环结束，最后将 tmp 赋值给 left 这个下标并返回 left

用例 1/1

步骤： 0 / 0

temp (基准/被挖出的坑)

空

当前动作：等待输入...

Java

// 挖坑法
private static int partition(int[] array, int left, int right) {
    int tmp = array[left];

    while (left < right) {
        while (left < right && array[right] >= tmp) {
            right--;
        }
        // 右边比较小的覆盖掉左边比较大的
        array[left] = array[right];
        while (left < right && array[left] <= tmp) {
            left++;
        }
        // 左边比较大的覆盖掉右边比较小的
        array[right] = array[left];
    }

    array[left] = tmp;
    return left;
}

前后指针法

这个仅仅只需要了解即可

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

Java

private static int partition(int[] array, int left, int right) {
    int prev = left ;
    int cur = left + 1;
    while (cur <= right) {
        if(array[cur] < array[left] && array[++prev] != array[cur]) {
            swap(array,cur,prev);
        }
        cur++;
    }
    swap(array,prev,left);
    return prev;
}

快速排序优化

背景：
由于快速排序主要的问题在于 在 $N$ 个数据是有序 的情况下，
树的高度会趋于 $N$ （遍历次数），而每次遍历的个数是 $N$ , 导致时间复杂度会区域 $O(N%20%5E%202)$
优化目标：把 树的高度尽可能降低 来实现排序的优化

获取三数的中位数
在递归到小区间，使用插入排序经行优化

Java

// 优化后的快速排序
private static void quick(int[] array, int start, int end) {
    // start >= end 就结束了
    if (start >= end) {
        return;
    }

    // 低于一定的数值后 剩下的数据基本有序，适用于插入排序
    if (end - start <= 15) {
        insertSort(array, start, end);
    }

    // 获取三数中中位数的下标并且交换
    int midIndex = getMidIndex(array, start, end);
    swap(array, start, midIndex);

    // 排序，然后返回中间值的下标
    int pivot = partition(array, start, end);

    // 遍历左边与右边
    quick(array, start, pivot - 1);
    quick(array, pivot + 1, end);
}

非递归快排

用 Stack<Integer> 存储，用两个元素分别表示头和尾，这样就可以知道快排的范围了

Java

public static void quickSortNor(int[] array) {
    int start = 0;
    int end = array.length - 1;

    int pivot = partition2(array, start, end);

    Stack<Integer> stack = new Stack<>();

    if (pivot - start > 1) {
        // 左边有两个及其以上
        stack.push(pivot - 1);
        stack.push(start);
    }

    if (end - pivot > 1) {
        stack.push(end);
        stack.push(pivot + 1);
    }

    while (!stack.isEmpty()) {
        start = stack.pop();
        end = stack.pop();

        pivot = partition2(array, start, end);

        if (pivot - start > 1) {
            // 左边有两个及其以上
            stack.push(pivot - 1);
            stack.push(start);
        }

        if (end - pivot > 1) {
            stack.push(end);
            stack.push(pivot + 1);
        }
    }
}

归并排序

思想：分而治之，分为“归”和“并”这两个过程
一直对半分，直到这个数组只剩下2个元素为止（归）
2个元素可以看为两个有序数组，将两个有序数组合并为一个有序数组，并覆盖掉原数组（并）
反复执行 1/2 这两个步骤，直到全部都遍历完
性质：
时间复杂度： $O(N%20*%20%5Clog_2%7BN%7D)$
空间复杂度： $O(N)$
稳定性：稳定

用例 1/1

步骤： 0 / 0

原数组用于“分割”与对比元素

↓ 归并 ↓

↑ 复制 ↑

临时数组 (Temp)用于存放排序好的子区间元素

当前动作：等待输入...

递归方式实现归并排序

Java

public static void mergeSort(int[] array) {
    mergeSort(array, 0, array.length - 1);
}

private static void merge(int[] array, int left, int mid, int right) {
    int[] tmpArray = new int[right - left + 1];
    int index = 0;

    int s1 = left, e1 = mid, s2 = mid + 1, e2 = right;

    while (s1 <= e1 && s2 <= e2) {
        // 这里使用 <= 是稳定的，没有等号就是不稳定的
        if (array[s1] <= array[s2]) {
            tmpArray[index++] = array[s1++];
        } else {
            tmpArray[index++] = array[s2++];
        }
    }

    while (s1 <= e1) {
        // 第一个数组还有元素
        tmpArray[index++] = array[s1++];
    }

    while (s2 <= e2) {
        // 第二个数组还有元素
        tmpArray[index++] = array[s2++];
    }

    // 用临时数组的数据覆盖掉原数组的数据
    for (int i = 0; i < tmpArray.length; i++) {
        array[i + left] = tmpArray[i];
    }
}


private static void merge(int[] array, int left, int right) {
    int mid = (right + left) / 2;

    merge(array, left, mid, right);
}

非递归方式实现归并排序

Java

public static void mergeSortNor(int[] array) {
    int gap = 1; // 用来表示当前有序数组的长度，从小到大归并
    // 不需要等号
    while (gap < array.length) {
        for (int i = 0; i < array.length; i += gap * 2) {
            int left = i;

            // 防止最后几个，跳过头导致 数组越界
            int mid = left + gap - 1;
            if (mid >= array.length) {
//                    mid = array.length - 1;
                break; // 如果左半部分已经触底，说明右半部分元素为 0，而左半部分是不需要排序的，因为已经是有序的了
            }

            int right = left + gap * 2 - 1;
            if (right >= array.length) {
                right = array.length - 1;
            }

            // 不能少 mid 这个参数
            merge(array, left, mid, right);
        }
        gap *= 2;
    }
}

疑问

为什么 gap < array.length 不需要等号
gap 表示有序数组的长度，等于 length 时候，有序数组的长度与原数组一样，那么就根本不需要排序了
为什么是使用 merge(array, left, mid, right) 而不是使用 merge(array, left, right)
非递归的情况下，right 由于会数组越界，所以在越界的时候会修正一下，此时如果还按照 mid = (right + left) / 2 来计算，那么 mid 就不是两个有序数组的中间了，而是整个数组的中间了

计数排序

适用于数据比较集中的数字集合
思路：
计算最大值 max 与最小值 min，依据 max 与 min 创建计数数组
遍历数组，通过元素值获取到相关值在计数数组的下标，然后在计数数组内加一
最后依据计数数组的下标与内部的计数，把相关信息赋值给原数组即可
性质：
时间复杂度： $O(max(N%2C%20max%20-%20min))$
空间复杂度： $O(max%20-%20min)$
稳定性：稳定

用例 1/1

步骤： 0 / 0

主数组 (Main)待排序数据与最终结果

↓ 1. 统计频率 ↓

↑ 2. 依次重构 ↑

计数数组 (Count Array)索引代表具体数值，内部存储该数值出现的频次

当前动作：等待输入...

Java

public static void countSort(int[] array) {
    // 先获取到最大最小值
    int max = array[0], min = array[0];
    for (int i = 1; i < array.length; i++) {
        if (max < array[i]) {
            max = array[i];
        } else if (min > array[i]) {
            min = array[i];
        }
    }

    int[] countArray = new int[max - min + 1];

    // 计数
    for (int i = 0; i < array.length; i++) {
        int index = array[i] - min;
        countArray[index]++;
    }

    // 赋值
    int index = 0; // array 下标
    for (int i = 0; i < countArray.length; i++) {
        while (countArray[i] != 0) {
            countArray[i]--;
            array[index++] = i + min;
        }
    }
}

基数排序

适用于纯数字的情况
思路：
创建10个队列（从 0 下标开始）
从个位数开始，通过当前位数的数字获取到队列，然后添加进去即可
一轮添加完毕后，从 0 下标的队列开始，依次出来，返回原来数组中
反复循环 1/2 这两个步骤，直到添加所有的位数都遍历过
最后一次出来后，数组就有序了

用例 1/1

步骤： 0 / 0

主数组

↓ 1. 分配 (Distribute) ↓

↑ 2. 收集 (Collect) ↑

0-9 号桶 (Buckets)根据当前位数的数值，将元素按序入桶

当前动作：等待输入...

桶排序

适用于纯数字的情况
思路：
分为若干桶，每桶存储一定范围内的数字
然后每桶内部经行排序
最后利用有序数组合并这个思想，把各桶之间的数据进行合并

用例 1/1

步骤： 0 / 0

主数组待分配的原始数据与合并后的最终结果

↓ 1. 按值域入桶 ↓

↑ 2. 桶内排序并收回 ↑

数据桶 (Buckets)每个桶负责一个固定的数值范围（区间长度为）

当前动作：等待输入...

JavaSE基础语法

Java数据结构

数据结构初阶

MySQL数据库

MySQL数据库基础

JavaEE

JavaEE初阶

JavaEE进阶

测试

LangChain-AI应用开发框架精品课

优选算法

抽奖系统

2025-07-31-排序 ​

排序的概念 ​

排序的类型 ​

排序的实现 ​

直接插入排序 ​

希尔排序 ​

选择排序 ​

堆排序 ​

冒泡排序 ​

快速排序 ​

思考 ​

快速排序类型实现 ​

Hoare法 ​

挖坑法 ​

前后指针法 ​

快速排序优化 ​

非递归快排 ​

归并排序 ​

递归方式实现归并排序 ​

非递归方式实现归并排序 ​

疑问 ​

计数排序 ​

基数排序 ​

桶排序 ​

2025-07-31-排序

排序的概念

排序的类型

排序的实现

直接插入排序

希尔排序

选择排序

堆排序

冒泡排序

快速排序

思考

快速排序类型实现

Hoare法

挖坑法

前后指针法

快速排序优化

非递归快排

归并排序

递归方式实现归并排序

非递归方式实现归并排序

疑问

计数排序

基数排序

桶排序