#include<bits/stdc++.h>
using namespace std;
const int maxn=10001;
int a[maxn];
void insertion_sort(int a[],int n){
	for(int i=2;i<=n;i++){
		int key=a[i];
		int j=i-1;
		while(j>=1 && a[j]>key){
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=key;
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	insertion_sort(a,n);
	for(int i=1;i<=n;i++) cout<<a[i]<<" ";
	return 0;
}

题目分析

本题的主要任务是使用插入排序算法对输入的一组整数进行排序。插入排序的基本思想是将一个数据插入到已经排好序的序列中的合适位置，使得插入后该序列仍然有序。具体来说，从第二个元素开始，依次将每个元素插入到前面已经排好序的子数组中。

代码实现

#include<iostream>
int n,a[10086]={0};
int main(){
    // 读取要排序的整数的数量
    scanf("%d",&n);
    // 循环读取 n 个整数并进行插入排序
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        int j,k=a[i];
        // 找到插入位置
        for(j=i - 1;j>=1&&a[j]>k;j--)
            a[j + 1]=a[j];
        // 将当前元素插入到合适的位置
        a[j + 1]=k;
    }
    // 输出排序好的数组
    for(int i=1;i<=n;i++)
        printf("%d ",a[i]);
    return 0;
}

代码解释

1. 变量和数组定义：

   • n：表示要排序的整数的数量。
   • a[10086]：用于存储输入的整数，数组大小为 10086，可处理最多 10085 个整数，初始值都为 0。

2. 输入部分：

   • scanf("%d",&n);：读取要排序的整数的数量。
   • for(int i = 1; i <= n; i++)：循环 n 次，每次读取一个整数并进行插入排序操作。

3. 插入排序部分：

   • int j, k = a[i];：将当前要插入的元素 a[i] 保存到变量 k 中，同时初始化一个变量 j 用于向前查找插入位置。
   • for(j = i - 1; j >= 1 && a[j] > k; j--)：从当前元素的前一个位置开始向前遍历，只要当前位置的元素 a[j] 大于要插入的元素 k，就将 a[j] 向后移动一位，即 a[j + 1] = a[j]。
   • a[j + 1] = k;：当找到合适的插入位置（即 a[j] <= k）时，将 k 插入到 a[j + 1] 的位置。

4. 输出部分：

   • for(int i = 1; i <= n; i++) printf("%d ", a[i]);：循环输出排序好的数组中的元素，元素之间用空格分隔。

复杂度分析

• 时间复杂度：插入排序的平均时间复杂度和最坏时间复杂度均为 $O(n^2)$，其中 $n$ 是数组的长度。在最好情况下（数组已经有序），时间复杂度为 $O(n)$。
• 空间复杂度：只使用了常数级的额外空间，因此空间复杂度为 $O(1)$。

通过上述代码和解释，我们可以使用插入排序算法对给定的一组整数进行升序排序。

记得给五星好评哦喵~ 谢谢客官啦~

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6;

int a[maxn];

void m(int a[],int n){

for(int i=2;i<=n;i++){
	int k=a[i];
	int j=i-1;
	while(j>=1 && a[j]>k){
		a[j+1]=a[j];
		j--;
	}
	a[j+1]=k;
}

}

int main(){

int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
m(a,n);
for(int i=1;i<=n;i++) cout<<a[i]<<" "; 
return 0;

}