??博主CSDN主頁:杭電碼農(nóng)-NEO??
?
?專欄分類:八大排序?qū)?
?
??代碼倉庫:NEO的學(xué)習(xí)日記??
?
??關(guān)注我??帶你學(xué)習(xí)排序知識(shí)
? ????

1. 前言

比較八大排序不能直接將
這八個(gè)排序放在一起討論
我們根據(jù)大致效率將它們分為兩組:
(每個(gè)排序的詳情鏈接在后面)

1. 第一組

• 插入排序 詳情
• 選擇排序 詳情
• 冒泡排序 (略)

2. 第二組

• 堆排序 詳情
• 希爾排序 詳情
• 快速排序 詳情
• 歸并排序 詳情

各大排序的進(jìn)階版本被放在了專欄:
? ? 八大排序?qū)?/p>

本篇文章將從穩(wěn)定性和效率兩個(gè)方面
來分析這兩組排序

2. 什么是排序算法的穩(wěn)定性?

官方話語是這樣的:

排序序列中,有多個(gè)具有相同關(guān)鍵字的記錄經(jīng)過排序,記錄對(duì)應(yīng)的相對(duì)次序保持不變,這就是排序的穩(wěn)定性。

舉個(gè)例子,定義一個(gè)無序數(shù)組:

int a[]={5(i),3,6,4,5(j),2,8};

數(shù)組中有兩個(gè)5
把第一個(gè)5記為 i
第二個(gè)5記為 j
當(dāng)我們用任意算法排好序后

int a[]={2,3,4,5,5,6,8};//排好序后的數(shù)組

若 i 還在 j 前面,則這個(gè)算法是穩(wěn)定的

int a[]={2,3,4,i,j,6,8};

若 i 在 j 后面,則算法不穩(wěn)定

int a[]={2,3,4,j,i,6,8};

3. 各大排序穩(wěn)定性分析

想要搞清楚排序是否穩(wěn)定
就要明白內(nèi)部的實(shí)現(xiàn)思路!

3.1 插入和希爾排序的分析

1. 插入排序:

插入排序是從數(shù)組中第一個(gè)元素開始
一一和它后面的元素做比較
并且一個(gè)元素向前挪動(dòng)停下來的條件是:
當(dāng)前元素的值大于等于正在挪動(dòng)的元素

結(jié)論: 是穩(wěn)定的

2. 希爾排序:

雖然希爾排序是對(duì)插入排序的優(yōu)化
但是希爾排序多了一個(gè)分組預(yù)排序
當(dāng)相同的數(shù)組被分到同一組時(shí)
它們的順序不會(huì)變化
但是當(dāng)相同的數(shù)據(jù)分到不同組時(shí)
排好序后的順序就有可能改變!

結(jié)論: 不是穩(wěn)定的

3.2 選擇,堆排序的分析

1. 選擇排序:

選擇排序明顯是不穩(wěn)定的
當(dāng)前循環(huán)選出的最大值是
這個(gè)值第一次出現(xiàn)的位置
將它放在數(shù)組最后,第二層循環(huán)
尋找次大值時(shí)若和剛剛的值相同
這個(gè)次打值就到倒數(shù)第二個(gè)位置了

結(jié)論: 不穩(wěn)定的

2. 堆排序:

堆排序和選擇排序類似
我們直接舉個(gè)向下調(diào)整的例子:

藍(lán)色的5從第一個(gè)位置跑到最后一個(gè)了

結(jié)論: 不穩(wěn)定的

3.3 冒泡,快速排序的分析

1. 冒泡排序:

冒泡排序是挨個(gè)兒比較
挨個(gè)兒交換.所以不會(huì)將相同的值
交換到不同的位置

結(jié)論: 穩(wěn)定的

2. 快速排序

快速排序比較特殊.
當(dāng)基準(zhǔn)值key和L,R指針相遇的點(diǎn)
對(duì)應(yīng)的值相同時(shí),會(huì)改變位置!
畫圖說明:

5的前后順序發(fā)生了變化

結(jié)論: 不穩(wěn)定的

3.4 歸并排序分析

歸并排序可以穩(wěn)定也可以不穩(wěn)定
當(dāng)左右子數(shù)組中出現(xiàn)相同值時(shí)
如果先將左子數(shù)組的數(shù)據(jù)入數(shù)組
那么歸并排序就是穩(wěn)定的
如果先將右子數(shù)組的數(shù)據(jù)入數(shù)組
那么歸并排序就是不穩(wěn)定的

所以我們寫歸并排序時(shí)
數(shù)據(jù)相同時(shí)盡量先下左邊

結(jié)論: 穩(wěn)定的!

4. 各大算法效率比較

現(xiàn)實(shí)生活中處理的信息量往往非常大
這里我們隨機(jī)生成五百萬個(gè)數(shù)排序
試一試每一個(gè)排序算法要花多少毫秒?

注:clock是記錄程序
走到當(dāng)前這一行運(yùn)行的時(shí)長(zhǎng)
兩個(gè)clock相減就是中間程序運(yùn)行的時(shí)間

//測(cè)試性能
void TestOP()
{
	srand(time(0));
	const int N = 5000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a2, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a2, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a2, 0, N - 1);
	QuickSort(a2, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a2, N);
	int end6 = clock();

	printf("InsertSort:%d ms\n", end1 - begin1);
	printf("ShellSort:%d ms\n", end2 - begin2);
	printf("SelectSort:%d ms\n", end3 - begin3);
	printf("HeapSort:%d ms\n", end4 - begin4);
	printf("QuickSort:%d ms\n", end5 - begin5);
	printf("MergeSort:%d ms\n", end6 - begin6);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

對(duì)于五百萬個(gè)數(shù)據(jù)來說
插入,選擇,冒泡排序運(yùn)行的時(shí)間會(huì)很長(zhǎng)
所以我們這里直接比較第二組排序:

五百萬個(gè)數(shù)據(jù):

一百萬個(gè)數(shù)據(jù):

每個(gè)排序效率都不錯(cuò)
快排與歸并格外的好!

5. 總結(jié)與代碼分享

八大排序整體完結(jié)!
下面分享一個(gè)知識(shí)表格大全:

我將C語言實(shí)現(xiàn)八大排序
所有代碼匯總分享給大家:

gitee代碼倉庫

八大排序所有內(nèi)容結(jié)束!
文章來源地址http://www.zghlxwxcb.cn/news/detail-502770.html

到了這里，關(guān)于【八大排序(十)】八大排序效率與穩(wěn)定性分析的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！