本文共 1856 字，大约阅读时间需要 6 分钟。

排序

1. 直接插入排序

直接插入排序是一种经典的稳定排序算法，适合大部分有序的数据集。插入排序的基本思想是将每个元素插入一个有序的子序列中，从而将整个数组排序。

时间复杂度

• 最坏情况（数据无序）：O(n²)
• 最好情况（数据有序）：O(n)
• 空间复杂度：O(1)

稳定性

直接插入排序是稳定排序算法，因为处理相等的元素时不会改变它们的相对顺序。

代码实现

public class DirectInsertSort {
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i - 1;
            while (j >= 0) {
                if (temp < array[j]) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
                j--;
            }
            array[j + 1] = temp;
        }
    }
    public static void main(String[] args) {
        int[] array = {10, 3, 2, 7, 19, 78, 65, 127};
        System.out.println(Arrays.toString(array));
        insertSort(array);
        System.out.println(Arrays.toString(array));
    }
}

2. 希尔排序（分组插排）

希尔排序是直接插入排序的优化版本，将数组分成若干个子序列进行插入，每个子序列的长度由一个增量序列决定。

优化条件

• 增量序列中的值没有其他公因子。
• 最后一个增量值必须是1。

时间复杂度

• 最坏情况：O(n²)
• 空间复杂度：O(1)

稳定性

希尔排序是不稳定排序算法，在处理相同的元素时可能会改变它们的相对顺序。

代码实现

public class XiErSort {
    public static void shell(int[] array, int gap) {
        for (int i = 0; i < array.length; i++) {
            int temp = array[i];
            int j = i - gap;
            while (j >= 0) {
                if (array[j] > temp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
                j--;
            }
            array[j + gap] = temp;
        }
    }
    public static void shellSort(int[] array) {
        int[] drr = {5, 3, 1};
        for (int i = 0; i < drr.length; i++) {
            shell(array, drr[i]);
        }
    }
    public static void main(String[] args) {
        int[] array = {10, 7, 5, 6, 90, 32};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }
}