??個人主頁：Ice_Sugar_7
??所屬專欄：初階數(shù)據(jù)結(jié)構(gòu)
??歡迎點贊收藏加關(guān)注哦！

??插入排序

插排就是將一個元素插入一個有序序列中合適的位置，分為直接插入排序和希爾排序

??直接插入排序

流程如下：
①保存待插入的值：假設(shè)某一趟中有序序列最后一個元素下標為end，先保存（end+1）位置的元素，保存到臨時變量tmp。

②為a[end+1]找到合適的位置：使用while循環(huán)，里面比較a[end]和a[end+1]的大小。
若前者<后者，就退出循環(huán)
反之，則將a[end]往后挪一位，覆蓋掉a[end+1]，end減1，然后讓tmp繼續(xù)往前找，直到找到比它小的元素或者end < 0（end<0說明所有元素都比tmp大，那么就應(yīng)該把tmp放在a[0]），插到該元素后面。
簡而言之就是讓tmp向前找比它小的元素，找到就插在它的后面；找不到就是插在第一位

③至此，我們排好了一個數(shù)據(jù)，現(xiàn)在要排列所有元素，只需在外面套上一層for循環(huán)
（假設(shè)數(shù)組有n個元素，注意循環(huán)的終止條件是i < n-1，即i最多只能取到n-2，因為是 i 和 i+1 進行比較）

比如：

int a[] = {2,7,1,9,6,5,8};

圖解如下：

代碼如下：

//n為數(shù)組元素個數(shù)
void InsertSort(int* a, int n) {
	for (int i = 0; i < n-1; i++) {
		int end = i;  //end為有序序列最后一個元素的下標
		int tmp = a[end + 1];  //tmp保存待插入的數(shù)據(jù)
		while (end >= 0)
		{
			if (a[end + 1] < a[end]) //待插入的數(shù)比end小，那么end就向后移動，給待插入的數(shù)據(jù)挪出位置
				a[end + 1] = a[end];
			else
				break;
			end--;  //更新end，向前找小 
		}
		//找到小或end == -1
		a[end + 1] = tmp;
	}
}

??復(fù)雜度及穩(wěn)定性

時間復(fù)雜度：第一趟1次，第二趟2次……由等差數(shù)列公式可以推出是O（N^2）
空間復(fù)雜度：O（1）
穩(wěn)定性：穩(wěn)定

??希爾排序

希爾排序是直接插入排序的優(yōu)化。分兩步完成：預(yù)排序+直接插入排序
預(yù)排序的意義：讓大的數(shù)更快到后面，小的數(shù)更快到前面。使序列趨于有序，降低直接插入排序的成本

??預(yù)排序

直接插入排序是讓相鄰的元素進行比較。預(yù)排序則是讓一個元素和與它相隔幾個位置的元素比較
比如：

int a[] = {9,1,2,5,7,4,8,6,3,5};

9、5、8、5可以分為一組；1、7、6也是一組；2、4、3同理
同一組的元素進行比較，排好序。
預(yù)排序后得到：

這樣就完成了一次預(yù)排序。希爾排序中有多次預(yù)排序，每次排完后會縮小間隔、重新分組，然后繼續(xù)預(yù)排序。假設(shè)最開始的間隔為gap，那么就一直縮小，gap越小，預(yù)排序一次后序列就越趨于有序。直到gap為1，此時就是直接插入排序，這一次排好后序列就有序了

gap每次預(yù)排序一般是縮小到上一次的一半，或是1/3（注意gap除以3之后需要+1，保證gap不為0）
代碼如下：

void ShellSort(int* a, int n) {
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;  //+1確保gap至少為1，最后一次循環(huán)gap == 1
		//一次預(yù)排序
		for (int i = 0; i < n - gap; i++)  //i+gap最多取到n-1
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
					a[end+gap] = a[end];
				else
					break;
				end -= gap;
			}
			a[end + gap] = tmp;
		}
	}
}

??復(fù)雜度及穩(wěn)定性

時間復(fù)雜度：O(N^1.3)
空間復(fù)雜度：O（1）
穩(wěn)定性：不穩(wěn)定。因為預(yù)排序很容易就把相同的數(shù)的相對順序打亂了

??選擇排序

排序思路：
●假設(shè)序列最左邊、右邊下標分別為begin、end
●從序列中找出最大、最小值，并分別將它們放到下標為begin、end的地方
●找出第二大和第二小，分別放到begin+1、end-1
●剩下元素也按照這樣排列

在“交換位置”這一步有一個很坑的點，如果最小值剛好在end，那就會和最大值交換位置，但是此時我們的mini仍然在end，直接交換a[mini]和a[begin]就會把最大值和begin處的元素交換位置
所以在最大值和a[end]交換之后檢查一下，看mini是否在end處。如果是，就將maxi賦值給mini（因為此時maxi指向的就是最小值）

void SelectSort(int* a, int n) {
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin,maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[maxi] < a[i])
				maxi = i;
			if (a[mini] > a[i])
				mini = i;
		}
		Swap(&a[maxi], &a[end]);
		if (end == mini)  //讓mini重新指向最小值
			mini = maxi;
		Swap(&a[mini], &a[begin]);
		++begin;
		--end;
	}
}

??復(fù)雜度及穩(wěn)定性

時間復(fù)雜度：第一趟走（n-2）次，第二趟走（n-4）次，第 i 趟走（n-2*i）次……由等差數(shù)列公式，可以得出時間復(fù)雜度為O（N^2）
空間復(fù)雜度：O（1）
穩(wěn)定性：不穩(wěn)定。比如1 9 9 4 2 1 3 6，第一趟第一個9就會被換到最后面

??堆排序

前面的文章有講過，升序建大堆，降序建小堆
比如排升序，就建大堆，然后讓堆頂元素和堆中最后一個元素交換位置，再進行調(diào)整

void HeapSort(int* a, int k) {  //a為給定數(shù)組
	for (int i = (k - 1 - 1) / 2; i >= 0; i--) {   //調(diào)整為一個堆
		AdjustDown(a, k, i);
	}

	for (int i = k - 1; i >= 0; i--) {  //采用刪除結(jié)點的思想，先交換，再調(diào)整
		Swap(a[0], a[i]);
		AdjustDown(a, i, 0);
	}
}

??復(fù)雜度及穩(wěn)定性

時間復(fù)雜度：如果有n個數(shù)據(jù)，那么堆的深度就是logn，最壞情況下，有（n-1）個數(shù)據(jù)需要調(diào)整，所以近似是（n-1）logn，又因為logn的量級比nlogn小，可以忽略，所以時間復(fù)雜度就是O（N*logN）
（注意：實際比N * logN略小一些）

上面說“近似”是因為并不是每個數(shù)據(jù)都要調(diào)整logn層，但是由于logn一般不大（參考：2的30次方是10億多一點，此時logn就是30），它的大小一般就是幾十這樣子，所以相差這一點對于時間復(fù)雜度基本沒影響

空間復(fù)雜度：O（1）
穩(wěn)定性：不穩(wěn)定

??寫在最后

以上就是本篇文章的全部內(nèi)容，如果你覺得本文對你有所幫助的話，那不妨點個小小的贊哦?。ū刃模?/strong>文章來源地址http://www.zghlxwxcb.cn/news/detail-779570.html

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