? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???食用指南：本文在有C基礎(chǔ)的情況下食用更佳?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ???這就不得不推薦此專欄了：C語言

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ??今日夜電波：透明で透き通って何にでもなれそうで—HaKU

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2:05?━━━━━━???──────── 5:38
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????? ? ?? ? ? ? ?? ? ???

????????????????????????????????????????關(guān)注??點贊??收藏您的每一次鼓勵都是對我莫大的支持???

目錄

??一、前置知識—什么是插入排序

??二、直接插入排序

? ? ? ??直接插入排序的思想

? ? ?? ?直接插入排序的實現(xiàn)?

? ? ? ? 直接插入排序的效率?

???三、希爾排序

? ? ? ? 希爾排序的思想

? ? ? ? 希爾排序的實現(xiàn)?

? ? ? ??? 希爾排序的效率?

??一、前置知識—什么是插入排序

????????插入排序的基本思想是將一個待排序的序列逐個插入到已經(jīng)排好序的序列中，直到全部元素都插入完成。每次插入一個元素時，將它與已經(jīng)排好序的元素逐個比較，找到它在已排好序列中的位置，并插入到該位置。具體實現(xiàn)時，可以將待排序序列分為已排序和未排序兩部分，從未排序序列中依次取出元素逐個插入已排序序列中，直到待排序序列為空為止。

? ? ? ? ?一個形象的??：

? ? ? ? 日常生活中我們在玩撲克時：將每一張牌都插入到一個有序的位置就是一種插入排序：

??二、直接插入排序

? ? ? ??直接插入排序的思想

? ? ? ??其基本思想是將待排序的元素插入到已經(jīng)有序的序列中，使得插入后的序列仍然有序。

????????具體操作步驟如下：

1. 將第一個元素看作已經(jīng)排好序的序列。
2. 依次將后面的元素插入到前面已經(jīng)排好序的序列中。
3. 對于未排序的元素，從后往前依次比較，若比前一個元素小則交換位置，直到找到合適的位置插入。
4. 重復(fù)步驟2和3，直到所有元素都插入到已排序的序列中。

? ? ? ? 一張經(jīng)典的插入排序動圖讓你理解：?

? ? ?? ?直接插入排序的實現(xiàn)?

????????詳細見代碼內(nèi)的注釋。

void InsertSort(int* a, int n)
{
	// [0,end]有序，把end+1位置的插入到前序序列
	// 控制[0,end+1]有序
	for (int i = 0; i < n - 1; i++)//遍歷每一個元素
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])//當后一個元素也就是tmp小于前面的某一個元素時先將前一個元素后移
			{
				a[end + 1] = a[end];
			}
			else//只要找到大于tmp的元素，直接跳出，然后插在這個元素后
			{
				break;
			}

			--end;//向前移動操作
		}

		a[end + 1] = tmp;//將要插入的元素也就是最后的元素插入到相應(yīng)的位置
	}
}

? ? ? ? 實現(xiàn)效果：

void Print(int* arr,int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}

	printf("\n");
}

int main()
{
	
	int arr[] = { 3,44,4,8,547,36,27,2,46,494,19,50,48 };
	Print(arr, sizeof(arr) / sizeof(arr[0]));
	InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
	Print(arr, sizeof(arr) / sizeof(arr[0]));

	return 0;
}

? ? ? ? 直接插入排序的效率?

????????1. 元素集合越接近有序，直接插入排序算法的時間效率越高
????????2. 時間復(fù)雜度：O(N^2)
????????3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
????????4. 穩(wěn)定性：穩(wěn)定

???三、希爾排序

? ? ? ? 希爾排序的思想

????????希爾排序通過將待排序的數(shù)組按照一定的間隔分組，對每組使用插入排序算法進行排序，隨著間隔的逐漸縮小，每組包含的元素數(shù)量逐漸增多，當間隔縮小至1時，整個序列被分成一組，算法便終止。

????????

????????希爾排序的步驟如下：

1. 首先選定一個增量gap，一般設(shè)置為數(shù)組長度的1/2，之后以gap為步長，將整個數(shù)組分為多個子序列（每個子序列長度為gap）。
2. 對于每個子序列，使用插入排序算法進行排序。
3. 縮小gap，重復(fù)第2步操作，直至gap為1時，整個序列被分成一組，算法終止。

? ? ? ? ?兩張經(jīng)典的圖讓你理解：

??

? ? ? ? 希爾排序的實現(xiàn)?

?????????詳細見代碼內(nèi)的注釋。

void ShellSort(int* a, int n)
{
	int gap = n;//首先，計算出最初的步長（通常為數(shù)組長度的一半）
	while (gap > 1)
	{
		gap = gap / 2;//對每個步長進行循環(huán)，直至步長為1
		//gap = gap / 3 + 1;//還有一種說法是每次除以3的步長，+1是為了保證最后gap==1

		for (int i = 0; i < n - gap; ++i)//前幾次為預(yù)排序，其實就是步長為gap的插入排序，當gap==1時就是插入排序了
		{
			int end = i;
			int tmp = a[end + gap];//按步長找到后一個元素
			while (end >= 0)
			{
				if (tmp < a[end])//當后一個元素也就是tmp小于前面的某一個元素時先將前一個元素后移
				{
					a[end + gap] = a[end];
				}
				else//只要找到大于tmp的元素，直接跳出，然后插在這個元素后
				{
					break;
				}
				end -= gap;//向前移動操作
			}
			a[end + gap] = tmp;//將要插入的元素也就是最后的元素插入到相應(yīng)的位置
		}
	}
}

????????? ? 實現(xiàn)效果：?

void Print(int* arr,int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}

	printf("\n");
}

int main()
{
	int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
	Print(arr, sizeof(arr) / sizeof(arr[0]));
	ShellSort(arr, sizeof(arr) / sizeof(arr[0]));

	Print(arr, sizeof(arr) / sizeof(arr[0]));

	return 0;
}

????????

? ? ? ??? 希爾排序的效率?

????????希爾排序的效率取決于增量序列的選擇。較好的增量序列可以使希爾排序比插入排序和選擇排序等簡單排序算法更加高效，但是對于不同的數(shù)據(jù)集，效率可能會有所差異。平均時間復(fù)雜度為O(n^1.3)，最壞時間復(fù)雜度為O(n^2)。希爾排序雖然不如快速排序和歸并排序等高級排序算法，但是在某些特定場景下具有很好的性能表現(xiàn)。

????????????????????感謝你耐心的看到這里?( ′???` )比心，如有哪里有錯誤請?zhí)咭荒_作者o(╥﹏╥)o！?

????????????????????????????????? ? ? ?

?????????????????????????????????????????????????????????????????????????給個三連再走嘛~??文章來源地址http://www.zghlxwxcb.cn/news/detail-716087.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】—從直接插入排序升級到希爾排序究極詳解（含C語言實現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！