我的学习笔记

外观

2025-07-31-排序 ​

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

排序的概念 ​

  • 稳定性： 排完序后，位置会不会乱。比如 [8,5a,5b] 这个数组（a,b 仅仅用来标记）

    稳定的排完序后是 [5a,5b,8]

    不稳定的排完序后可能是 [5b,5a,8]

  • 内部排序：在内存上的排序，适用于数据比较少的情况

  • 外部排序：在外存（硬盘）上的排序，适用于数据比较多的情况

排序的类型 ​

  1. 插入排序
    1. 直接插入排序
    2. 希尔排序
  2. 选择排序
    1. 选择排序
    2. 堆排序
  3. 交换排序
    1. 冒泡排序
    2. 快速排序
  4. 归并排序

排序的实现 ​

直接插入排序 ​

思想：

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

性质：

  • 时间复杂度：O(N2)
  • 空间复杂度：O(1)
  • 稳定性：稳定
步骤： 0 / 0

当前动作：加载中...

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;
    }
}

希尔排序 ​

希尔排序是直接插入排序的优化

思想：

  1. 它是分组排序，分为 array.length / gap 组，通过让每组元素的个数变小从而让排序次数变小
  2. 内部排序（shell() 执行的过程）的思路与直接插入排序基本相同，只是从相隔 1 之间排序变为相隔 gap
  3. 外部排序只需要保证 gap 最后为 1 的时候在执行一次内部排序即可

性质：

  • 时间复杂度：O(N1.3)∼O(N1.5)

    由于 gap 不确定什么时候最优解，所以目前来说，这个时间复杂度还没有确定的值

  • 空间复杂度：O(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;
    }
}

选择排序 ​

由于时间复杂度/稳定性都没有优势，所以通常不使用这个排序

思想：

  1. 先遍历一次数组获取最小值的下标
  2. 接着把第一个元素与最小值交换，把第一个元素变为最小值
  3. 然后遍历第二个，第三个元素，直到遍历完数组为止

性质：

  • 时间复杂度：O(N2)
  • 空间复杂度：O(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×log2⁡N)
  • 空间复杂度：O(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;
        }
    }
}