原理

插入排序是一种经典的排序算法,其实现原理就是每一步将一个待排元素插入到已经有序的数据中,下面主要分析插入排序中的直接插入排序。(原理通常晦涩难懂,说得直白一点就是,一群身高学生站成了一列,然后体育老师从第二个学生开始,把这个学生拎出来排到前面对应他身高的位置上去)。

排序图

代码实现

直接插入排序适用于待排序数列略微整齐,时间复杂度为O(n^2),是稳定排序。

#include "stdio.h"

// 插入排序
void insertSort(int *arr, int length) {
	int i, j, key;
	for (i = 1; i < length; i++) {
		key = arr[i];
		j = i - 1;
         // 当前一个元素的值比当前值大,则依次向前移动游标
		while (j >= 0 && arr[j] > key) {
			arr[j+1] = arr[j];
		  	j--;
		}
		arr[j+1] = key;
	}
}

int main() {
	int arr[10] = {2,6,1,0,3,9,7,8,5,4};
	insertSort(arr,10);
	for (int i = 0; i < 10; i++) {
	  printf("%d,",arr[i]);
	}
	return 0;
}