数据结构与算法篇--插入排序

插入排序

插入排序的核心思想是，从前到后找排序元素，然后出坑；然后从后到前找插入位置，入坑。如果是升序排序的话，如果当前项的数值大于排序元素，那么就让当前数值向后移动，反之则请排序元素直接进入空隙

核心思想

从前到后找待排序元素，从后到前找插入位置。每次都在更新，每次都在迭代知道全部结束。每一次都在排小的，然后越来越大，前到后，步步都是基础，后面依赖前面。

C语言实现

插入排序

#include<stdio.h>
int* InsertSort(int*arr,int size) {
	for (int i = 1; i < size; i++) {
		int item = *(arr + i);
		int cur = i - 1;
		//升序排列
		while (cur >= 0 && arr[cur]>item) {
			arr[cur + 1] = arr[cur];
			cur--;
		}
		arr[cur + 1] = item;
	}
	return arr;
}
int main() {
	int* p = NULL;
	int arr[3] = {3,4,5};
	p = arr;
	p=InsertSort(p,3);
	for (int i = 0; i < 3; i++) {
		printf("%d ",*(p+i));
	}
	return 0;
}