算法笔记--直接插入排序


直接插入排序是插入排序的一种,算法简单,适用于数据量小的情况。


1. 算法思想

          每次从待排序序列中取出一个元素k,插入到已经排好序的序列A[0...i]中合适的位置。插入时k依次由后向前比较,小于k的元素后移。

2. 时间复杂度

          最好情况 O(n):序列正序有序,只需比较n次,不需移动元素

          最坏情况 O(n^2):序列逆序有序,每次插入一个元素均需移动前面的所有元素

3. 空间复杂度 O(1)

          就地排序,辅助空间为常数级

4. 稳定性

          稳定。将k插入到第一个不大于k的元素之后,不改变同值元素的顺序

5. 代码实现(C语言)

void InsertSort(int *A, int n)
{
	int i, j;
	int tmp;

	for (i = 1; i < n; ++i)
	{
		j = i;
		tmp = A[j];

		while (j > 0 && tmp < A[j - 1])
		{
			A[j] = A[j - 1];
			--j;
		}
		
		A[j] = tmp;
	}
}


上一篇:基于ONOS的T-SDN Super控制器,突破多域网络运营的难关


下一篇:安全分析:叫好不叫座