算法思想

直接插入排序的算法思想：每趟将一个待排序的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置，直到所有待排关键字都被插入到有序序列中为止。

执行过程

下面画图具体说明下执行过程是实现一步步实现的：

代码

/* 快速插入排序 */
/* R[]指的是要进行排序的原数组；n指的是数组中元素个数 */ 
void sort(int R[],int n) {
	for(int i=1;i<n;i++){// 从下标1开始，循环遍历数组中的每个元素
		// 为什么不从0开始？因为要将nums[i]与nums[i]之前的所有数比较大，如果从0开始，下标就会溢出 
		int j=i-1;// 表示nums[i]的前一个元素的下标，从后往前遍历 
		int temp=R[i];// 临时保存要插入的元素 
		while(j>=0&&temp<R[j]){// 遍历比较，将nums[i]之前的所有元素同temp相比较，直到遇到比nums[i]小的才停止，如果比nums[i]大则一直比较下去 
			// 为什么要j>=0这个条件呢？因为在j--过程中j可能出界 
			R[j+1]=R[j];// 将元素向后移动一个位置 
			// 为什么是R[j+1]=R[j]而不是R[j]=R[j-1]呢？因为要从i位置开始，而j=i-1，i=j+1，所以覆盖值要从j+1开始。 
			j--;
		}
		R[j+1]=temp;// 将空出来的位置放入temp 
		// 为什么是j+1呢？因为在while循环中，最后要进行j--，故要加上1才表示空位置		
	}
}

完整代码：

#include<stdio.h>

/* 打印数组元素 */
void print(int nums[],int n) {
	printf("\n");
	for(int i=0; i<n; i++) {
		printf("%d\t",nums[i]);
	}
	printf("\n");
}

/* 快速插入排序 */
/* R[]指的是要进行排序的原数组；n指的是数组中元素个数 */
void sort(int R[],int n) {
	for(int i=1; i<n; i++) { // 从下标1开始，循环遍历数组中的每个元素
		// 为什么不从0开始？因为要将nums[i]与nums[i]之前的所有数比较大，如果从0开始，下标就会溢出
		int j=i-1;// 表示nums[i]的前一个元素的下标，从后往前遍历
		int temp=R[i];// 临时保存要插入的元素
		while(j>=0&&temp<R[j]) { // 遍历比较，将nums[i]之前的所有元素同temp相比较，直到遇到比nums[i]小的才停止，如果比nums[i]大则一直比较下去
			// 为什么要j>=0这个条件呢？因为在j--过程中j可能出界
			R[j+1]=R[j];// 将元素向后移动一个位置
			// 为什么是R[j+1]=R[j]而不是R[j]=R[j-1]呢？因为要从i位置开始，而j=i-1，i=j+1，所以覆盖值要从j+1开始。
			j--;
		}
		R[j+1]=temp;// 将空出来的位置放入temp
		// 为什么是j+1呢？因为在while循环中，最后要进行j--，故要加上1才表示空位置
	}
}

int main() {
	int nums[]= {49,38,65,97,76,13,27,49};
	int n=8;
	printf("排序前：");
	print(nums,n);

	sort(nums,n);// 进行插入排序
	printf("排序后：");
	print(nums,n);

	return 0;
}

运行效果：