[排序算法] 2. 直接插入排序(插入排序)

1. 基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

可以类比平日打扑克的情况：

当插入第 i(i>=1)个元素时，前面的 array[0]、array[1]…、array[i-1] 已经排好序，此时用 array[i] 的排序码与array[i-1]、array[i-2]、… 的排序码顺序进行比较，找到插入位置即将array[i] 插入，原来位置上的元素顺序后移即可。

2. 代码实现

// 直接插入排序（递增）
void InsertSort(int array[], int size) {
	for (int i = 1; i < size; ++i) {	// 遍历array
		int k = array[i];
		int j = i - 1;
		for (j; j >= 0; --j) {		// 与array[i]前面各个元素比较
			if (array[j] <= k) {	// 如果比前一个元素大，说明前半段已经有序，返回
				break;
			}
			array[j + 1] = array[j];	// 将大于array[i]的元素向后移动，注意从后向前赋值
		}

		array[j + 1] = k;	// 在前半段有序处插入array[i]
	}
}

测试数据：int array[] = { 3, 9, 1, 4, 2, 8, 2, 7, 5, 3, 6, 11, 9, 4, 2, 5, 0, 6 };

3. 性能分析

时间复杂度

• 最坏 $O(n^2)$ 已经逆序
• 平均 $O(n^2)$
• 最好 $O(n)$ 已经有序

空间复杂度

• $O(1)$

排序稳定性

• 稳定

最后

以上就是明亮石头为你收集整理的[排序算法] 2. 直接插入排序(插入排序)的全部内容，希望文章能够帮你解决[排序算法] 2. 直接插入排序(插入排序)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。