資料結構與算法篇--插入排序

插入排序

插入排序的核心思想是，從前到後找排序元素，然後出坑；然後從後到前找插入位置，入坑。如果是升序排序的話，如果目前項的數值大于排序元素，那麼就讓目前數值向後移動，反之則請排序元素直接進入空隙

核心思想

從前到後找待排序元素，從後到前找插入位置。每次都在更新，每次都在疊代知道全部結束。每一次都在排小的，然後越來越大，前到後，步步都是基礎，後面依賴前面。

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;
}