直接插入排序（直接插入排序）

题目链接：直接插入排序

考查知识：直接插入排序

题意描述：对n个整数进行直接插入排序

相关知识：

直接插入排序

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

• 性能分析

  • 时间复杂度：平均时间复杂度为 O ( n 2 ) O(n^2) O(n2)，元素集合越接近有序，直接插入排序算法的时间效率越高

  • 空间复杂度：需要一个临时变量存储待排序元素，因此空间复杂度为 O ( 1 ) O(1) O(1)

  • 算法稳定性：稳定

具体代码

#include
using namespace std;
const int N=1e3;
int a[N];
void InsertSort(int a[],int n){
	for(int i=1;i<n;i++){//插入排序，进行n-1趟，i指向无序部分首，每次从无序部分中依次取出元素与有序部分中的元素进行比较，将其放入有序部分的正确位置上 
		int t=a[i],j;
		for(j=i-1;a[j]>t&&j>=0;j--){//j初始指向有序部分尾，然后向前遍历，将[有序部分比原无序部分首大的，原无序部分首)元素后移一位  
			a[j+1]=a[j];
		}
		a[j+1]=t;//将其放入正确位置上 
	}
}
void print(int a[],int n){
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
int main(){
	int n; 
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	InsertSort(a,n);
	print(a,n);
	return 0;
}