直接插入排序

概念

算法思想

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

代码实现

核心算法：

“向一个有序的序列，插入一个数”（单趟的排序）

算法图解：

用代码实现上图的步骤实现：

// 交换数值函数
void swap(int* x1,int* x2)
{
	int tmp=*x1;
	*x1=*x2;
	*x2=tmp;
}

// int类型的指针a，接收外界int类型的数组
void InsertSort(int* a, int n)
{	
	// 假设end就是已经排好序的序列的最后一个数的下标
	int end = n-2;	// 下标n-1是即将要插入的数，而n-2之前的数已经是排好序的序列
	int tmp = a[end+1];		// end+1 就是即将要插入的数，存到临时变量tmp中,
							// tmp将始终存储着要插入的数值
	
	while(end>=0)
	{
		// 升序
		if(tmp<a[end])		// 如果tmp比a[end]小,则tmp要排到前面,前面较大的数往后挪
		{
			swap(&a[end],&a[end+1]);// 将大的往后挪
			end--;  // end下标移到前一位进行比较
		}
		else		// 如果tmp比a[end]大,则tmp排在该数的后面,跳出循环,实现插入
		{
			break;	// 跳出循环
		}
	}
	a[end+1] = tmp;		// 将要插入的数tmp存到到end的下一位
	
}

int main()
{
	int arr[6]={1,2,4,6,9,5};
	InsertSort(arr,sizeof(arr)/sizeof(int));
	
	return 0;
}

直接插入排序的算法实现：

思路：
依次挨个的插入数据，每次的插入都是一趟核心算法
第一次插入时，没有升序/降序一说，但是依旧满足核心算法逻辑

第二次插入时，数组中只有1个数，即可以认为是升序，也可以认为是降序。因此符合向一个有序的序列插入一个数，即核心算法

第三次插入时，数组中只有2个数，但是是经过核心算法插入的结果，所以这2个数依旧是一个有序的序列，所以插入第三个数时，依旧是核心算法。
…

第n次插入时， 数组中有n-1个数，但是都是经过核心算法插入的结果，所以这n-1个数依旧保持着一个有序的排序，所以插入最后一个数时，依旧满足核心算法思想。

// 交换数值函数
void swap(int* x1,int* x2)
{
	int tmp=*x1;
	*x1=*x2;
	*x2=tmp;
}


void InsertSort(int* a, int n)
{
	assert(a);

	// 最后一个 n-1(下标) 插入到 前n-2个排好序列的数 
	// i是有序序列的下标，当i=n-1，即数组最后一个数的下标时，则整个数组就是有序的序列了
	for (int i = 0; i < n - 1; i++)
	{
		// 单趟排序，设定end为已排序部分的最后一个元素下标
		int end = i;	// 有序序列的最后一个下标是i
		int tmp = a[end + 1];  // a[end+1] 是即将要插入的数据

		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;	
	}
	// 出了for循环，利用直接插入算法实现对数组的升序/降序的效果

}

特性总结

1、元素集合越接近有序，直接插入排序算法的时间效率越高
2、时间复杂度：O(N^2）

/*
（考虑最坏的情况）
插入第1个元素，挪动 0 次
插入第2个元素，挪动 1 次
插入第3个元素，挪动 2 次
...
插入第n个元素，挪动 (n-1) 次

我们发现挪动次数是一个，首项为0，公差为1的等差数列。
时间复杂度就是该等差数列的前n项和。根据公式 Sn = n*(a1 + an)/2 = na1 + n*(n-1)*d/2;
得Sn = n^2/2 - n/2;
所以时间复杂度为O(N^2)
*/

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