C语言实现-直接插入排序（带图详解）

直接插入排序的实现

一、基本思想

像现实中打扑克牌一样，抓牌就是直接插入排序的很好例子，每抓一张牌插入到合适的位置，最后得到一个有序序列。所以直接插入排序的思想就是把待排序的数字逐个插入到已经排好的有序序列里，最后得到一个新的有序序列。

二、实现思路

①先进行单趟排序：使一个有序区间，插入一个数继续有序，使其依然保持有序。

②再排多趟排序：多趟排序后序列越来越接近有序，最后得到有序序列。

三、图形解释过程

四、代码实现

//直接插入排序
void insertsort(int* a, int n)
{
    //多趟数排序，最后为一个有序序列
	for (int i = 0; i < n - 1; i++)
	{
      //单趟排序 [0,end]有序，把值end+1的值插入后，依然有序	
	    int end=i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}

}

五、直接插入排序性质总结

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定