欢迎讨论

#include<iostream>
#define n 3
using namespace std;
int* InsertSort(int* ar, int N);
int main() {
	int num[n];
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	int * out = InsertSort(num, n);
	for (int i = 0; i < n; i++) {
		cout<<out[i]<<" ";
	}
	return 0;
}
int* InsertSort(int* ar, int m) {//函数定义
	int N = m + 1;
	int* Ar = new int[N];//创建辅助数组
	Ar[0] = 0;//0号位置用作哨兵
	for (int i = 1; i < N; ++i) {//读取输入到辅助数组
		Ar[i] = ar[i - 1];
	}
	//插入排序算法
	for (int i = 2; i < N; i++) {//从第二个元素开始插入
		Ar[0] = Ar[i];//待插入元素设为哨兵
		for (int j = i - 1; j > 0; j--) {//从待插入元素的上一元素开始比较
			if (Ar[j] > Ar[0]) {//前面的元素大于哨兵则向后移动
				Ar[j + 1] = Ar[j];
				if (j == 1) {
					Ar[j] = Ar[0];
				}
			}//小于哨兵则插入该元素位置
			else {
				Ar[j + 1] = Ar[0];
				break;
			}
		}
	}
	return Ar+1;//从哨兵后返回数据
}