常用的排序算法之插入排序（Insertion Sort）

插入排序（Insertion Sort）

原理

插入排序（Insertion Sort）的起源并不明确，但它是计算机科学中最早提出的排序算法之一。它的工作原理类似于我们日常整理扑克牌或书籍时的过程：我们创建一个新的有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

定义

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

扩展应用

插入排序的思想可以扩展到其他更复杂的排序算法中，例如希尔排序（Shell Sort），它实际上是插入排序的一种更高效的改进版本，也称为缩小增量排序。希尔排序通过使用一个增量序列，使得每次排序时，都能将序列中较远的元素提前放到合适的位置，从而为后续的插入操作减少了数据移动量。

优缺点

优点：

• 实现简单直观，易于理解。
• 在数据规模较小或基本有序的情况下，效率较高。
• 是稳定的排序算法，即相等的元素在排序后保持原有的顺序。

缺点：

• 时间复杂度较高，为O(n^2)，在大数据集上性能不佳。
• 在数据规模较大且无序的情况下效率较低。

使用场景

插入排序通常用于数据量较小或基本有序的情况，或者作为教学示例来帮助学生理解排序算法的基本概念。由于其稳定性，它也被用于需要保持元素原始顺序的排序任务。

使用数据一步步举例

假设有一个数组[4, 2, 8, 3, 1]，我们使用插入排序来对其进行升序排序：

1. 初始时，认为第一个元素（索引为0）是有序的，因此从第二个元素（索引为1）开始向前扫描：
   • [2, 4, 8, 3, 1] // 将4和2交换
2. 将索引为1的元素（现在值为2）与前面的有序序列进行比较，如果比前面的元素小，则交换位置：
   • [2, 4, 8, 3, 1]（无需交换）
3. 将索引为2的元素（现在值为8）与前面的有序序列进行比较，由于8比前面的所有元素都大，因此无需交换：
   • [2, 4, 8, 3, 1]
4. 将索引为3的元素（现在值为3）与前面的有序序列进行比较，由于3比4小，因此交换位置：
   • [2, 3, 8, 4, 1]
   • [2, 3, 4, 8, 1] // 将8和4交换
5. 将索引为4的元素（现在值为1）与前面的有序序列进行比较，并依次交换位置，直到找到合适的位置：
   • [1, 2, 3, 4, 8]

Java示例代码

public class InsertionSort {  
    public static void main(String[] args) {  
        int[] array = {4, 2, 8, 3, 1};  
        insertionSort(array);  
        System.out.println(Arrays.toString(array));  
    }  
  
    public static void insertionSort(int[] array) {  
        int n = array.length;  
        for (int i = 1; i < n; i++) {  
            int key = array[i];  
            int j = i - 1;  
  
            // Move elements of array[0..i-1], that are greater than key,  
            // to one position ahead of their current position  
            while (j >= 0 && array[j] > key) {  
                array[j + 1] = array[j];  
                j = j - 1;  
            }  
            array[j + 1] = key;  
        }  
    }  
}

运行上述代码，将输出排序后的数组[1, 2, 3, 4, 8]。