#include <stdio.h>

/**
* 预先理解:把前i个当成排好序的,后面当成没有排好序的,把没排好序的一个个插到排好序的序列中
* 插入排序关键点:
* 理解:就像打扑克牌你抓到一张牌为他找合适的位置一样
* 在程序中实现,用key保存要插入排序的值,在循环中不断腾位置直到循环结束
* 最后把key放到找到的确切位置
*/

//插好一个元素(n代表元素位置)
void insertion(int arr[], int n) {
	int key = arr[n];
	int i = n;
	while (i > 0 && arr[i - 1] > key) {
		arr[i] = arr[i - 1];	//不断向后copy腾位置
		--i;
	}
	arr[i] = key;
}

//插入排序(从前到后一个个向前插入)
int insertionSort(int arr[], int n) {
	if (n > 1) {
		insertionSort(arr, n-1);
		insertion(arr, n);

	}
	else {
		return 0;
	}
}

void print(int arr[], int n) {
	int i;
	for (i = 0; i < n; ++i) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main() {
	int arr[5] = {6, 3, 15, 4, 8};
	printf("Before: ");
	print(arr, 5);
	
	insertionSort(arr, 4);

	printf("After: ");
	print(arr, 5);

	return 0;
}