06.3 插入排序

插入排序详解

1. 引言

插入排序是一种简单而有效的排序算法，其核心思想是逐步构建有序序列。在每一轮遍历中，将未排序部分的元素逐个插入已排序部分的合适位置。

2. 插入排序原理

[!NOTE] 插入排序的基本思路是将一个元素插入已经有序的部分，通过不断地扩大已排序部分的范围，最终完成整个数组的排序。

3. 插入排序步骤

插入排序的具体步骤如下：

[!TIP]

1. 从第二个元素开始，将其与已排序部分的元素逐个比较。
2. 如果当前元素小于已排序元素，将当前元素插入到合适的位置。
3. 重复以上步骤，直至整个数组有序。

4. 插入排序代码

4.1 Python插入排序代码

def insertion_sort(arr):
    n = len(arr)

    for i in range(1, n):
        key = arr[i]
        j = i - 1

        # 将当前元素与已排序部分逐个比较并插入合适位置
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("排序后的数组:", arr)

4.2 Java插入排序代码

package org.example;  
  
import java.util.Arrays;  
  
public class InsertSort {  
    public static void main(String[] args) {  
        int[] arr = {-1, -2, 3, 7, 4, 2};  
        System.out.println("排序前：" + Arrays.toString(arr));  
        insertSort(arr);  
    }  
  
    public static void insertSort(int[] arr) {  
        //逐步分析  
        //第一轮{-1, -2, 3, 7, 4, 2}  ==>  {-2, -1, 3, 7, 4, 2}  
  
        //待插入的数  
//        int insertVal = arr[1];  
//        int insertIndex = 1 - 1; //arr[1]前面的数下标  
//  
//        //给insertValue找到插入的位置  
//        //insertIndex >= 0保证在给insertValue找插入位置 不越界  
//        //insertVal < arr[insertIndex]待插入的数，还没找到插入位置  
//        //就需要将arr[insertIndex]后移  
//        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {  
//            arr[insertIndex + 1] = arr[insertIndex];  
//            insertIndex--;  
//  
//        }  
//        //推出while时，说明插入的位置找到，insertIndex+1  
//        arr[insertIndex + 1] = insertVal;  
//        System.out.printf("第%d轮：",1);  
//        System.out.println(Arrays.toString(arr));  
//  
//        insertVal = arr[2];  
//        insertIndex = 2 - 1; //arr[1]前面的数下标  
//        //给insertValue找到插入的位置  
//        //insertIndex >= 0保证在给insertValue找插入位置 不越界  
//        //insertVal < arr[insertIndex]待插入的数，还没找到插入位置  
//        //就需要将arr[insertIndex]后移  
//        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {  
//            arr[insertIndex + 1] = arr[insertIndex];  
//            insertIndex--;  
//        }  
//        arr[insertIndex + 1] = insertVal;  
//        System.out.printf("第%d轮：",2);  
//        System.out.println(Arrays.toString(arr));  
        for (int i = 1; i < arr.length; i++) {  
            int insertVal = arr[i];  
            int insertIndex = i-1; //arr[1]前面的数下标  
  
            //给insertValue找到插入的位置  
            //insertIndex >= 0保证在给insertValue找插入位置 不越界  
            //insertVal < arr[insertIndex]待插入的数，还没找到插入位置  
            //就需要将arr[insertIndex]后移  
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {  
                arr[insertIndex + 1] = arr[insertIndex];  
                insertIndex--;  
            }  
            //推出while时，说明插入的位置找到，insertIndex+1  
            arr[insertIndex + 1] = insertVal;  
            System.out.printf("第%d轮：", i);  
            System.out.println(Arrays.toString(arr));  
        }  
    }  
}

5. 插入排序的时间复杂度

插入排序的时间复杂度为O(n^2)，其中n为数组的长度。这是因为在最坏情况下，每个元素都需要与已排序部分的所有元素比较。

6. 总结

插入排序是一种简单而稳定的排序算法，特别适用于对已近乎有序的数据进行排序。尽管在大规模数据集上性能较差，但其思想易于理解，是一种良好的排序算法入门选择。在实际应用中，对于小规模数据或者部分有序数据，插入排序仍然是一个可行的选择。