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