考研数据结构与算法笔记之直接插入排序

话不多说，直接上代码，以下是C语言的代码：

void InsertSort(int R[], int n)
{
	int i,j;
	int temp;
	for(int i = 1; i < n; i++)
	{
		temp = R[i];		//将数组分为已排序的序列和未排序的序列，temp取未排列序列的第一个元素；
		j = i - 1;			//下标j为已排列序列的最后一个元素的下标；
		while( j>= 0 && temp < R[j])	//将未排序的第一个元素与前面所有的数据相比较，知道碰到比其小的数据则停止；
		{
			R[i+1] = R[j];		//比未排序第一个数据大的数据依次向后移一位；
			--j;
		}
		R[j+1] = temp;		//将temp赋值给空出来的位置；
	}
	
}
           

举个例子：

12 | 25 23 5 36 35 （“|”为分界线）

先以12为已排序序列，之后都为未排序序列，25为未排序序列的第一个数据；

第一次排序后：

12 25 | 23 5 36 35

第二次排序后：

12 23 25 | 5 36 35

第三次排序后：

5 12 23 25 | 36 35

第四次排序后：

5 12 23 25 36 | 35

第五次排序后：

5 12 23 25 35 36 |

排序完成

本算法的平均时间复杂度为O(n^2)

其中最好情况下整个序列已经有序，时间复杂度为O(n)

最坏的情况下整个序列是逆序的，时间复杂度为O(n^2),基本操作总的执行次数是n(n-1)/2;

空间复杂度为O(1);