排序技术：插入排序（C++实现）

#include <iostream>

using namespace std;

void insertSort(int arr[], int length) {
	//传入的数组的第一个位置为哨岗
	
	for (int i = 2; i < length; i++) {
		//对数组中的每一个元素进行插入排序
		//因为数组中第一个元素即是最大值，也是最小值
		//不需要进行任何判断和操作，循环从 2 开始 
		
		arr[0] = arr[i];//哨兵设置为当前进行插入的元素
		
		int j = i;//从尾部开始比较。i 为已经插入元素的后一位
				  //即为当前进行插入的元素在数组中的位置
				  //哨兵已经记录下了这个元素，此时相当于一个空位

		//此时进行插入的元素的值小于已经插入的最后元素时才会进入循环
		//否则代表不用进行插入排序，因为这个元素放在这个位置刚刚好 
		while (arr[j - 1] > arr[0]) {
		//倒序与已经插入的元素依次进行比较（每次与前一个元素比较） 
		//若比较到的元素大于哨兵（此时插入的元素），将这个元素后移
		//若比较到的元素小于或等于哨兵，插入位置找到，退出循环 
			arr[j] = arr[j - 1];
			j--;
		} 
		arr[j] = arr[0];//将本次进行插入的元素插入找到的位置
	}
}

int main() {
	int n;
	
	cin >> n;//指定数组的长度 
	
	//声明一个长度为 n + 1 的数组（数组第一个位置为哨岗） 
	const int LEN = n + 1;
	int a[LEN];
	
	for (int i = 1; i < LEN; i++) {
		//从键盘输入指定数量的数组元素 
		cin >> a[i];
	} 
	
	insertSort(a, LEN);//对数组进行排序 
	
	for (int i = 1; i < LEN; i++) {
		cout << a[i] << ' ';
	}
	
	return 0;
}