當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

排序八种经典排序算法

發(fā)布時(shí)間：2023/12/20 编程问答 22 豆豆

生活随笔收集整理的這篇文章主要介紹了排序八种经典排序算法小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

排序(Sorting) 是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素(或記錄)的任意序列，重新排列成一個(gè)關(guān)鍵字有序的序列。
我整理了以前自己所寫的一些排序算法結(jié)合網(wǎng)上的一些資料，共介紹8種常用的排序算法，希望對大家能有所幫助。

八種排序算法分別是：
1.冒泡排序；
2.選擇排序；
3.插入排序；
4.快速排序；
5.歸并排序；
6.希爾排序；
7.二叉排序；
8.計(jì)數(shù)排序；

其中快排尤為重要，幾乎可以說IT開發(fā)類面試必考內(nèi)容，而希爾排序和歸并排序的思想也非常重要。下面將各個(gè)排序算法的排序原理，代碼實(shí)現(xiàn)和時(shí)間復(fù)雜度一一介紹。

—，最基礎(chǔ)的排序——冒泡排序
冒泡排序是許多人最早接觸的排序算法，由于邏輯簡單，所以大量的出現(xiàn)在計(jì)算機(jī)基礎(chǔ)課本上，作為一種最基本的排序算法被大家所熟知。

設(shè)無序數(shù)組a[]長度為N，以由小到大排序?yàn)槔Ｃ芭莸脑硎沁@樣的：
1.比較相鄰的前兩個(gè)數(shù)據(jù)，如果前面的數(shù)據(jù)a[0]大于后面的數(shù)據(jù)a[1] (為了穩(wěn)定性，等于不交換)，就將前面兩個(gè)數(shù)據(jù)進(jìn)行交換。在將計(jì)數(shù)器 i ++;
2.當(dāng)遍歷完N個(gè)數(shù)據(jù)一遍后，最大的數(shù)據(jù)就會沉底在數(shù)組最后a[N-1]。
3.然后N=N-1；再次進(jìn)行遍歷排序?qū)⒌诙蟮臄?shù)據(jù)沉到倒數(shù)第二位置上a[N-2]。再次重復(fù)，直到N=0；將所有數(shù)據(jù)排列完畢。

無序數(shù)組： 2 5 4 7 1 6 8 3 遍歷1次后： 2 4 5 1 6 7 3 8 遍歷2次后： 2 4 1 5 6 3 7 8 ... 遍歷7次后： 1 2 3 4 5 6 7 8

可以輕易的得出，冒泡在 N– 到 0 為止，每遍近似遍歷了N個(gè)數(shù)據(jù)。所以冒泡的時(shí)間復(fù)雜度是 -O(N^2)。

按照定義實(shí)現(xiàn)代碼如下：

void BubbleSore(int *array, int n) { int i = 0;int j = 0;int temp = 0;for(i = 0; i < n; ++i){ for(j = 1; j < n - i; ++j){if(array[j - 1] > array[j]){temp = array[j-1];array[j - 1] = array[j];array[j] = temp;}}} }

我們對可以對冒泡進(jìn)行優(yōu)化，循環(huán)時(shí)，當(dāng)100個(gè)數(shù)據(jù)，僅前10個(gè)無序，發(fā)生了交換，后面沒有交換說明有序且都大于前10個(gè)數(shù)據(jù)，那么以后循環(huán)遍歷時(shí)，就不必對后面的90個(gè)數(shù)據(jù)進(jìn)行遍歷判斷，只需每遍從0循環(huán)到10就行了。

void BubbleSore(int *array, int n) //優(yōu)化 { int i = n;int j = 0;int temp = 0;Boolean flag = TRUE; while(flag){flag = FALSE; for(j = 1; j < i; ++j){if(array[j - 1] > array[j]){temp = array[j-1];array[j - 1] = array[j];array[j] = temp;flag = TRUE;} }i--;} }

雖然我們對冒泡進(jìn)行了優(yōu)化，但優(yōu)化后的時(shí)間復(fù)雜度邏輯上還是-O(n^2)，所以說冒泡還是效率比較低下的，數(shù)據(jù)較大時(shí)，建議不要采用冒泡。

二，最易理解的排序——選擇排序
如果讓一個(gè)初學(xué)者寫一個(gè)排序算法，很有可能寫出的就是選擇排序(反正我當(dāng)時(shí)就是 ^.^)，因?yàn)檫x擇排序甚至比冒泡更容易理解。

原理就是遍歷一遍找到最小的，與第一個(gè)位置的數(shù)進(jìn)行交換。再遍歷一遍找到第二小的，與第二個(gè)位置的數(shù)進(jìn)行交換。看起來比較像冒泡，但它不是相鄰數(shù)據(jù)交換的。

無序數(shù)組： 2 5 4 7 1 6 8 3 遍歷1次后： 1 5 4 7 2 6 8 3 遍歷2次后： 1 2 4 7 5 6 8 3 ... 遍歷7次后： 1 2 3 4 5 6 7 8

選擇排序的時(shí)間復(fù)雜度也是 -O(N^2);

void Selectsort(int *array, int n) {int i = 0;int j = 0;int min = 0;int temp = 0; for(i; i < n; i++){min = i;for(j = i + 1; j < n; j++){if(array[min] > array[j])min = j;}temp = array[min];array[min] = array[i];array[i] = temp; } } #endif

三，撲克牌法排序——插入排序
打牌時(shí)(以挖坑為例)我們一張張的摸牌，將摸到的牌插入手牌的”順子”里,湊成更長的順子，這就是插入排序的含義。

設(shè)無序數(shù)組a[]長度為N，以由小到大排序?yàn)槔２迦氲脑硎沁@樣的：
1.初始時(shí)，第一個(gè)數(shù)據(jù)a[0]自成有序數(shù)組，后面的a[1]~a[N-1]為無序數(shù)組。令 i = 1;
2.將第二個(gè)數(shù)據(jù)a[1]加入有序序列a[0]中，使a[0]~a[1]變?yōu)橛行蛐蛄小++;
3.重復(fù)循環(huán)第二步，直到將后面的所有無序數(shù)插入到前面的有序數(shù)列內(nèi)，排序完成。

無序數(shù)組： 2 | 5 4 7 1 6 8 3 遍歷1次后： 2 5 | 4 7 1 6 8 3 遍歷2次后： 2 4 5 | 7 1 6 8 3 遍歷3次后： 2 4 5 7 | 1 6 8 3 ...

插入排序的時(shí)間度仍然是-O(N^2)，但是，插入排序是一種比較快的排序，因?yàn)樗看味际呛陀行虻臄?shù)列進(jìn)行比較插入，所以每次的比較很有”意義”，導(dǎo)致交換次數(shù)較少，所以插入排序在-O(N^2)級別的排序中是比較快的排序算法。

{int i = 0;int j = 0;int temp = 0; for(i = 1; i < n; i++){if(array[i] < array[i-1]){temp = array[i]; for(j = i - 1; j >= 0 && array[j] > temp; j--){ array[j+1] = array[j];}array[j+1] = temp;}} }

四，最快的排序——快速排序
我真的很敬佩設(shè)計(jì)出這個(gè)算法的大神，連起名字都這么霸氣——Quick Sort。為什么這么自信的叫快速排序？因?yàn)橐呀?jīng)被數(shù)學(xué)家證明出在交換類排序算法中，快排是是速度最快的！
快排是C.R.A.Hoare于1962年提出的一種劃分交換區(qū)的排序。它采用一種很重要的”分治法(Divide-and-ConquerMethod)”的思想。快排是一種很有實(shí)用價(jià)值的排序方法，很多IT公司在面試算法時(shí)幾乎都會去問，所以快排是一定要掌握的。

快排的原理是這樣的：
1. 先在無序的數(shù)組中取出一個(gè)數(shù)作為基數(shù)。
2. 將比基數(shù)小的數(shù)扔到基數(shù)的左邊，成為一個(gè)區(qū)。將比基數(shù)大的數(shù)扔到基數(shù)的右邊，成為另一個(gè)區(qū)。
3. 將左右兩個(gè)區(qū)重復(fù)進(jìn)行前兩步操作，使數(shù)列變成四個(gè)區(qū)。
4. 重復(fù)操作，直到每個(gè)區(qū)里只有一個(gè)數(shù)時(shí)，排序完成。

快速排序初次接觸比較難理解，我們可以把快排看做挖坑填數(shù)，具體操作如下：

數(shù)組下標(biāo)： 0 1 2 3 4 5 6 7 無序數(shù)列： 4 2 5 7 1 6 8 3

初始時(shí)，left = 0; right = 7; 將第一個(gè)數(shù)設(shè)為基數(shù) base = a[left];
由于將a[0]保存到base中，可以理解為在a[0]處挖了一個(gè)坑，可以將數(shù)據(jù)填入a[0]中。
從最右邊right挨個(gè)開始找比base小的數(shù)。當(dāng)right==7符合，則將a[7]挖出來填入a[0]的坑里面(a[0] = a[7])，所以又形成了新坑a[7]，并且left ++。
再從左邊left開始挨個(gè)找比base大的數(shù)(注意上一步left++)，當(dāng)left == 2符合，就將a[2]挖出來填入a[7]位置處，并且right–。
現(xiàn)在數(shù)組變?yōu)?#xff1a;

數(shù)組下標(biāo)： 0 1 2 3 4 5 6 7 無序數(shù)列： 3 2 5 7 1 6 8 5

重復(fù)以上步驟，左邊挖的坑在右邊找，右邊找到比基數(shù)小的填到左邊，左邊++。右邊的坑在左邊找，找到比基數(shù)大的填在右邊，右邊–。
循環(huán)條件是left > right,當(dāng)排序完后，將基數(shù)放在循環(huán)停止的位置，比基數(shù)小的都到了基數(shù)的左邊，比基數(shù)大的都到了基數(shù)的右邊。

數(shù)組下標(biāo)： 0 1 2 3 4 5 6 7 無序數(shù)列： 3 2 1 4 7 6 8 5

再對0~2區(qū)間和4~7區(qū)間重復(fù)以上操作。直到分的區(qū)間只剩一個(gè)數(shù)，證明排序已經(jīng)完成。

可以看出快排是將數(shù)組一分為二到底，需要log N次，再乘以每個(gè)區(qū)間的排序次數(shù) N。所以時(shí)間復(fù)雜度為：-O(N * log N)。

void Quicksort(int *array, int l, int r) {int i = 0;int j = 0;int x = 0;if(l < r){i = l;j = r;x = array[l];while(i < j){while(i < j && array[j] >= x){j--;}if(i < j){array[i++] = array[j];} while(i < j && array[i] <= x){i++;}if(i < j){array[j--] = array[i];}}array[i] = x;Quicksort(array, l, i - 1);Quicksort(array, i + 1, r);} }

快排還有許多改進(jìn)版本，如隨機(jī)選擇基數(shù)，區(qū)間內(nèi)數(shù)據(jù)較少時(shí)直接用其他排序來減小遞歸的深度等等。快排現(xiàn)在仍是很多人研究的課題，有興趣的同學(xué)可以深入的研究下。

五，分而治之——?dú)w并排序
歸并排序是建立在歸并操作上的一種優(yōu)秀的算法，也是采用分治思想的典型例子。
我們知道將兩個(gè)有序數(shù)列進(jìn)行合并，是很快的，時(shí)間復(fù)雜度只有-O(N)。而歸并就是采用這種操作，首先將有序數(shù)列一分二，二分四……直到每個(gè)區(qū)都只有一個(gè)數(shù)據(jù)，可以看做有序序列。然后進(jìn)行合并，每次合并都是有序序列在合并，所以效率比較高。

無序數(shù)組： 2 5 4 7 1 6 8 3 第一步拆分：2 5 4 7 | 1 6 8 3 第二步拆分：2 5 | 4 7 | 1 6 | 8 3 第三步拆分：2 | 5 | 4 | 7 | 1 | 6 | 8 | 3 第一步合并：2 5 | 4 7 | 1 6 | 3 8 第二步合并：2 4 5 7 | 1 3 6 8 第三步合并：1 2 3 4 5 6 7

可見歸并排序的時(shí)間復(fù)雜度是拆分的步數(shù) log N 乘以排序步數(shù) N ，為-O(N * log N)。也是高級別的排序算法(-O(N ^ 2)為低級別)。

void Mergesort(int *array, int n) {int *temp = NULL;if(array == NULL || n < 2)return;temp = (int *)Malloc(sizeof(int )*n);mergesort(array, 0, n - 1, temp);free(temp); }void mergesort(int *array, int first, int last, int *temp) {int mid = -1;if(first < last){mid = first + ((last - first) >> 1);mergesort(array, first, mid, temp);mergesort(array, mid+1, last, temp);mergearray(array, first, mid, last, temp); } }void mergearray(int *array, int first, int mid, int last, int *temp) {int i = first;int m = mid;int j = mid + 1;int n = last;int k = 0;while(i <= m && j <= n){if(array[i] <= array[j]){temp[k++] = array[i++];}else{temp[k++] = array[j++];}}while(i <= m){temp[k++] = array[i++];}while(j <= n){temp[k++] = array[j++];}memcpy(array + first, temp, sizeof(int) * k); }

由于要申請等同于原數(shù)組大小的臨時(shí)數(shù)組，歸并算法快速排序的同時(shí)也犧牲了N大小的空間。這是速率與空間不可調(diào)和矛盾，接觸數(shù)據(jù)結(jié)構(gòu)越多，越能發(fā)現(xiàn)這個(gè)道理，我們只能取速度與空間權(quán)衡點(diǎn)，不可能兩者兼得。

六，縮小增量——希爾排序
希爾排序的實(shí)質(zhì)就是分組插入排序，該方法又稱為縮小增量排序，因DJ.Shell與1959年提出而得名。

該方法的基本思想是：先將整個(gè)待排序列分割成若干個(gè)子序列(由相隔某個(gè)”增量”的元素組成)分別進(jìn)行插入排序，然后依次縮減增量再次進(jìn)行排序，待整個(gè)序列中的元素基本有序時(shí)(增量足夠小)，再對全體進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下(接近最好情況)，效率是很高的。

無序數(shù)組： 2 5 4 7 1 6 8 3 第一次gap=8/2 2A 1A5B 6B4C 8C7D 3D

設(shè)第一次增量為N/2 = 4，即a[0]和a[4]插入排序，a[1]和a[5]插入排序，a[2]和a[6]，a[3]和a[7].字母相同代表在同一組進(jìn)行排序。
排序完后變?yōu)?#xff1a;

一次增量： 1 5 4 3 2 6 8 7A B C D A B C D

縮小增量，gap=4/2。

一次增量： 1 5 4 3 2 6 8 7 第二次gap=4/2 ：1A 4A 2A 8A5B 3B 6B 7B

第二次增量變?yōu)?，即a[0]，a[2]，a[4]，a[6]一組進(jìn)行插入排序。a[1]，a[3]，a[5]，a[7]一組進(jìn)行排序。結(jié)果為：

二次增量： 1 3 2 5 4 6 8 7

第三次增量gap=1，直接進(jìn)行選擇排序。

三次增量： 1 2 3 4 5 6 7 8

希爾排序的時(shí)間復(fù)雜度為-O(N * log N)，前提是使用最佳版本，后面有提到。

void Shellsort(int *array, int n) {int i,j,k,temp,gap;for(gap = n/2; gap > 0; gap /= 2){for(i = 0; i < gap; i++){for(j = i + gap; j < n; j += gap){ for(k = j - gap; k >= i && array[k] > array[k+1]; k -= gap){temp = array[k+1];array[k+1] = array[k];array[k] = temp;} } }} }

很顯然，上面的Shell排序雖然對直觀理解希爾排序有幫助，但代碼過長循環(huán)過多，不夠簡潔清晰。因此進(jìn)行一下改進(jìn)和優(yōu)化，在gap內(nèi)部進(jìn)行排序顯然也能達(dá)到縮小增量排序的目的。

void Shellsort(int *array, int n) {int i,j,k,temp;for(gap = n/2; gap > 0; gap /= 2){for(j = gap; j < n; j ++){if(array[j] < array[j-gap]){temp = array[j];k = j - gap;while(k >= 0 && array[k] > temp){array[k+gap] = array[k];k -= gap;}array[k+gap] = temp;} }} }

希爾排序的縮小增量思想很重要，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)主要就是學(xué)習(xí)思想。我們上面排序的步長gap都是N/2開始，在進(jìn)行減半，實(shí)際上還有更高效的步長選擇，如果你有興趣，可以去維基百科查看更多的步長算法推導(dǎo)。

七，集中數(shù)據(jù)的排序——計(jì)數(shù)排序
如果有這樣的數(shù)列，其中元素種類并不多，只是元素個(gè)數(shù)多，請選擇->計(jì)數(shù)排序。
比如一億個(gè)1~100的整型數(shù)據(jù)，它出現(xiàn)的數(shù)據(jù)只有100種可能。這個(gè)時(shí)候計(jì)數(shù)排序非常的快(親測，快排需要19秒，基數(shù)排序只需要不到1秒！)。

計(jì)數(shù)排序的思想是這樣的：
1. 根據(jù)數(shù)據(jù)范圍size(100)，malloc構(gòu)造一個(gè)用于計(jì)算數(shù)據(jù)出現(xiàn)次數(shù)的數(shù)組,并將其初始化個(gè)數(shù)都置為0。
2. 遍歷一遍，將出現(xiàn)的每個(gè)數(shù)據(jù)的次數(shù)記錄于數(shù)組。
3. 再次遍歷，按照順序并根據(jù)數(shù)據(jù)出現(xiàn)的次數(shù)重現(xiàn)擺放，排序完成。

可見計(jì)數(shù)排序僅僅遍歷了兩遍。時(shí)間復(fù)雜度：-O(N) + -O(N) = -O(N)。

void count_sort(int *array, int length, int min, int max) {int *count = NULL;int c_size = max - min + 1;int i = 0;int j = 0;count = (int *)Malloc(sizeof(int) * c_size); bzero(count, sizeof(int) * c_size); for(i = 0; i < length; ++i){count[array[i] - min]++;} for(i = 0, j = 0; i < c_size;){if(count[i]){ array[j++] = i + min;count[i]--;}else{i++;} }free(count); }

計(jì)數(shù)排序雖然時(shí)間復(fù)雜度最小，速度最快。但是，限制條件是數(shù)據(jù)一定要比較集中，要是數(shù)據(jù)范圍很大，程序可能會卡死。

八，構(gòu)造樹——二叉堆排序

堆排序與快速排序，歸并排序一樣都是時(shí)間復(fù)雜度為 O(N*logN)的幾種常見排序方法。學(xué)習(xí)堆排序前，先講解下什么是數(shù)據(jù)結(jié)構(gòu)中的二叉堆。

二叉堆的定義：
二叉堆是完全二叉樹或者是近似完全二叉樹。

二叉堆滿足二個(gè)特性：
1．父結(jié)點(diǎn)的鍵值總是大于或等于（小于或等于）任何一個(gè)子節(jié)點(diǎn)的鍵值。
2．每個(gè)結(jié)點(diǎn)的左子樹和右子樹都是一個(gè)二叉堆（都是最大堆或最小堆）。

當(dāng)父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最大堆。當(dāng)父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最小堆。下圖展示一個(gè)最小堆：

由于其它幾種堆（二項(xiàng)式堆，斐波納契堆等）用的較少，一般將二叉堆就簡稱為堆。

堆的存儲：
一般都用數(shù)組來表示堆，i 結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為(i – 1) / 2。它的左右子結(jié)點(diǎn)下標(biāo)分別為 2 * i + 1 和 2 * i + 2。如第 0 個(gè)結(jié)點(diǎn)左右子結(jié)點(diǎn)下標(biāo)分別為 1 和 2。

堆的操作——插入刪除:
下面先給出《數(shù)據(jù)結(jié)構(gòu) C++語言描述》中最小堆的建立插入刪除的圖解，再給出代碼實(shí)現(xiàn)，最好是先看明白圖后再去看代碼。

堆的插入:
每次插入都是將新數(shù)據(jù)放在數(shù)組最后。可以發(fā)現(xiàn)從這個(gè)新數(shù)據(jù)的父結(jié)點(diǎn)到根結(jié)點(diǎn)必然為一個(gè)有序的數(shù)列，現(xiàn)在的任務(wù)是將這個(gè)新數(shù)據(jù)插入到這個(gè)有序數(shù)據(jù)中——這就類似于直接插入排序中將一個(gè)數(shù)據(jù)并入到有序區(qū)間中，寫出插入一個(gè)新數(shù)據(jù)時(shí)堆的調(diào)整代碼：

void MinHeapFixup(int a[], int i) {int j,temp;temp = a[i];j = (i - 1) / 2; //父結(jié)點(diǎn)while (j >= 0){if (a[j] <= temp)break;a[i] = a[j]; //把較大的子結(jié)點(diǎn)往下移動(dòng),替換它的子結(jié)點(diǎn)i = j;j = (i - 1) / 2;}a[i] = temp; }

更簡短的表達(dá)為：

void MinHeapFixup(int a[], int i) {for (int j = (i - 1) / 2; j >= 0 && a[i] > a[j]; i = j, j = (i - 1) / 2)Swap(a[i], a[j]);}

插入時(shí)：//在最小堆中加入新的數(shù)據(jù)nNum

void MinHeapAddNumber(int a[], int n, int nNum) {a[n] = nNum;MinHeapFixup(a, n); }

堆的刪除：
按定義，堆中每次都只能刪除第 0 個(gè)數(shù)據(jù)。為了便于重建堆，實(shí)際的操作是將最后一個(gè)數(shù)據(jù)的值賦給根結(jié)點(diǎn)，然后再從根結(jié)點(diǎn)開始進(jìn)行一次從上向下的調(diào)整。調(diào)整時(shí)先在左右兒子結(jié)點(diǎn)中找最小的，如果父結(jié)點(diǎn)比這個(gè)最小的子結(jié)點(diǎn)還小說明不需要調(diào)整了，反之將父結(jié)點(diǎn)和它交換后再考慮后面的結(jié)點(diǎn)。相當(dāng)于從根結(jié)點(diǎn)將一個(gè)數(shù)據(jù)的“下沉”過程。下面給出代碼：

// 從i節(jié)點(diǎn)開始調(diào)整,n為節(jié)點(diǎn)總數(shù) 從0開始計(jì)算 i節(jié)點(diǎn)的子節(jié)點(diǎn)為 2*i+1, 2*i+2 void MinHeapFixdown(int a[], int i, int n) {int j, temp;temp = a[i];j = 2 * i + 1;while (j < n){if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的j++;if (a[j] >= temp)break;a[i] = a[j]; //把較小的子結(jié)點(diǎn)往上移動(dòng),替換它的父結(jié)點(diǎn)i = j;j = 2 * i + 1;}a[i] = temp; }

//在最小堆中刪除數(shù)

void MinHeapDeleteNumber(int a[], int n) {Swap(a[0], a[n - 1]);MinHeapFixdown(a, 0, n - 1); }

堆化數(shù)組：
有了堆的插入和刪除后，再考慮下如何對一個(gè)數(shù)據(jù)進(jìn)行堆化操作。要一個(gè)一個(gè)的從數(shù)組中取出數(shù)據(jù)來建立堆吧，不用！先看一個(gè)數(shù)組，如下圖：

很明顯，對葉子結(jié)點(diǎn)來說，可以認(rèn)為它已經(jīng)是一個(gè)合法的堆了即 20，60， 65，4， 49 都分別是一個(gè)合法的堆。只要從 A[4]=50 開始向下調(diào)整就可以了。然后再取 A[3]=30，A[2] = 17，A[1] = 12，A[0] = 9 分別作一次向下調(diào)整操作就可以了。下圖展示了這些步驟：

寫出堆化數(shù)組的代碼：

//建立最小堆 void MakeMinHeap(int a[], int n) {for (int i = n / 2 - 1; i >= 0; i--)MinHeapFixdown(a, i, n); }

至此，堆的操作就全部完成了，再來看下如何用堆這種數(shù)據(jù)結(jié)構(gòu)來進(jìn)行排序。

堆排序：
首先可以看到堆建好之后堆中第 0 個(gè)數(shù)據(jù)是堆中最小的數(shù)據(jù)。取出這個(gè)數(shù)據(jù)再執(zhí)行下堆的刪除操作。
這樣堆中第 0 個(gè)數(shù)據(jù)又是堆中最小的數(shù)據(jù)，重復(fù)上述步驟直至堆中只有一個(gè)數(shù)據(jù)時(shí)就直接取出這個(gè)數(shù)據(jù)。由于堆也是用數(shù)組模擬的，故堆化數(shù)組后，第一次將 A[0]與 A[n - 1]交換，再對A[0…n-2]重新恢復(fù)堆。第二次將 A[0]與 A[n – 2]交換，再對 A[0…n - 3]重新恢復(fù)堆，重復(fù)這樣的操作直到 A[0]與 A[1]交換。
由于每次都是將最小的數(shù)據(jù)并入到后面的有序區(qū)間，故操作完成后整個(gè)數(shù)組就有序了。有點(diǎn)類似于直接選擇排序。

// 堆排序最小堆 –> 降序排序 void MinheapsortTodescendarray(int a[], int n) {for (int i = n - 1; i >= 1; i--){Swap(a[i], a[0]);MinHeapFixdown(a, 0, i);} }

注意使用最小堆排序后是遞減數(shù)組，要得到遞增數(shù)組，可以使用最大堆。由于每次重新恢復(fù)堆的時(shí)間復(fù)雜度為 O(logN)，共 N - 1 次重新恢復(fù)堆操作，再加上前面建立堆時(shí) N / 2 次向下調(diào)整，每次調(diào)整時(shí)間復(fù)雜度也為 O(logN)。二次操作時(shí)間相加還是 O(N * logN)。故堆排序的時(shí)間復(fù)雜度為 O(N * logN)。

總結(jié)

以上是生活随笔為你收集整理的排序八种经典排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

编程问答

排序 八种经典排序算法

總結(jié)

排序八种经典排序算法