本篇文章介紹數(shù)據(jù)結(jié)構(gòu)中的幾種排序哦~

前言

? 排序在我們的生活當(dāng)中無處不在，當(dāng)然，它在計(jì)算機(jī)程序當(dāng)中也是一種很重要的操作，排序的主要目的是為了便于查找。

一、排序是什么？

所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的一種擦作。

二、排序的分類

框架圖：

這里呢我們就介紹幾種比較重要的排序算法。?

1.直接插入排序

撲克牌是我們幾乎每個(gè)人都可能玩過的游戲吧，最基本的撲克玩法大多都是一邊摸牌，一邊理牌的。

這里先看個(gè)動(dòng)圖吧，你是否看完動(dòng)圖就已經(jīng)知道這種排序方式的思路了呢？

動(dòng)態(tài)圖演示：

思路：

?直接插入排序的思路呢就是每次將一個(gè)等待排序的元素與已經(jīng)排序的元素進(jìn)行一一比較，直到找到合適的位置按大小插入。它的基本操作就是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而得到一個(gè)新的，記錄數(shù)增1的有序表。

代碼如下：

//插入排序
#include<stdio.h>

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

//測(cè)試
void TestInsertSort()
{
	int a[] = { 9,1,5,7,4,8,3 };
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}
void TestOP()
{
	srand(time(0));
	const int N = 10000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	for (int i = N - 1;i >= 0;--i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
    printf("InsertSort:%d\n", end1 - begin1);
    free(a1);
	free(a2);
}
int main()
{
	TestOP();
    TestInsertSort();
	return 0;
}

執(zhí)行結(jié)果：

2.希爾排序（縮小增量排序）

首先，給大家說明一下，希爾排序是D.L.Shell于1959年提出來的一種排序算法，在這之前呢，排序算法的時(shí)間復(fù)雜度大多基本都是O(n^2)的，而希爾排序算法可以說是突破這個(gè)時(shí)間復(fù)雜度的第一批算法之一了，換句話說，希爾排序算法的發(fā)明，使得我們終于突破了慢速排序的時(shí)代。之后，更為高效的排序算法也就相繼出現(xiàn)了。

有條件了很好，沒條件我們?nèi)?chuàng)造條件也是可以去做的，那么，在科學(xué)家希爾對(duì)直接插入排序進(jìn)行打磨之后就可以增加效率了。一個(gè)問題的解決務(wù)必是因?yàn)樵搯栴}的誕生，那如何讓待排序的記錄個(gè)數(shù)變少呢？分割成若干個(gè)子序列，此時(shí)每個(gè)序列待排序的記錄個(gè)數(shù)就比較少了，接著在這些子序列內(nèi)分別進(jìn)行直接插入排序，當(dāng)整個(gè)序列都基本有序時(shí)，這里可要注意啦，是基本有序時(shí)，再次對(duì)全體記錄進(jìn)行一次直接插入排序。

強(qiáng)調(diào)一下：這里的基本有序指的是小的關(guān)鍵字基本在前邊，大的關(guān)鍵字基本在后邊，不大不小的基本在中間。就和我們高中跑早操排隊(duì)一樣嘛，但是偶爾會(huì)出現(xiàn)一兩對(duì)身高不太一樣的好朋友往一塊站對(duì)嘛。

可是這里分割待排序記錄的目的是減少待排序記錄的個(gè)數(shù)，并且使整個(gè)序列向基本有序發(fā)展·，不過按照這樣的方式好像并不能滿足我們讓分完組后就各自排序的這種要求哦，所以，我們需要采取的措施是：將相距某個(gè)“增量”的記錄組成一個(gè)子序列，這樣的話才能夠保證在子序列內(nèi)部分別進(jìn)行直接插入排序后得到的結(jié)果是基本有序而不是局部有序的。

?總結(jié)：希爾排序的基本思想就是：先選定一個(gè)整數(shù)，把待排序文件中所有記錄分成gap組，所有距離為gap的記錄在同一組內(nèi)，并且對(duì)每一組內(nèi)的記錄進(jìn)行排序。然后，重復(fù)上述分組和排序的工作。當(dāng)達(dá)到gap = 1時(shí)，所有記錄在同一組內(nèi)排好序。

代碼如下：

//希爾排序
void PrintArray(int* a, int n)
{
	for (int i = 0;i < n;i++)
	{
		printf("%d", a[i]);
	}
	printf("\n");
}

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
//測(cè)試
void TestShellSort()
{
	int a[] = { 9,1,5,7,4,8,3 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}
void TestOP()
{
	srand(time(0));
	const int N = 10000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	for (int i = N - 1;i >= 0;--i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}
	int begin1 = clock();
	ShellSort(a1, N);
	int end1 = clock();

	printf("ShellSort:%d\n", end1 - begin1);

	free(a1);
	free(a2);
}
int main()
{
	TestOP();
	TestShellSort();

	return 0;
}

執(zhí)行結(jié)果;

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

（1）當(dāng)gap > 1時(shí)其實(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。

? ? ? ? ?當(dāng)gap == 1 時(shí)，其實(shí)就是直接插入排序，數(shù)組已經(jīng)接近有序了，這樣就會(huì)很快。就整體而言，可以達(dá)到優(yōu)化的效果。

（2）希爾排序的時(shí)間復(fù)雜度不是很好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算。

說明：gap的取法有很多種，Shell提出取 gap = n / 2, gap = gap / 2,直到gap為1；

? ? ? ? ? 后來，Knuth提出取gap = (gap / 3) + 1。

無論哪一種，都沒有得到證明！ ！ ！

注：在Knuth所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第三卷中，利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出，當(dāng)n很大時(shí)，關(guān)鍵碼平均比較次數(shù)和對(duì)象平均移動(dòng)次數(shù)在n^1.25~1.6*n^1.25范圍內(nèi)，這是在利用直接插入排序作為子序列排序方法的情況下得到的。?

?3.選擇排序

動(dòng)態(tài)圖演示：

看完圖有沒有思路呢？其實(shí)選擇排序的思路蠻簡(jiǎn)單的，就是每一次從待排序的數(shù)據(jù)元素中選出最小/最大的一個(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。這種排序也就是通過n-i次關(guān)鍵字間的比較，從n - i + 1個(gè)記錄中選出關(guān)鍵字最小的記錄，并且和第 i (1 <= i <= n)個(gè)記錄交換。

代碼如下：

 //選擇排序
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;

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

			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		if (maxi == begin)
		{
			maxi = mini;
		}

		Swap(&a[end], &a[maxi]);

		++begin;
		--end;
	}
}

//測(cè)試
void TestSelectSort()
{
	int a[] = { 9,1,5,7,4,8,3 };
	SelectSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestOP()
{
	srand(time(0));
	const int N = 100;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	for (int i = N - 1; i >= 0; --i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}
	int begin1 = clock();
	SelectSort(a1, N);
	int end1 = clock();

	printf("SelectSort:%d\n", end1 - begin1);

	free(a1);
	free(a2);
}
int main()
{
	TestOP();
	TestSelectSort();

	return 0;
}

執(zhí)行結(jié)果：

?從選擇排序的過程來看，它最大的特點(diǎn)就是交換移動(dòng)數(shù)據(jù)次數(shù)相對(duì)較少，這樣也就節(jié)約了相應(yīng)的時(shí)間。

總結(jié)：選擇排序它的思路很好理解，但是其效率并不是很好，很少用到。

4.冒泡排序

無論你學(xué)習(xí)哪種編程語言，在學(xué)到循環(huán)和數(shù)組的時(shí)候，通常都會(huì)介紹一種排序算法，而這個(gè)算法一般就是冒泡排序。并不是說它的名字好聽，而是說這個(gè)算法的思路最簡(jiǎn)單，最容易理解哦。

冒泡排序呢我們可以理解為一種交換排序，其基本思想是：對(duì)數(shù)組進(jìn)行遍歷，每次對(duì)相鄰兩個(gè)進(jìn)行比較大小，如果大的數(shù)值在前面，那么交換位置也可以理解為升序，完成一趟遍歷后數(shù)組中最大的數(shù)值到了數(shù)組的末尾位置，再對(duì)前面n-1個(gè)數(shù)值進(jìn)行相同的遍歷，一共完成n-1次遍歷就實(shí)現(xiàn)了排序完成。

動(dòng)態(tài)圖演示：

代碼如下：

//冒泡排序
void PrintArray(int* a, int n)
{
	for (int i = 0;i < n;i++)
	{
		printf("%d", a[i]);
	}
	printf("\n");
}
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		int exchange = 0;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}

		if (exchange == 0)
		{
			break;
		}
	}
}

//測(cè)試
void TestBubbleSort()
{
	int a[] = { 9,1,5,7,4,8,3 };
	BubbleSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}
void TestOP()
{
	srand(time(0));
	const int N = 100;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	for (int i = N - 1; i >= 0; --i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}
	int begin1 = clock();
	BubbleSort(a1, N);
	int end1 = clock();

	printf("BubbleSort:%d\n", end1 - begin1);

	free(a1);
	free(a2);
}
int main()
{
	TestOP();
	TestBubbleSort();

	return 0;
}

執(zhí)行結(jié)果：

在這里呢簡(jiǎn)單提一下冒泡排序的效率，冒泡排序是穩(wěn)定的排序算法，在相同數(shù)據(jù)排序時(shí)不會(huì)影響原來的順序，對(duì)結(jié)構(gòu)體類型有影響的。它的時(shí)間復(fù)雜度是O(n^2),空間復(fù)雜度是O(1)。?

?5.快速排序

? 終于，我們的高手就要出場(chǎng)啦！假如說未來你在工作后，你的老板讓你寫個(gè)排序算法，而你會(huì)的算法中竟然沒有快速排序，那么我建議你還是火速把快速排序算法找來敲入你排序算法的大隊(duì)伍中吧，哈哈哈哈……

? ?簡(jiǎn)單介紹一下快速排序吧，快速排序算法最早是由圖靈獎(jiǎng)獲得者Tony Hoare設(shè)計(jì)出來的。他在形式化方法理論以及ALGOL60編程語言的發(fā)明中都有卓越的貢獻(xiàn)，是上世紀(jì)最偉大的計(jì)算機(jī)科學(xué)家之一。而這快速排序算法只是他眾多貢獻(xiàn)中小小的一個(gè)發(fā)明而已。你們知道嗎，我們接下來要學(xué)習(xí)的這個(gè)快速排序算法可是被列為20世紀(jì)十大算法之一的哦~

?這段話大家好好看看哦~

希爾排序可以說是直接插入排序的升級(jí)，都屬于插入排序這一大類哦；

快速排序可以說是冒泡排序的升級(jí)，都屬于交換排序這一大類哦。也就是通過不斷比較和移動(dòng)交換來實(shí)現(xiàn)排序，不過它的實(shí)現(xiàn)相較其他而言，就是增大了記錄的比較和移動(dòng)的距離，將關(guān)鍵字大的記錄從前面直接移動(dòng)到后面去，關(guān)鍵字較小的記錄從后面直接移動(dòng)到前面，從而減少了總的比較次數(shù)和移動(dòng)交換次數(shù)。

? 基本思想：任取待排序元素序列中的某個(gè)元素作為基準(zhǔn)值，按照該排序碼將待排序碼集合分割成兩個(gè)子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。

在這里呢，我們主要對(duì)hoare排序以及對(duì)其的幾種優(yōu)化進(jìn)行介紹：

（1）hoare版本

hoare版本是快速排序最原始的情況，（看看單趟的過程）

這里單趟的目的是：要求左邊的key要小，右邊的key要大

動(dòng)態(tài)圖演示：

看完圖，是否稍微有一點(diǎn)點(diǎn)思路呢？因?yàn)榭焖倥判蛟谂判蛑泻苤匾赃@里可能會(huì)說的詳細(xì)一點(diǎn)，大家不要嫌我啰嗦哦~

思路:

a:先記錄下keyi的位置，接著 left 和 right 分別從數(shù)組兩端開始往中間走；

b:當(dāng)right先開始向中間行動(dòng)，如果right處的值小于keyi處所對(duì)應(yīng)的值，則停止等待left走；

c:此時(shí)left開始行動(dòng)，當(dāng)left找到比keyi處小的值的時(shí)候，left 和 right處的值進(jìn)行交換；

d:當(dāng)兩個(gè)位置相遇時(shí)，將兩個(gè)相遇位置的值與keyi處所對(duì)應(yīng)的值進(jìn)行交換，并且將相遇的位置記為新的keyi；

?代碼如下：

//這里出現(xiàn)了一種三數(shù)取中的方法，這樣的話快速排序就不會(huì)出現(xiàn)最壞情況
// 三數(shù)取中

void PrintArray(int* a, int n)
{
	for (int i = 0;i < n;i++)
	{
		printf("%d", a[i]);
	}
	printf("\n");
}
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	// left mid right
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])  // mid是最大值
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right]) // mid是最小
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

//快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
	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]);
	return left;
};
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	if ((right - left + 1) > 10)
	{
		int keyi = PartSort1(a, left, right);

		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
	else
	{
		InsertSort(a + left, right - left + 1);
	}
}

執(zhí)行結(jié)果：

（2）挖坑法版本

動(dòng)態(tài)圖演示：

看完圖，有什么想法嗎，或許有些同學(xué)對(duì)快速排序的第一個(gè)原始版本中，左邊設(shè)置為keyi之后，右邊就要先走是不太能理解的吧，這里就有腦洞大開的大佬想出了另外一種快速排序的方法，可能思路不太一樣，不過相比而言，對(duì)我們這些小白來說更容易理解哦~?

思路：

a:首先將begin處的值放到key中，然后將其設(shè)置為坑位，接著right抗下任務(wù)開始行動(dòng)找值從而補(bǔ)坑；

b:right找到比key小的值后將這個(gè)值放到剛才的坑位中，然后將這個(gè)新的位置重新設(shè)置為坑位；

c:此時(shí)left也開始找值來進(jìn)行補(bǔ)坑啦，找到比key大的值，然后將這個(gè)值放到坑位中，接著將這個(gè)新的位置重新設(shè)置為坑位；

d:當(dāng)left與right碰面時(shí)，再將key放入到坑位中；

代碼如下：

//三數(shù)取中那一部分在前面哦！
//挖坑法

int PartSort2(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	// 保存key值以后，左邊形成第一個(gè)坑
	int hole = left;

	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;
	return hole；
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort2(a, begin, end);
	// [begin, keyi-1] keyi [keyi+1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

?執(zhí)行結(jié)果：

（3）前后指針法版本

動(dòng)態(tài)圖演示：

這里呢，前后指針法與前面兩種版本相比的話，無論是從哪個(gè)方面考慮都是有很大的提升的，也是一種很常見的寫法。

思路：

a:cur位于begin+1的位置，prev位于begin的位置，keyi先存放begin處的值；

b:cur不斷往前+1，直到cur大于等于end時(shí)停止循環(huán)；

c:如果cur處的值小于key處的值，而且prev+1不等于cur，那么與prev處的值進(jìn)行交換；

d:當(dāng)循環(huán)結(jié)束時(shí)，將prev處的值與keyi處的值進(jìn)行交換，而且將其置為新的keyi值?

?代碼如下：

 //前后指針
int PartSort3(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int prev = left;
	int cur = prev + 1;

	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	return prev;
}

// [begin, end]
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort3(a, begin, end);
	// [begin, keyi-1] keyi [keyi+1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

執(zhí)行結(jié)果：

說明：

? 這里，在遍歷的整個(gè)過程中，cur是不斷向前的，只是cur處的值小于keyi處的值時(shí)才進(jìn)行交換，使其進(jìn)行判斷；在cur位置處的值小于keyi處的值時(shí)，需要進(jìn)行判斷prev++是否等于cur，如果等于的話，則會(huì)出現(xiàn)自己交換自己的情形，當(dāng)然，如果相等的話不用進(jìn)行交換哦~?

//這是上面三種情況的測(cè)試代碼
void TestQuickSort()
{
	int a[] = { 9,1,5,7,4,8,3 };
	QuickSort(a,0, sizeof(a) / sizeof(int)-1);
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestOP()
{
	srand((unsigned)time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	for (int i = N - 1; i >= 0; --i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}
	int begin1 = clock();
	QuickSort(a1, 0, N-1);
	int end1 = clock();

	printf("QuickSort:%d\n", end1 - begin1);

	free(a1);
	free(a2);
}
int main()
{
	TestOP();
	TestQuickSort();

	return 0;
}

6.歸并排序

? 歸并排序，歸并歸并，從字面意思來看，我們就可以有著把兩個(gè)合并到一起的感覺。在數(shù)據(jù)結(jié)構(gòu)中的定義呢是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。

? 我想問一下大家知道我們高考完那個(gè)所謂的一本，二本，還有?？凭€是怎么劃分出來的嗎，簡(jiǎn)而言之，假設(shè)各個(gè)高校的本科專業(yè)要在甘肅省高三學(xué)理科的學(xué)生中打算招收一萬名學(xué)生，那么將全省參加高考的理科生進(jìn)行一個(gè)倒排序，那么，這位排名在一萬名的這位幸運(yùn)同學(xué)的分?jǐn)?shù)就會(huì)是本科線。換個(gè)思路想，如果你是年級(jí)第一，但你的分?jǐn)?shù)沒有高于這個(gè)分?jǐn)?shù)線，那么很遺憾，你也就失去了上本科的機(jī)會(huì)。換言之，所謂的排名，其實(shí)也就是這個(gè)省份中的每個(gè)市一直到每個(gè)縣城的每個(gè)學(xué)校的每個(gè)班級(jí)的排名合并之后，從而得到的。

為了讓大家更清楚的理解思路，這里給大家看個(gè)動(dòng)態(tài)圖吧~

動(dòng)態(tài)圖演示：

看完動(dòng)態(tài)圖，有沒有稍微理解一點(diǎn)呢，話說回來，這就是我們要說的歸并排序。?

歸并排序用到了分治的思想，借助遞歸的方式對(duì)一串?dāng)?shù)字進(jìn)行排序，整個(gè)過程分為分開和合并這兩個(gè)過程，其實(shí)，這里的思想也沒有那么難理解，就是在代碼實(shí)現(xiàn)的過程中我們需要寫兩個(gè)函數(shù)分別實(shí)現(xiàn)分開合并以及每一次排序的這個(gè)過程。

通過上面的動(dòng)圖演示，我們不難發(fā)現(xiàn)，首先是要將整個(gè)待排序的數(shù)逐步分成小塊，然后再進(jìn)行歸并。

思路：

? 歸并排序的思路就是對(duì)于左右子區(qū)間都有序的序列，通過借助一個(gè)臨時(shí)數(shù)組進(jìn)行歸并。

然后定義兩個(gè)指針begin1和begin2，分別指向兩個(gè)子區(qū)間的頭部，另外定義兩個(gè)指針end1和end2,分別指向兩個(gè)子區(qū)間的尾部。然后依次挨個(gè)比較begin1和begin2指向的值，將小的放入下面的臨時(shí)數(shù)組中，直到其中的一個(gè)區(qū)間遍歷完成后，我們就停下來，然后接著將沒有走完的那個(gè)區(qū)間剩下的值直接拷貝給新數(shù)組。

看到這的時(shí)候，我們應(yīng)該能知道，當(dāng)區(qū)間里只有1個(gè)數(shù)的時(shí)候，那么我們就可以理解為有序了，也就是可以進(jìn)行歸并操作了。所以，當(dāng)左右這兩個(gè)子區(qū)間都沒有序的時(shí)候，我們就分治遞歸，不斷的分割區(qū)間，直到區(qū)間分割到只剩下1個(gè)數(shù)的時(shí)候，此時(shí)，我們就進(jìn)行歸并啦~?

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

//sort.c
#include"Sort.h"
#include"Stack.h"
#include<stdlib.h>

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

 歸并排序遞歸實(shí)現(xiàn)
void _MergeSort(int* a, int* tmp, int begin, int end)
{
	if (end <= begin)
		return;

	int mid = (end + begin) / 2;

	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid + 1, end);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int index = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}

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

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

	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	_MergeSort(a, tmp, 0, n - 1);
	free(tmp);
}

? 我們常說，沒有最好，只有更好。雖然說歸并排序大量引用了遞歸，盡管在代碼上是比較清晰的，可以使我們?nèi)菀桌斫?，但是這會(huì)造成時(shí)間和空間上的性能損耗，我們排序追求的不就是效率嗎，有沒有可能將遞歸轉(zhuǎn)化為迭代呢？當(dāng)然可以，而且改進(jìn)之后，性能上可是進(jìn)一步提高了哦~

前面提到的是歸并排序的遞歸思想，那接下來就說一下歸并排序的非遞歸是怎么樣的。

思路：

a:申請(qǐng)空間，使它的大小為兩個(gè)已經(jīng)排序的序列的和，然后該空間用來存放合并后的序列；

b：設(shè)定兩個(gè)指針，最開始的兩個(gè)位置分別為兩個(gè)已經(jīng)排序的序列的起始位置；

c:比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并的空間中，并且移動(dòng)指針到下一個(gè)位置；

d:對(duì)上一步的步驟進(jìn)行重復(fù)，直到某一指針超出序列尾部將另一個(gè)序列剩下的所有元素怒直接復(fù)制到合并的序列尾部。

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

//sort.c
void TestMergeNonRSort()
{
	int a[] = { 9,1,2,5,7,4,3,9,3,1,2 };
    MergeSortNonR(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestOP()
{
	srand(time(0));
	const int N = 10000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);

	for (int i = N - 1; i >= 0; --i)
	{
		a1[i] = rand() + i;
		a2[i] = a1[i];
	}

	int begin1 = clock();
	MergeSortNonR(a1, N);
	int end1 = clock();

	printf("MergeSortNonR:%d\n", end1 - begin1);

	free(a1);
	free(a2);
}

int main()
{
	//TestOP();
	TestMergeNonRSort();

	return 0;
}

? ?說明：非遞歸的方法，雖然說不是很好理解，也有點(diǎn)難，但是其避免了遞歸時(shí)深度為log2n的棧空間，并且避免遞歸也在時(shí)間性能上有一定的提升，可以說，使用歸并排序時(shí)，盡可能考慮用非遞歸的方法。?

7.計(jì)數(shù)排序

這里要說的計(jì)數(shù)排序呢，它的原理就是通過遍歷數(shù)組，記錄每一個(gè)數(shù)字出現(xiàn)的次數(shù)，最終在新數(shù)組中體現(xiàn)出來，那么是如何實(shí)現(xiàn)的呢？

思路：

a:首先我們先遍歷整個(gè)數(shù)組，找到數(shù)組中數(shù)值最大的數(shù)字max,并且申請(qǐng)max+1個(gè)桶（隨便起的名字哈）來存儲(chǔ)每個(gè)數(shù)字出現(xiàn)的次數(shù)，此時(shí)用下表記錄；

b:然后我們遍歷原來的數(shù)組，找到每個(gè)數(shù)字對(duì)應(yīng)的桶號(hào)，并且計(jì)數(shù)；

c:遍歷桶數(shù)組，看對(duì)應(yīng)的桶內(nèi)計(jì)數(shù)是多少，那么就取出幾個(gè)下標(biāo)值，放到原數(shù)組中。

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

//sort.c
//計(jì)數(shù)排序
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
		int range = max - min + 1;
		int* count = (int*)malloc(sizeof(int) * range);
		printf("range:%d\n",range);
		if (count == NULL)
		{
			perror("malloc fail");
			return;
		}
		memset(count, 0, sizeof(int) * range);

		for (int i = 0; i < n; i++)
		{
			count[a[i] - min]++;
		}
		//排序
		int j = 0;
		for (int i = 0;i < range;i++)
		{
			while (count[i]--)
			{
				a[j++] = i + min;
			}
		}
}

運(yùn)行結(jié)果和前面的一樣，就不貼出來啦，大家主要要體會(huì)每種排序的精髓在哪，完全理解它的思路，要領(lǐng)，核心還有它之所以叫這個(gè)排序，是為什么，到底哪里和其他的排序方式有差別，我想，如果大家報(bào)著這個(gè)態(tài)度去學(xué)習(xí)每一種排序，那數(shù)據(jù)結(jié)構(gòu)中的幾種排序不得被你狠狠拿捏了……

總結(jié)

這里呢，就對(duì)幾種排序的時(shí)間復(fù)雜度，空間復(fù)雜度進(jìn)行一個(gè)簡(jiǎn)單的總結(jié)哦~

圖片貼到這里啦，大家格外要理解穩(wěn)定性不穩(wěn)的幾種排序的理由哦~

好啦，關(guān)于數(shù)據(jù)結(jié)構(gòu)中幾種常見排序就先介紹到這里啦，如果哪里出錯(cuò)了，歡迎大家留言和我一起進(jìn)步嘞。文章來源地址http://www.zghlxwxcb.cn/news/detail-718296.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)---排序】很詳細(xì)的哦的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！