直接插入排序

直接插入排序

概述：

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本 *** 作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

思路：

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。（此处没设置哨兵）

时间复杂度为：O(n²)

代码：

//直接插入排序 
#include  
using namespace std;
void Print(int array[],int length){	//自定义输出函数，每执行一次打印一次序列 
	for(int i=0;itemp;j--){//a[j]小于 temp 时循环结束，结束后应将 temp 赋值给a[j+1]
			array[j+1]=array[j];	//将 a[j] 后移一位 
			}
		array[j+1]=temp;			//将 temp 赋值给a[j+1]
		Print(array,length);
	}
}
int main(){
	int array[]={49,38,65,97,76,13,27,49};
	int length=sizeof(array)/sizeof(*array);
	Print(array,length);			//先打印原始序列 
	InsertSort(array,length);
	return 0;
}

运行结果：