C語言直接插入排序與希爾排序如何使用

這篇文章主要講解了“C語言直接插入排序與希爾排序如何使用”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“C語言直接插入排序與希爾排序如何使用”吧！

一.直接插入排序

1.1直接插入排序引入

排序是我們生活中經(jīng)常會面對的問題，以打撲克牌為例，你摸的手牌肯定是雜亂的，你一定會將小牌移動到大牌的左面，大牌移動到小牌的右面，這樣順序就算理好了。這里我們的理牌方法就是直接插入排序。

1.2直接插入排序的核心思想與算法分析

核心思想: 就是將一個記錄插入到已經(jīng)排好序的有序表中，從而得到一個新的記錄數(shù)增1的有序表。

算法分析：

• 從序列第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序

• 取出下一個元素，設(shè)為待插入元素，在已經(jīng)排序的元素序列中從后向前掃描，如果該元素（已排序）大于待插入元素，將該元素移到下一位置。

• 重復(fù)步驟2，直到找到已排序的元素小于或者等于待排序元素的位置，插入元素。

• 重復(fù)2，3步驟，完成排序。

1.3實例說明

以12，2，9，8，18，7這幾個數(shù)字為例，排序過程：

• 這里三角形表示要插入的值

• 橫線表示已經(jīng)排好序的數(shù)字

• j是趟數(shù)，是這一趟開始的時候已排序隊列的最后一個值的下標(biāo)。

1.4直接插入排序代碼實現(xiàn)

代碼如下：

void InsertSort(int* arr, int len)
{
	//assert arr!=NULL
	for (int i = 1; i < len; i++)//一共跑了多少趟  //01234   12345  
	{
		int tmp = arr[i];//待插入的值  
		//j 指向 這一趟開始的時候的已排序好的隊列中最后一個值的下標(biāo)
		int j;
		for (j = i - 1; j >= 0; j--)//這里控制待插入的值和 已排序隊列的挨著比較（從右向左比較）
		{
			if (arr[j] <= tmp)
			{
				break;//這時應(yīng)該停下來
			}
			else
			{
				arr[j + 1] = arr[j];
			}
		}
		arr[j + 1] = tmp;
	}
}

1.5直接插入排序性能分析

時間復(fù)雜度：

（1）順序排序時，只需比較(n-1)次，插入排序時間復(fù)雜度為O(n)；

（2）逆序排序時，需比較n(n-1)/2次，插入排序時間復(fù)雜度為O(n^2)；

（3）當(dāng)原始序列雜亂無序時，平均時間復(fù)雜度為O(n^2)。

空間復(fù)雜度：

插入排序過程中，需要一個臨時變量temp存儲待排序元素，因此空間復(fù)雜度為O(1)。

算法穩(wěn)定性：

插入排序是一種穩(wěn)定的排序算法。

二.希爾排序

2.1希爾排序引入

希爾排序其實就是對直接插入排序的優(yōu)化，在第一部分我們說過==(1)直接插入排序數(shù)據(jù)越有序，插入的效率就越高；(2)記錄數(shù)比較少時，直接插入的優(yōu)勢也很明顯。==希爾排序就是根據(jù)這兩個特點進(jìn)行的優(yōu)化。

2.2希爾排序的核心思想與算法分析

核心思想： 通過一個不斷縮小的增量序列，對無序序列反復(fù)的進(jìn)行拆分并且對拆分后的序列使用插入排序的。

算法分析：

1. 先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）；

2. 分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序；

3. 待整個序列中的元素基本有序（增量足夠?。r，再對全體元素進(jìn)行一次直接插入排序；

4. 完成排序。

2.3實例說明

以12，2，9，8，5，88，99，10，7，17，77，66，89，10，21為例，排序過程如下：

• 這里相同顏色的線相同的分組

• 每次增量取上一次的一半（向下取整）

• 注意：最后一個增量值必須等于1才可以

2.4希爾排序代碼實現(xiàn)

代碼如下：

void Shell(int arr[], int len, int gap)//一趟希爾排序
{
	for (int i = gap; i < len; i++)//i++  不是i=i+gap;
	{
		int tmp = arr[i];//待插入的值  
		//j 指向 這一趟開始的時候的已排序好的隊列中最后一個值的下標(biāo)
		int j;
		for (j = i - gap; j >= 0; j = j - gap)//這里控制待插入的值和 已排序隊列的挨著比較（從右向左比較）
		{
			if (arr[j] <= tmp)
			{
				break;//這時應(yīng)該停下來
			}
			else
			{
				arr[j + gap] = arr[j];
			}
		}
		arr[j + gap] = tmp;
	}
}
void ShellSort(int arr[], int len)
{
	int gap[] = { 5, 3, 1 };//
	int gap_len = sizeof(gap) / sizeof(gap[0]);
	for (int i = 0; i < gap_len; i++)
	{
		Shell(arr, len, gap[i]);
	}
}

2.5希爾排序性能分析

時間復(fù)雜度：

希爾排序的時間復(fù)雜度依賴于增量序列的函數(shù)，當(dāng)n在某個特定的范圍后最優(yōu)的情況下，希爾排序的時間復(fù)雜度為O(n ^ 1.3)，在最差的情況下，希爾排序的時間復(fù)雜度為：O(n ^ 2)。

空間復(fù)雜度：

希爾排序的空間復(fù)雜度：O(1)。

算法穩(wěn)定性：

希爾排序并不是一種穩(wěn)定的排序算法。

感謝各位的閱讀，以上就是“C語言直接插入排序與希爾排序如何使用”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對C語言直接插入排序與希爾排序如何使用這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！