当前位置：首页 > article >正文

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

article 2024/12/24 13:47:50

插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用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(n log n)，因为二分查找将比较次数降低到O(log n)。
最好情况：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(n log n)，但最坏情况仍然是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;
        }
    }
}