??

文章目錄

引入

一、插入排序

1、1 插入排序的實現(xiàn)思想

1、2 插入排序的代碼實現(xiàn)及特點分析?

二、希爾排序

2、1 希爾排序的實現(xiàn)思想

2、2 希爾排序的代碼實現(xiàn)及特點分析?

三、選擇排序

3、1 選擇排序的實現(xiàn)思想

3、2 選擇排序的代碼實現(xiàn)及特點分析

四、堆排序

五、冒泡排序

六、快速排序

6、1 快速排序遞歸形式實現(xiàn)

6、2 快速排序的非遞歸形式實現(xiàn)

6、2、1?快速排序非遞歸形式的實現(xiàn)思想

6、2、2?快速排序非遞歸形式的代碼實現(xiàn)?

七、歸并排序

7、1 遞歸實現(xiàn)歸并排序

7、2 歸并排序非遞歸實現(xiàn)?

7、2、1?歸并排序非遞歸形式的實現(xiàn)思想

7、2、2?歸并排序非遞歸形式的實現(xiàn)代碼及邊界處理

總結(jié)

---

???♂??作者：@Ggggggtm????♂?

???專欄：數(shù)據(jù)結(jié)構(gòu)與 ??

???標題：排序算法 ??

????寄語：與其忙著訴苦，不如低頭趕路，奮路前行，終將遇到一番好風(fēng)景???

? 本編文章詳解常見七大大排序（插入排序、希爾排序、選擇排序、冒泡排序、堆排序、快速排序、歸并排序），其中快速排序和歸并排序遞歸實現(xiàn)是我們常見的思路，但是非遞歸實現(xiàn)的情況相對少見，理解起來也會有點難度，本篇文章會給出詳解！

引入

? 排序算法重要嗎？排序算法有什么用呢？我給大家舉一個例子先看一下：

? 我想網(wǎng)上購物是平常很常見的事情了吧。我們?yōu)榱烁玫倪x擇出自己理想的物品，我們通常會根據(jù)物品的價格或者銷量等條件進行篩選。那么這就是一個排序。

? 還有我們經(jīng)常說到的大學(xué)的好壞：

? 大學(xué)之間的排名也會是根據(jù)很多指標進行綜合排序來定名次的。在日常生活中，用到的排序的例子還有很多很多，也間接體現(xiàn)出來排序的重要性。我們應(yīng)該熟練的掌握常見排序的細節(jié)及其用法。? 上圖即為我們要詳解的七大常見排序，我們接下來進入整體。

一、插入排序

1、1 插入排序的實現(xiàn)思想

? 插入排序是我們在生活中經(jīng)常見的一種排序。例如玩撲克牌時，我們一張一張的抽取撲克牌，每抽取一張，我們自己會對它進行排序，放到合適的位置。

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

? 我們可結(jié)合下圖理解：

? 從上圖中，我們再詳細分析一下插入排序的實現(xiàn)思路：

1. 首先第一個數(shù)據(jù)不用進行比較，當(dāng)只有一個數(shù)據(jù)時，我們可以理解為是有序的；
2. 選取下一個數(shù)據(jù)，看是否大于前一個元素。如果大于前一個元素，我們直接可以把該數(shù)據(jù)放到前一個元素的后面。如果小于前一個元素，我們需要把前一個元素后移一位。
3. 每插入一個新的元素，我們需要比較的時前面已經(jīng)有序的所有數(shù)據(jù)，直到找到大于前一個元素數(shù)據(jù)即可停下，否則將會放在首位。
4. 每插入一個元素，重復(fù)上述操作即可完成有序。

? 上述即為插入排序的整個實現(xiàn)的過程，我們接下來看一下插入排序的代碼實現(xiàn)。

1、2 插入排序的代碼實現(xiàn)及特點分析?

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = a[i + 1];
		
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}

		a[end + 1] = tmp;
	}
}

? 我們學(xué)完插入排序后不難發(fā)現(xiàn)，正常情況下插入排序的時間復(fù)雜度為O(N^2)。只有極少的特殊情況（有序）的實現(xiàn)復(fù)雜度為O（N），效率并不是太理想。

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

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

? 我們還可對插入排序進行優(yōu)化碼？答案是可以的。下面我們看希爾排序，就是在插入排序上進行了優(yōu)化。

二、希爾排序

2、1 希爾排序的實現(xiàn)思想

? 通過上述的插入排序特性元素集合越接近有序，直接插入排序算法的時間效率越高，我們想到：是否在對改組數(shù)據(jù)排序前進行預(yù)排序呢？通過預(yù)排序是的數(shù)組達到接近有序的狀態(tài)呢？希爾排序因此誕生了。

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

? 具體思路可結(jié)合下圖理解：?

? 那gap的大小怎么選呢？當(dāng)gap越大時，大的數(shù)據(jù)往后跳躍的越塊，但是排完后并沒有那么有序。當(dāng)gap越小時，大的數(shù)據(jù)往后跳躍的越慢，但是排完后相對已經(jīng)很有序了。所以在這里我們gap的取法就是從數(shù)組的大小折半開始，一直折半，直到為1時，排完后有序就停止。當(dāng)然，也就可以除以3，但是要注意其中的細節(jié)，最后一趟排序gap必為1。

? 這里就會有一些疑問：上述的每一趟以gap為一組的數(shù)據(jù)排序都是用插入排序的思想實現(xiàn)的，那時間復(fù)雜度不是會更高嗎？我們先看希爾排序的代碼實現(xiàn)。

2、2 希爾排序的代碼實現(xiàn)及特點分析?

void ShellSort(int* a, int n)
{
    //以gap為3的數(shù)據(jù)一組的預(yù)排序代碼，該排序分3趟
	/*int gap = 3;
	for (int j = 0; j <gap; j++)
	{
		for (int i = j; i < n - gap; i += gap)
		{
			int end = i;
			int tmp = a[i + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}*/
    
    //希爾排序
	//n!=1的情況，全為預(yù)排序
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
        //同時對所有以gap為一組的進行排序
		for (int i = 0; i < n - gap; i ++)
		{
			int end = i;
			int tmp = a[i + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
		
	}
}

? ?通過上述代碼，我們這里是根據(jù)插入排序特性元素集合越接近有序，直接插入排序算法的時間效率越高進行的預(yù)排序。當(dāng)gap為1時，代碼與插入排序的代碼相同，但是此時的數(shù)據(jù)已經(jīng)幾乎接近有序，并不需要消耗太多，時間復(fù)雜度接近O（N）。

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

1. ?希爾排序是對直接插入排序的優(yōu)化。
2. 當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
3. 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些書中給出的希爾排序的時間復(fù)雜度都不固定：
4. 穩(wěn)定性：不穩(wěn)定。

三、選擇排序

3、1 選擇排序的實現(xiàn)思想

? 選擇排序的實現(xiàn)就比較簡單了。選擇排序的基本思想：每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的 數(shù)據(jù)元素排完 。也就是我們需要進行n趟尋找，每趟去尋找未排序的最小（或最大）元素完成排序。

? 我們結(jié)合下圖一起理解一下：

? 我們直接看代碼的實現(xiàn)：

3、2 選擇排序的代碼實現(xiàn)及特點分析

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

void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;

	while (left < right)
	{
		int maxi = left, mini = right;
		for (int i = left; i <= right; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

		Swap(&a[left], &a[mini]);

		//如果左邊界與最大的數(shù)重合，交換左邊界與最小的值后，最大值的位置下標變?yōu)榻粨Q后的下標
		if (left == maxi)
		{
			maxi = mini;
		}
		Swap(&a[right], &a[maxi]);

		left++;
		right--;
	}
}

? 直接選擇排序的特性總結(jié)：

1. ?直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用；
2. ?時間復(fù)雜度：O(N^2)；
3. 空間復(fù)雜度：O(1)；
4. 穩(wěn)定性：不穩(wěn)定

四、堆排序

? 堆排序，我們在之前的文章中（重點算法排序之堆排序）詳細講述了其實現(xiàn)的細節(jié)。我們可以直接去參考學(xué)習(xí)一下。

五、冒泡排序

? 我們之前的文章也有對冒泡排序（冒泡排序詳解）的詳解，需要學(xué)習(xí)的也可去參考一下。

六、快速排序

6、1 快速排序遞歸形式實現(xiàn)

??重點算法排序之快速排序詳解了快速排序的三種遞歸實現(xiàn)的方法，可以直接參考學(xué)習(xí)。

6、2 快速排序的非遞歸形式實現(xiàn)

6、2、1?快速排序非遞歸形式的實現(xiàn)思想

? 通過學(xué)習(xí)了遞歸形式實現(xiàn)的快速排序后，我們了解到遞歸實現(xiàn)其實就是采用了分治的思想 。但是當(dāng)數(shù)據(jù)量特別大、遞歸層數(shù)較多時，有可能會造成棧溢出（爆棧），導(dǎo)致進程無法正常進行。這里也可采用小區(qū)間優(yōu)化方法，但是我們想能不能采用非遞歸的方式去實現(xiàn)快排呢？如果不遞歸，采用循環(huán)的方式同樣不會爆棧，而且更加安全。答案是可以的。

? 我們首先需要去分析遞歸方式實現(xiàn)快排的一些性質(zhì)：

• 每次遞歸前我們會先選出一個關(guān)鍵數(shù)據(jù)，作為我們的keyi來劃分左右區(qū)間；
• 每次的遞歸是去遞歸的左子區(qū)間和右子區(qū)間，對左子區(qū)間和右子區(qū)間進行排序劃分；
• 當(dāng)遞歸到左子區(qū)間和右子區(qū)間不存在時，就停止遞歸；
• 當(dāng)遞歸到左子區(qū)間和右子區(qū)間只有一個數(shù)據(jù)時，我們認為它就是有序的，停止遞歸。

? 通過上面分析，我們發(fā)現(xiàn)每次遞歸都是需要明確知道左右子區(qū)間下標的。于是在這里我們 就想到如果采用非遞歸，我們需要把所有的左右子區(qū)間下標保存下來。對其進行劃分排序倒不難，主要是怎么保存起來左右子區(qū)間的下標呢？

? ?當(dāng)我們自己去畫一下遞歸實現(xiàn)快排的展開圖時我們會發(fā)現(xiàn)到，遞歸完左子區(qū)間才會去遞歸右子區(qū)間。每遞歸一個區(qū)間，會劃分出新的兩個區(qū)間。我們這時候想到用棧去存儲區(qū)間下標。最初我們存儲進去其實的下標，再去循環(huán)劃分排序左右子區(qū)間，并且把左右子區(qū)間把左右子區(qū)間的下標加入棧中。循環(huán)時，從棧中去取出下標。當(dāng)左右子區(qū)間不存在時，或者只有一個數(shù)據(jù)時，我們認為它就是有序的，不再加入棧中。直到棧為空時，循環(huán)停止。我們結(jié)合下面代碼一起理解一下。

6、2、2?快速排序非遞歸形式的代碼實現(xiàn)?

int PartSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	//int randi = left + (rand() % (right - left));
	int midi = MidKey(a, left, right);
	if (midi != left)
		Swap(&a[left], &a[midi]);
	int keyi = left;
	int begin = left, end = right;
	while (left < right)
	{
		//如果是從左邊界為分界點，那么必須從右邊開始找，以確定right==left的位置為較小的哪一個
		//右邊找小
		while (left<right && a[right]>a[keyi])
		{
			right--;
		}

		//左邊找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[keyi], &a[left]);

	keyi = left;
	return keyi;
}
void QuickSortNoCir(int* a, int left, int right)
{
	ST st;  //建立一個棧，這里用C語言實現(xiàn)，引用了已實現(xiàn)棧的頭文件，在C++中，可直接用STL中的容器
	STInit(&st);

	STPush(&st, left);
	STPush(&st, right);

	while (!STIsEmpty(&st))
	{
		int right = STTop(&st);
		STPop(&st);

		int left = STTop(&st);
		STPop(&st);

		int keyi = PartSort(a, left, right);

		if (keyi + 1 < right)
		{
			STPush(&st, keyi + 1);
			STPush(&st,  right);
		}

		if (keyi - 1 > left)
		{
			STPush(&st, left);
			STPush(&st, keyi - 1);
		}
	}

	STDestory(&st);
}

? 這里的一個區(qū)間的排序與遞歸實現(xiàn)的排序相同，我們在這里只不過是把它單獨劃分為一個函數(shù)。?

七、歸并排序

7、1 遞歸實現(xiàn)歸并排序

? 重點算法排序之歸并排序?對歸并排序進行了詳解，可參考學(xué)習(xí)。

7、2 歸并排序非遞歸實現(xiàn)?

7、2、1?歸并排序非遞歸形式的實現(xiàn)思想

? 歸并排序的非遞歸實現(xiàn)又該怎么實現(xiàn)呢？當(dāng)我們了解了遞歸實現(xiàn)后，遞歸實現(xiàn)是先將整個區(qū)間劃分為左右兩個大區(qū)間，接著不斷劃分子區(qū)間，直到一個區(qū)間的大小為1開始歸并的。于是我們非遞歸實現(xiàn)也可從一個區(qū)間的大小為1開始歸并。當(dāng)區(qū)間為1時，也就只有一個數(shù)據(jù)就被視為有序，所以就可以開始歸并。當(dāng)1個數(shù)與1個數(shù)歸并完后，相當(dāng)于兩個數(shù)的區(qū)間是有序的，就開始歸并兩個數(shù)據(jù)的區(qū)間。以此類推，最終將整個區(qū)間歸并為有序區(qū)間。大致過程可參考下圖：

? 這樣考慮似乎并沒有什么錯。但是當(dāng)數(shù)組的元素個數(shù)為9個呢？我們打印出歸并的區(qū)間看看：

? 我們發(fā)現(xiàn)確實有很多越界的情況。因此，我們要對越界的情況進行特殊處理。我們先來開歸并排序非遞歸實現(xiàn)的代碼，在對越界情況處理進行解釋。

7、2、2?歸并排序非遞歸形式的實現(xiàn)代碼及邊界處理

void MergeSortNoCir(int* a, int left, int right)
{
	int* tmp = (int *)malloc(sizeof(int) * (right - left + 1));
	if (tmp == NULL)
	{
		perror("malloc failed");
		return;
	}

	int n = right - left + 1;
	int gap = 1;
	while (gap < n)
	{
		for(int i = 0; i < n;i += 2*gap )
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			if (begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			int j = 0;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1];
					begin1++;
				}
				else
				{
					tmp[j++] = a[begin2];
					begin2++;
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1];
				begin1++;
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2];
				begin2++;
			}

			memcpy(a + i, tmp, sizeof(int)*(end2 - i + 1));
		}
		gap *= 2;
	}

	free(tmp);
}

? 在這里我們把區(qū)間的邊界劃分為[ begin1 ] [ end1 ] - [ begin2 ] [ end2 ]。首先，begin1 是不可能越界的，因為我們是把 i 的值 begin1。然后我們再分情況處理越界的問題：

• end1 越界，就不再動該組數(shù)據(jù)（break）；
• begin2 越界，也是不再動該組數(shù)據(jù)（break）；
• end2 越界，begin2 沒有越界。修改end2，再歸并改組數(shù)據(jù)。

? ?上述情況中，end1和begin2越界為什么就不在動該組數(shù)據(jù)呢？歸并的前提是該組數(shù)據(jù)有左右兩個有序子區(qū)間，只有一個區(qū)間是不用歸并的。因為一但end1和begin2越界，該組數(shù)據(jù)就不能夠進行歸并。越界情況的數(shù)據(jù)就在原數(shù)組中沒有動，也就是并沒有歸并到tmp數(shù)組中，所以也不用再拷貝回去。?

? end1越界的情況，begin2也一定越界。但是end1不越界的話，begin2也有可能越界。如果end1不越界，同時begin2也不越界，就進入到了else if (end2 >= n)的情況。所以，在這里我們發(fā)現(xiàn)，不用判斷end1的情況也是可以的。

? 我們再來看加入越界判斷后的區(qū)間劃分：

? 通過上述劃分區(qū)間，我們發(fā)現(xiàn)不會再出現(xiàn)區(qū)間越界的情況，同時也不會漏掉任何區(qū)間。

總結(jié)

? 排序總體難度還是比較大的，也是重點掌握內(nèi)容，尤其是快速排序和歸并排序。在這里給大家總結(jié)出一張關(guān)于排序的表格：? ?大家也可借助此表格來理解和記憶排序算法。本篇文章的講解就到這里，希望以上內(nèi)容會對你有所幫助，感謝觀看ovo~?文章來源地址http://www.zghlxwxcb.cn/news/detail-415468.html

到了這里，關(guān)于排序算法終極篇之手撕常見排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！