【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

英杰社區(qū)https://bbs.csdn.net/topics/617804998

常見算法的實(shí)現(xiàn)

? ? ? ? 插入排序

????????希爾排序

? ? ? ? 堆排序

? ? ? ? 選擇排序

????????冒泡排序

????????快速排序

? ? ? ? Hoare版本

????????隨機(jī)選Keyi? ? ??

????????三數(shù)取中

????????挖坑法

? ? ? ? 前后指針版本

????????歸并排序

常見算法的實(shí)現(xiàn)

? ? ? ? 插入排序

? ? ? ? ? ? ? ? 動(dòng)畫演示：

【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序

????????思路(升序)：

? ? ? ? ? ? ? ? 從最開始前，我們?nèi)〉谝晃粩?shù)和第二位數(shù)，進(jìn)行比較，如果第一位數(shù)大于，第二位數(shù)，

則將第一位數(shù)和第二位數(shù)進(jìn)行交換，如果小于，則直接跳出去，此時(shí)則完成一次交換，end不斷向

前挪動(dòng)，不斷進(jìn)行比較，隨著i的變化，比較的位置也發(fā)生變化

????????代碼：

void InsertSort(int* a,int n)
{
	for (int i=1; i < n; i++)
	{
		int end = i-1;
		int temp = a[i];

		while (end >= 0)
		{
			if (a[end] > temp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;
	}
}

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

1. 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高

2. 時(shí)間復(fù)雜度：O(N^2)

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

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

????????希爾排序

? ? ? ? ? ? ? ? 圖片演示：

【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序

? ? ? ? ? ? ? ? 思路(升序)

? ? ? ? ? ? ? ? ? ? ? ? 我們對(duì)數(shù)組每隔gap個(gè)數(shù)字進(jìn)行比較一次，當(dāng)前數(shù)字與gap位后的數(shù)字進(jìn)行比較

如果當(dāng)前數(shù)字大于gap數(shù)之后的數(shù)，則將其進(jìn)行調(diào)換，如果沒(méi)有，則跳出循環(huán)，當(dāng)外層循環(huán)進(jìn)行

++操作時(shí)，則從第二個(gè)數(shù)字開始，與從第二個(gè)數(shù)字開始數(shù)gap位之后的數(shù)字，進(jìn)行比較，大于交

換，小于跳出循環(huán)，同時(shí)gap也在不斷發(fā)生變化，最后gap==1時(shí)，進(jìn)行最后的比較

????????

? ? ? ? ? ? ? ? 代碼：

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap>1)
	{
		gap =gap/ 2;
		for (int i = 0; i< n-gap;i++)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > temp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
}

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

????????1. 希爾排序是對(duì)直接插入排序的優(yōu)化。

????????2. 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比。

????????3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些樹中給出的希爾排序的時(shí)間復(fù)雜度都不固定

? ? ? ?

????????堆排序

?????????堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。它是通過(guò)堆來(lái)進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。

? ? ? ? ? ? ? ? 思路：

????????????????首先應(yīng)該建一個(gè)大堆，不能直接使用堆來(lái)實(shí)現(xiàn)?？梢詫⑿枰判虻臄?shù)組看作是一個(gè)堆，但需要將數(shù)組結(jié)構(gòu)變成堆我們可以從堆從下往上的第二行最右邊開始依次向下調(diào)整直到調(diào)整到堆頂，這樣就可以將數(shù)組調(diào)整成一個(gè)堆，且如果建立的是大堆，堆頂元素為最大值。然后按照堆刪的思想將堆頂和堆底的數(shù)據(jù)交換，但不同的是這里不刪除最后一個(gè)元素。這樣最大元素就在最后一個(gè)位置，然后從堆頂向下調(diào)整到倒數(shù)第二個(gè)元素，這樣次大的元素就在堆頂，重復(fù)上述步驟直到只剩堆頂時(shí)停止。
?

????????????????圖片演示：

【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序

???????

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

// 堆排序
void AdjustDown(int* a, int n, int root)//向下調(diào)整
{
	assert(a);
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
void HeapSort(int* a, int n)
{
	assert(a);
 
    //建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
 
    //交換
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[i], &a[0]);
		AdjustDown(a, i, 0);
	}
}

? ? ? ?

????????選擇排序

【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序

? ? ? ? 思路(升序)：

????????????????第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始(末尾)位置，然后選出次小(或次大)的一個(gè)元素，存放在最大(最小)元素的下一個(gè)位置，重復(fù)這樣的步驟直到全部待排序的數(shù)據(jù)元素排完。

? ? ? ?????????代碼：

void SelectSort(int* arr, int n)
{
	//保存參與單趟排序的第一個(gè)數(shù)和最后一個(gè)數(shù)的下標(biāo)
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		//保存最大值的下標(biāo)
		int maxi = begin;
		//保存最小值的下標(biāo)
		int mini = begin;
		//找出最大值和最小值的下標(biāo)
		for (int i = begin; i <= end; ++i)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		//最小值放在序列開頭
		Swap(&arr[mini], &arr[begin]);
		//防止最大的數(shù)在begin位置被換走
		if (begin == maxi)
		{
			maxi = mini;
		}
		//最大值放在序列結(jié)尾
		Swap(&arr[maxi], &arr[end]);
		++begin;
		--end;
	}
}

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

1. 直接選擇排序思考非常好理解，但是效率不是很好。實(shí)際中很少使用

2. 時(shí)間復(fù)雜度：O(N^2)

3. 空間復(fù)雜度：O(1)

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

????????

????????冒泡排序

? ? ? ? ? ? ? ? 算法思想:

? ? ? ? ? ? ? ? 從左到右依次進(jìn)行比較，升序時(shí)：如果左邊大于右邊則交換，從到到尾，全部進(jìn)行交

換，挑選出最大的元素，放到最后，這是一次單趟排序，再進(jìn)行循環(huán)選出第二大的，再循環(huán)選出第

三大的

【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序

? ? ? ? ? ? ? ? 代碼實(shí)現(xiàn)：

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

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

//冒泡實(shí)現(xiàn)
void BubbleSort(int* a,int n)
{
	for (int j =0; j<n; j++)
	{
		for (int i = 1; i < n-j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
			}
		}
	}

}

???????? 冒泡排序的特性總結(jié)：

?????? ??1. 冒泡排序是一種非常容易理解的排序

????????2. 時(shí)間復(fù)雜度：O(N^2)

????????3. 空間復(fù)雜度：O(1)

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

? ? ? ?

????????快速排序

? ? ? ? ? ? ? ? 1962年由Hoare提出的一種二叉樹結(jié)構(gòu)的交換排序的方法，其基本思想:任取待排序

元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中

所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過(guò)

程，直到所有元素都排列在相應(yīng)位置上為止。

? ? ? ? ? ? ? ? 選出一個(gè)關(guān)鍵值key，把他放到正確的位置,我們?cè)趯W(xué)習(xí)任何排序前，都應(yīng)該先弄明白單

趟排序，然后再清楚整體思想即可

?????????Hoare版本

? ? ? ? ? ? ? ? ? ? ? ? ?左邊做Key右邊先走，如果右邊做Key左邊先走，將小的往左邊換，把大的往右邊

????????換，到相遇位置，停下，此時(shí)左邊全是比中間位置小的，右邊全是比中間位置大的，相遇位

? ? ? ? 一定比Key小

【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序

? ? ? ? ? ? ? ? ?Hoare一次排序其實(shí)本質(zhì)是在排一個(gè)數(shù)據(jù)?????????????

void QuickSort(int* a,int left ,int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left, end = right;

	int keyi = left;
	while (left < right)
	{
		//右邊先走找小
		while (a[right] >= a[keyi] && left < right)
		{
			--right;
		}
		
		//左邊找大
		while (a[left] <= a[keyi] && left < right)
		{
			++left;
		}
		Swap(&a[left],&a[right]);
	}
	Swap(&a[keyi],&a[left]);
	QuickSort(a,begin,keyi-1);
	QuickSort(a,keyi+1,end);
}

??????? 注：但其有個(gè)致命特點(diǎn)，如果keyi在最左邊時(shí)，而數(shù)組為有序，這樣排序時(shí)，需要不斷

創(chuàng)建新的棧幀，其時(shí)間復(fù)雜度，直接為n*logn，我們可以將Keyi的位置進(jìn)行隨機(jī)排放

????????隨機(jī)選Keyi? ? ??

????????????????我們將keyi進(jìn)行隨機(jī)處理，就可以解決上面的問(wèn)題

void QuickSort(int* a, int left, int right)
{
	//  ... 返回條件
	if (left >= right)
	{
		return;
	}
	int begin = left, end = right;
	int randi = left + (rand() % (right - left));
	Swap(&a[left],&a[randi]);
	int keyi = left;
	while (left < right)
	{
		// 右邊找小
		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;

	// [begin, keyi-1] keyi [keyi+1, end] 
	// 遞歸
	QuickSort(a,begin,keyi-1);
	QuickSort(a,keyi+1,end);
}

????????三數(shù)取中

??????? ????????有序情況下，三數(shù)取中對(duì)時(shí)間復(fù)雜度的優(yōu)化，其極其明顯

void QuickSort(int* a, int left, int right)
{
	//  ... 返回條件
	if (left >= right)
	{
		return;
	}
	int begin = left, end = right;
	int midi = GetMidNumi(a,left,right);
	Swap(&a[midi],&a[left]);
	/*int randi = left + (rand() % (right - left));
	Swap(&a[left],&a[randi]);*/

	int keyi = left;
	while (left < right)
	{
		// 右邊找小
		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;

	// [begin, keyi-1] keyi [keyi+1, end] 
	// 遞歸
	QuickSort(a,begin,keyi-1);
	QuickSort(a,keyi+1,end);
}

????????挖坑法

【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序

????????

int QuickSort(int* a, int left, int right)
{
	//  ... 返回條件
	if (left >= right)
	{
		return;
	}
	int begin = left, end = right;
	int midi = GetMidNumi(a,left,right);
	if(midi != left)
		Swap(&a[midi],&a[left]);
	
	int key = a[left];
	int hole = key;
	while (left < right)
	{
		// 右邊找小
		while (left < right && a[right] >= key)
			--right;
		a[hole] = a[right];
		hole = right;

		// 左邊找大
		while (left < right && a[left] <= key)
			++left;
		a[hole] = a[left];
		hole = left;

	}
	a[hole] = key;

	// [begin, keyi-1] keyi [keyi+1, end] 
	// 遞歸
}
void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = QuickSort(a,left,right);
	QuickSort1(a,left,keyi-1);
	QuickSort1(a,keyi+1,right);
}

? ? ? ? 前后指針版本

? ? ? ? ????????1.cur找到比key小的值，++prev，cur和prev位置的值交換,++cur

? ? ? ? ? ? ? ? 2.cur找到比key大的值，++cur

? ? ? ? ? ? ? ? ?說(shuō)明

? ? ? ? ? ? ? ? ? ? ? ? 1.prev要么緊跟著cur

? ? ? ? ? ? ? ? ? ? ? ? ?2.prev跟cur中間間隔著比key大的一段值區(qū)間

【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序

??????? 思路：

??????? 通過(guò)創(chuàng)建兩個(gè)指針，prev指針指向數(shù)組序列首元素位置，cur指向prev的下一個(gè)位置，cur通過(guò)遍歷去尋找比key基準(zhǔn)值小的，若找到了，還得看prev的下一個(gè)位置是否為cur所處的位置，若prev的下一個(gè)位置確實(shí)為cur所處位置，則將cur指向的值與prev指向的值進(jìn)行互換，若prev的下一個(gè)位置不是cur所處位置，則cur繼續(xù)往后遍歷，直到cur遍歷結(jié)束，最后要將key基準(zhǔn)值與prev指向的值進(jìn)行互換，最終確認(rèn)基準(zhǔn)值處于數(shù)組序列的中間位置。

//交換函數(shù)
void Swap(int* p1, int* p2) {
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//三數(shù)取中
int GetMidIndex(int* arr, int left, int right) {
	int mid = (right - left) / 2 + left;
	if (arr[left] < arr[mid]) {
		if (arr[mid] < arr[right]) {
			return mid;
		}
		else if (arr[left] > arr[right]) {
			return left;
		}
		else {
			return right;
		}
	}
	else {			//arr[left]>=arr[mid]
		if (arr[mid] > arr[right]) {
			return mid;
		}
		else if (arr[left] < arr[right]) {
			return left;
		}
		else {
			return right;
		}
	}
}
 
//前后指針?lè)?int PartSort(int* arr, int left, int right) {
	int mid = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[mid]);
	int keyi = left;	//基準(zhǔn)值下標(biāo)放在最左側(cè)
	int prev = left;
	int cur = left + 1;
	while (cur<=right) {
		if (arr[cur] < arr[keyi] && ++prev != cur) {
			Swap(&arr[prev], &arr[cur]);
		}
		++cur;
	}
	Swap(&arr[keyi], &arr[prev]);	
	return prev;
}

????????歸并排序

【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序

????????

??????? 思路：

????????從下往上的歸并排序：將待排序的數(shù)列分成若干個(gè)長(zhǎng)度為1的子數(shù)列，然后將這些數(shù)列兩兩合并；得到若干個(gè)長(zhǎng)度為2的有序數(shù)列，再將這些數(shù)列兩兩合并；得到若干個(gè)長(zhǎng)度為4的有序數(shù)列，再將它們兩兩合并；直接合并成一個(gè)數(shù)列為止，從上往下的歸并排序：它與"從下往上"在排序上是反方向的。

?????代碼:??

????????

//輔助歸并排序遞歸的子函數(shù)
void _MergeSort(int* a, int* tmp, int begin, int end)
{
	if (begin >= end)
		return;//單個(gè)或者不存在其區(qū)間就結(jié)束遞歸
 
	//類似于后序：
	int middle = (begin + end) / 2;
	int begin1 = begin;
	int end1 = middle;
	int begin2 = middle + 1;
	int end2 = end;
	_MergeSort(a, tmp, begin1, end1);
	_MergeSort(a, tmp, begin2, end2);
 
	//此時(shí)認(rèn)為 [begin1, end1] 和 [begin2, end2]兩段區(qū)間上有序
	//歸并算法
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
 
}
 
//歸并排序 遞歸版本
void MergeSort(int* a, int n)
{
	//首先malloc一個(gè)數(shù)組
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("未能申請(qǐng)到內(nèi)存\n");
		exit(-1);
	}
	//第一次傳入 0 和 n - 1 傳入閉區(qū)間
	_MergeSort(a, tmp, 0, n - 1);
	free(tmp);
}

文末送書:

????????

【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序

?書籍推薦:

????????算法不是一行行神秘的代碼，而是你我都應(yīng)具備的一種思維模式。在計(jì)算機(jī)出現(xiàn)之前，算法就已經(jīng)存在了。了解經(jīng)典算法的起源，不僅是因?yàn)槲覀兩硖幮畔r(shí)代，更是因?yàn)樗惴ǖ牡讓舆壿嫼蛻?yīng)用可以為我們的工作、生活提供解決問(wèn)題的新思路
?
????????本書從最基礎(chǔ)的“什么是算法”開始討論，首先介紹如何評(píng)價(jià)算法的性能，然后展開討論與圖、搜索和排序相關(guān)的經(jīng)典算法，解釋“算法是怎么運(yùn)作的”，最后介紹PageRank和深度學(xué)習(xí)兩個(gè)大型算法應(yīng)用。本書用通俗易懂的語(yǔ)言來(lái)描繪算法世界，穿插有趣的文化歷史故事和簡(jiǎn)單易懂的例子，不涉及艱深的數(shù)學(xué)知識(shí)，即使非專業(yè)人士也能輕松讀懂。

作者簡(jiǎn)介:

??????? 帕諾斯·盧里達(dá)斯（Panos Louridas）

????????曼徹斯特大學(xué)軟件工程博士，現(xiàn)為雅典經(jīng)濟(jì)與商業(yè)大學(xué)管理科學(xué)與技術(shù)系副教授，研究興趣包括算法應(yīng)用、軟件工程、安全和實(shí)用密碼學(xué)等。著有《真實(shí)世界的算法：初學(xué)者指南》。在加入高校之前，他曾在投資銀行擔(dān)任高級(jí)軟件工程師。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-473231.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】帶你玩轉(zhuǎn)排序：堆排序、希爾排序、插入排序、選擇排序、冒泡排序、快排(多版本)、歸并排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！