排序算法插入与希尔

算法排序

算法

发布日期: 2024-09-12

作者: 小乐

文章字数: 721

阅读时长: 3 分

阅读次数:

一、插入排序

1.1 核心思想

将元素逐个插入到已排序序列的合适位置，就像整理扑克牌。

1.2 实现

public void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // 将大于key的元素后移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

1.3 复杂度分析

情况	时间复杂度	说明
最好	( O(n) )	已排序，每次比较1次
最坏	( O(n^2) )	逆序
平均	( O(n^2) )
空间	( O(1) )
稳定性	稳定

1.4 部分有序的优势

插入排序对部分有序数组非常高效：

每个元素距离最终位置不远
实际比较和移动次数远小于 ( O(n^2) )

1.5 二分优化

查找插入位置时使用二分查找：

public void binaryInsertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int left = 0, right = i - 1;
        
        // 二分查找插入位置
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > key) right = mid - 1;
            else left = mid + 1;
        }
        
        // 移动元素
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
}

比较次数降为 ( O(n \log n) )，但移动仍是 ( O(n^2) )。

二、希尔排序

2.1 核心思想

插入排序的改进版。先让相距较远的元素有序，再逐步缩小间隔，最终间隔为1时就是普通插入排序。

2.2 为什么有效

远距离交换让元素快速接近最终位置
最后一步插入排序时，数组已基本有序

2.3 实现

public void shellSort(int[] arr) {
    int n = arr.length;
    
    // 增量序列：n/2, n/4, ..., 1
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子序列进行插入排序
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i;
            
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}

2.4 增量序列

不同增量序列影响复杂度：

增量序列	最坏复杂度
( n/2, n/4, … )	( O(n^2) )
Hibbard: ( 2^k-1 )	( O(n^{3/2}) )
Sedgewick	( O(n^{4/3}) )

2.5 复杂度

情况	时间复杂度
最好	( O(n \log n) ) ~ ( O(n \log^2 n) )
最坏	( O(n^2) ) ~ ( O(n^{4/3}) )
平均	取决于增量序列
空间	( O(1) )
稳定性	不稳定

三、总结

特性	插入排序	希尔排序
最好时间	( O(n) )	( O(n \log n) )
最坏时间	( O(n^2) )	( O(n^2) ) ~ ( O(n^{4/3}) )
空间	( O(1) )	( O(1) )
稳定性	稳定	不稳定
适用	小数据、部分有序	中等数据