目錄

一，排序的概念

二，直接插入排序

1，基本思想

2，基本思路

3，思路實現(xiàn)

三，希爾排序

1，希爾排序的特性總結(jié)：

2，思路實現(xiàn)：

一，排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作；

穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。

外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。

二，直接插入排序

1，基本思想

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

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

?實際中我們玩撲克牌時，就用了插入排序的思想：

2，基本思路

當插入第i(i>=1)個元素時，前面的 array[0],array[1],…,array[i-1] 已經(jīng)排好序，此時用array[i]的排序碼與 array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移；

直接插入排序的特性總結(jié)：

1，?元素集合越接近有序，直接插入排序算法的時間效率越高

2.，時間復雜度：O(N^2)

3，?空間復雜度：O(1)，它是一種穩(wěn)定的排序算法

4，?穩(wěn)定性：穩(wěn)定

3，思路實現(xiàn)

剛開始數(shù)組前一個數(shù) arr [ 0 ] 是有序的然后讓第二個數(shù) arr [ 1 ] 當做插入數(shù)使得前兩個數(shù)有序；

然后再讓第三個數(shù) arr [ 2 ] 當做插入數(shù)使得前三個數(shù)有序；

以此類推直至數(shù)組全部有序；

我們現(xiàn)在寫一個升序的直接插入排序：

//交換
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//插入排序
void InsertSort(int* arr, int n)
{
	int i = 0;
	for (i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] >= tmp)
			{
				//交換
				Swap(&arr[end], &arr[end+1]);
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

我們測試一下；

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

int main()
{
	int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
	//插入排序
	InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintSort(arr, sizeof(arr) / sizeof(arr[0]));
	return 0;
}

可以看到是有序的，直接插入排序就 OK 了；

三，希爾排序

希爾排序法又稱縮小增量法；

希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成 gap 組，所有距離為的 gap 的數(shù)組分在同一組，并對每一組內(nèi)的數(shù)據(jù)進行排序。然后重復上述分組和排序的工作。當 gap=1時，所有數(shù)組在統(tǒng)一組內(nèi)排好序;

圖示：

1，希爾排序的特性總結(jié)：

1，?希爾排序是對直接插入排序的優(yōu)化；

2，?當 gap > 1時都是預排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果；

3，?希爾排序的時間復雜度不好計算，因為 gap 的取值方法很多，導致很難去計算，因此在好些數(shù)據(jù)中給出的希爾排序的時間復雜度都不固定：

因為我們的 gap 是按照 Knuth 提出的方式取值的，而且 Knuth 進行了大量的試驗統(tǒng)計，我們暫時就按照：O（n^1.25) 到O(1,6*n^1.25) 來算，其實平均也就是 O（n*1.3）；

4.，穩(wěn)定性：不穩(wěn)定

2，思路實現(xiàn)：

我們先讓 gap 的值取總數(shù)據(jù)的一半也就是 n/2 ，然后每下次循環(huán)都縮減一半直至 gap=1 ，出循環(huán)程序結(jié)束；

//希爾排序
void HillSort(int* arr, int n)
{
	int gap = n;
	int i = 0;
	while (gap > 1)
	{
		gap = gap / 2;
		for (i = 0; i < n-gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] >= tmp)
				{
					//交換
					Swap(&arr[end], &arr[end + gap]);
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

還是上面那組數(shù)據(jù)：

這就 OK 了，其實就是換湯不換藥，學會了直接插入排序，希爾排序直接秒殺！

第一階段就到這里了，帶大家秒殺秒殺兩個排序熱熱身；

后面博主會陸續(xù)更新；

如有不足之處歡迎來補充交流！

完結(jié)。。

文章來源地址http://www.zghlxwxcb.cn/news/detail-721110.html

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