C語言數(shù)據(jù)結(jié)構(gòu)與算法之排序總結(jié)(二)
一、前言
之前的排序總結(jié)（一）對插入類和交換類排序作了比較詳細的總結(jié)，對于直接插入、希爾排序、冒泡排序、快速排序要求熟練掌握
這篇排序全面總結(jié)(二)主要介紹選擇類排序中的簡單、樹形和堆排序，歸并排序、分配類排序的基數(shù)排序
二、選擇類排序
選擇類：每次從待排序的無序序列中，選擇一個最大或最小的數(shù)字，放到前面，數(shù)據(jù)元素為空時排序結(jié)束
1.簡單選擇排序
動態(tài)演示：
算法講解：
- 首先通過n-1次比較，從n個記錄中找出最小值，將它與第一個元素交換
- 再通過n-2次比較，從剩余的n-1個記錄中找出次小的值，將它與第二個記錄交換
- 重復上述操作n-1，排序完成
代碼：
void SelectSort(RecordType r[], int length)
/*對記錄數(shù)組r做簡單選擇排序，length為數(shù)組的長度*/
{
int i,j,k; int n; RecordType x; n=length;
for ( i=1 ; i<= n-1; ++i)
{
k=i;
for (j=i+1 ; j<= n ; ++j)
if (r[j].key < r[k].key ) k=j;
if ( k!=i)
{
x= r[i]; r[i]= r[k]; r[k]=x;
}
}
} /* SelectSort */
特點：?
不穩(wěn)定排序
時間復雜度O(n*n), 空間復雜度O(1)
2.樹形選擇排序
靜態(tài)演示：
算法講解：
- 最下面一行21 25 49 25 16 08 63是給定需要從小到大排序的數(shù)字
- 相鄰的兩個選出一個最小的向上移一層，只有一個的補一個值無窮大的數(shù)
- 倒數(shù)第二層再次兩兩組合，直到最頂端
- 此時，最頂端08就是值最小的數(shù)，輸出08，把所有08至為無窮大
- 再次選出一個最小值，以此類推
特點：?
算法不作要求
穩(wěn)定排序, 增加額外的存儲空間
時間復雜度O（nlogn）,空間復雜度O(n-1)
3.堆選擇排序
動態(tài)演示：
算法講解：
- 根結(jié)點值最大的叫大頂堆，根結(jié)點值最小的叫小頂堆，上圖就是一個構(gòu)造大頂堆的圖
- 從最后一層開始，如果孩子結(jié)點的值比父親結(jié)點大，那么就交換位置
- 一層層向上推，直到根結(jié)點值最大
建立初始堆：
void crt_heap(RecordType r[], int length )
/*對記錄數(shù)組r建堆，length為數(shù)組的長度*/
{
int i,n;
n= length;
for ( i=n/2; i >= 1; --i) /* 自第[n/2]個記錄開始進行篩選建堆 */
sift(r,i,n);
}
調(diào)整堆：
void sift(RecordType r[], int k, int m)
/* 假設(shè)ｒ[k..m]是以ｒ[k]為根的完全二叉樹，且分別以ｒ[2k]和ｒ[2k+1]為根的左、右子樹為大根堆，調(diào)整r[k]，使整個序列r[k..m]滿足堆的性質(zhì) */
{ RecordType t; int i,j; int x; int finished;
t= r[k]; /* 暫存"根"記錄r[k] */
x=r[k].key; i=k; j=2*i;
finished=FALSE;
while( j<=m && !finished )
{
if (j<m && r[j].key< r[j+1].key ) j=j+1; /* 若存在右子樹，
且右子樹 根的關(guān)鍵字大，則沿右分支"篩選" */
if ( x>= r[j].key) finished=TRUE; /* 篩選完畢 */
else
{ r[i] = r[j]; i=j; j=2*i; } /* 繼續(xù)篩選 */
}
r[i] =t; /* r[k]填入到恰當?shù)奈恢?*/
}
堆排序：
void HeapSort(RecordType r[],int length)
/* 對r[1..n]進行堆排序，執(zhí)行本算法后，r中記錄按關(guān)鍵字由大到小有序排列 */
{
int i,n; RecordType b;
crt_heap(r, length); n= length;
for ( i=n ; i>= 2; --i)
{
b=r[1]; /* 將堆頂記錄和堆中的最后一個記錄互換 */
r[1]= r[i];
r[i]=b;
sift(r,1,i-1); /* 進行調(diào)整，使r[1..i-1]變成堆 */
}
} /* HeapSort */
特點：?
堆選擇是樹形的改進，空間占用較小
不穩(wěn)定排序，適合n值較大的排序
時間復雜度O(n*logn)，空間復雜度O(1)
三、歸并排序
法一：
將整體數(shù)字一分為二，逐層細分
細分完成后，每一塊進行排序，直到整體有序
法二：
將一串序列，相鄰的兩個歸并到一起排序，再次把相鄰兩個有序的歸并塊再次排序，直到最后有序（優(yōu)先推薦這種算法）
代碼：
void MergeSort ( RecordType r[], int n) /* 對記錄數(shù)組r[1..n]做歸并排序 */
{
MSort ( r, 1, n, r);
}
void MSort(RecordType r1[], int low, int high, RecordType r3[])
/* r1[low..high]經(jīng)過排序后放在r3[low..high]中，r2[low..high]為輔助空間 */
{
int mid; RecordType r2[20];
if (low==high) r3[low]=r1[low];
else
{
mid=(low+high)/2;
MSort(r1,low, mid, r2);
MSort(r1,mid+1,high, r2);
Merge (r2,low,mid,high, r3);
}
} /* MSort */
特點：?
穩(wěn)定排序
時間復雜度O(nlogn)，空間復雜度O(n)
附加空間比較大，很少用于內(nèi)部排序，主要是外部排序
四、分配類排序
1.多關(guān)鍵字排序
高位優(yōu)先：按照花色大小分成四類，在每一類中按照面值進行排序
低位優(yōu)先：按照面值大小分成13類，將相同面值的不同花色進行排序
2.鏈式基數(shù)排序
算法講解：
- 對于上面的9個三位數(shù)，第一步我們按照個位數(shù)從小到大排序
- 接著第一步的結(jié)果，按照十位數(shù)從小到達排序
- 最后借助第二步的結(jié)果，按照百位數(shù)從小到大排序
- 同樣的，對于4位 5 位方法一樣
特點：
時間復雜度O(d*n)，d是關(guān)鍵字數(shù)，n是記錄數(shù)
穩(wěn)定的排序
空間復雜度=2個隊列指針+n個指針域
五、總結(jié)歸納
到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)與算法之排序總結(jié)(二)的文章就介紹到這了,更多相關(guān)C語言 數(shù)據(jù)結(jié)構(gòu) 排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了在MFC中利用CComboBox控件修改編輯框光標顯示位置的兩種解決方法，文中的示例代碼講解詳細，感興趣的可以了解一下2022-02-02
本文主要介紹了C++ 逗號運算符的具體使用,使用逗號運算符是為了把幾個表達式放在一起,具有一定的參考價值,感興趣的可以了解一下2023-08-08
以下是對c語言中static函數(shù)的用法進行了詳細的分析介紹，需要的朋友可以過來參考下2013-08-08
這篇文章主要介紹了在Visual Studio 2019中修改項目名的方法，文中通過示例介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-03-03
Visual?Studio2022的完全卸載及安裝到D盤的操作方法
這篇文章主要介紹了Visual?Studio2022的完全卸載以及完全安裝到D盤,因為VS如果隨便寫在會有很多很多的亂七八糟的東西掉出來，所以我們選擇制式一點的卸載方式，需要的朋友可以參考下2022-09-09
這篇文章主要介紹了C++語言中的加法運算符與賦值運算符的用法,是C++入門學習中的基礎(chǔ)知識,需要的朋友可以參考下2016-01-01
C++實現(xiàn)判斷一個字符串是否為UTF8或GBK格式的方法
這篇文章主要介紹了C++實現(xiàn)判斷一個字符串是否為UTF8或GBK格式的方法,涉及C++針對字符編碼的遍歷、判斷、編碼轉(zhuǎn)換等相關(guān)操作技巧,需要的朋友可以參考下2017-11-11
下面小編就為大家?guī)硪黄褂胷emalloc的注意事項說明(必看篇)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-03-03
下面小編就為大家?guī)硪黄猚++ 類中const成員變量的賦值方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
Matlab實現(xiàn)黑洞優(yōu)化算法的示例代碼
根據(jù)黑洞現(xiàn)象原理首次提出BH 算法,它在傳統(tǒng)PSO基礎(chǔ)上引入了新的機制,有效地提高了收斂速度并防止了陷入局部極值的情況發(fā)生.本文將用Matlab實現(xiàn)這一算法，需要的可以參考一下2022-06-06