【唐叔学算法】第17天：排序算法之插入排序

插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 $O(1)$ 的额外空间的排序）。

1. 直接插入排序 (Straight Insertion Sort)

算法原理

直接插入排序是插入排序的一种，它逐个检查要排序的元素，从数组的起始位置开始，将每个元素插入到前面已经排好序的子数组中的适当位置。

• 时间复杂度
  最坏情况：$O(n^2)$，当要排序的数组是逆序时。
  平均情况：$O(n^2)$。
  最好情况：$O(n)$，当输入数组已经是正序时。

• 空间复杂度：$O(1)$，因为排序是原地进行的。

Java代码实现

public void straightInsertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

2. 折半插入排序 (Binary Insertion Sort)

算法原理

折半插入排序是对直接插入排序的一种改进，它使用二分查找确定元素的插入位置，减少了比较元素的次数。

• 时间复杂度
  最坏情况：$O(n^2)$，与直接插入排序相同。
  平均情况：接近 $O(nlogn)$，因为二分查找将比较次数降低到 $O(logn)$。
  最好情况：$O(n)$，当输入数组已经是正序时。

• 空间复杂度：$O(1)$，同样是原地排序。

Java代码实现

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) left = mid + 1;
            else right = mid - 1;
        }
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
}

3. 希尔排序 (Shell Sort)

算法原理

希尔排序是插入排序的一种更高效的改进版本。它通过比较距离一定间隔的元素来工作，然后逐步减小间隔来排序元素。

• 时间复杂度
  希尔排序的时间复杂度很难精确分析，它依赖于间隔序列的选择。在最佳和平均情况下，时间复杂度可以低至 $O(nlogn)$，但最坏情况仍然是 $O(n^2)$。

• 空间复杂度：$O(1)$，希尔排序也是原地排序。

Java代码实现

public void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

总结

这三种插入排序算法各有特点，直接插入排序简单易懂，折半插入排序在找到插入位置时效率更高，而希尔排序通过引入间隔的概念，可以更快地对数组进行初步排序。在实际应用中，可以根据数据的特点和需求选择合适的排序算法。