C語言深入淺出講解直接插入排序算法的實現(xiàn)

更新時間：2022年05月18日 10:53:02 作者：安然無虞

插入排序也是最簡單的一類排序方法，我今天介紹的也是插入排序里最直觀且淺顯易懂的直接插入排序。對這個很簡單的排序，記得當時也是花了近兩個晚上才搞懂它的原理的，接下來就來介紹一下

直接插入排序

1.基本思想

直接插入排序是一種簡單的插入排序算法，其基本思想是：

把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。

說得通俗一點就是：

假設區(qū)間[0, end]有序，將end+1位置的值插入到[0, end]中，保持區(qū)間[0, end+1]依舊有序。

生活中我們玩撲克牌時，就用了插入排序的思想。

在這里，我們以排升序為例。

核心思想：摸牌的過程

動圖演示：

2.算法實現(xiàn)

寫排序時，先從單趟開始考慮

//[0, end]已經(jīng)有序，將end+1位置的值插入到[0,end]中，使得[0,end+1]依舊保持有序
//有一個有序區(qū)間，插入一個數(shù)據(jù)，依舊保持有序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	//控制摸牌的過程，一開始從僅一張開始
	//注意循環(huán)結(jié)束條件，只需要到n-2的位置，若將其改成i<n，則會出現(xiàn)越界的情況
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)//保證牌是有序的
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];//往后挪，注意畫圖感受哦
				end--;
			}
			else
			//有兩種可能：（現(xiàn)想常規(guī)的，再考慮特殊情況）
			//一是找到了比它小的數(shù)，放到其后；
			//二是沒有比它小的數(shù)，直到end為-1才結(jié)束
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

完整代碼：