常用的排序算法之插入排序（Insertion Sort）
插入排序（Insertion Sort）
原理
插入排序（Insertion Sort）的起源并不明确，但它是计算机科学中最早提出的排序算法之一。它的工作原理类似于我们日常整理扑克牌或书籍时的过程：我们创建一个新的有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
定义
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
扩展应用
插入排序的思想可以扩展到其他更复杂的排序算法中，例如希尔排序（Shell Sort），它实际上是插入排序的一种更高效的改进版本，也称为缩小增量排序。希尔排序通过使用一个增量序列，使得每次排序时，都能将序列中较远的元素提前放到合适的位置，从而为后续的插入操作减少了数据移动量。
优缺点
优点：
- 实现简单直观，易于理解。
- 在数据规模较小或基本有序的情况下，效率较高。
- 是稳定的排序算法，即相等的元素在排序后保持原有的顺序。
缺点：
- 时间复杂度较高，为O(n^2)，在大数据集上性能不佳。
- 在数据规模较大且无序的情况下效率较低。
使用场景
插入排序通常用于数据量较小或基本有序的情况，或者作为教学示例来帮助学生理解排序算法的基本概念。由于其稳定性，它也被用于需要保持元素原始顺序的排序任务。
使用数据一步步举例
假设有一个数组[4, 2, 8, 3, 1]，我们使用插入排序来对其进行升序排序：
- 初始时，认为第一个元素（索引为0）是有序的，因此从第二个元素（索引为1）开始向前扫描：
- [2, 4, 8, 3, 1] // 将4和2交换
- 将索引为1的元素（现在值为2）与前面的有序序列进行比较，如果比前面的元素小，则交换位置：
- [2, 4, 8, 3, 1]（无需交换）
- 将索引为2的元素（现在值为8）与前面的有序序列进行比较，由于8比前面的所有元素都大，因此无需交换：
- [2, 4, 8, 3, 1]
- 将索引为3的元素（现在值为3）与前面的有序序列进行比较，由于3比4小，因此交换位置：
- [2, 3, 8, 4, 1]
- [2, 3, 4, 8, 1] // 将8和4交换
- 将索引为4的元素（现在值为1）与前面的有序序列进行比较，并依次交换位置，直到找到合适的位置：
- [1, 2, 3, 4, 8]
Java示例代码
代码语言：javascript代码运行次数：0运行复制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]。
发布评论