如何進行C語言數據結構與算法中的排序總結
這篇文章將為大家詳細講解有關如何進行C語言數據結構與算法中的排序總結，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。
一、前言
學習目標：
排序和查找密不可分，將待處理的數據按關鍵值大小有序排列后，查找更加快速準確
理解各種排序算法的定義和特點，并能將代碼靈活運用
掌握各種排序方法時間復雜度與空間復雜度
理解排序穩定和不穩定的概念? ? ? ? ? ? ? ??
重點和難點： 希爾、快速、堆、歸并排序這幾種快速排序
二、基本概念
1.排序
定義：將一個無序的數據元素任意序列，重新排列成有序的過程
代碼：
typedef?struct{??
???????int?key;???//假設關鍵字為int型
???????OtherType??other_data;
}?RecordType;
2.排序方法的穩定性
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 5 | 4 | 10 | 11 | 22 | 8 | 10 | 76 | 1 | 2 |
解讀：如上個表格這樣的一個無序數組，想要將它按照從小到大排序。上圖下標2和6對應的數字都是10，排序后假如紅色的10任然在黑色的10前面，那這種排序方法就是穩定的，否則排序方法不穩定。
3.內部和外部排序
內部排序：整個排序過程在內存中
外部排序：需要排序的數過大，需要借助外部設備
三、插入類排序
插入類：在一個有序序列插入一個新的記錄，使之仍然有序
1.直接插入排序
動態演示：
算法講解：?
上面的動態圖可以很好的表達直接插入的過程，只是動態圖有點長
首先將0作為監視哨，用一個指針從前往后找后面的數字比前面數字小的，找到了放到0
指針開始向前移動，如果指向的值比監視哨里的值大，數字向后移
如果指向的值比監視哨里的值小，那把監視哨里的值存入這個元素之后
以此類推
代碼：
void?InsSort(RecordType??r[],??int?length)
/*?對記錄數組r做直接插入排序，length為數組中待排序記錄的數目*/
{?
int?i,j;
for?(i=2;??i<=length;??i++)?
{
r[0]=r[i];??????/*將待插入記錄存放到監視哨r[0]中*/
j=i-1; ?????????
while?(r[0].key<?r[j].key?)?????/*?尋找插入位置?*/
{
r[j+1]=?r[j];?
j=j-1;
}
r[j+1]=r[0]; /*將待插入記錄插入到已排序的序列中*/
}
}?/*??InsSort??*/
特點：?
穩定排序
時間復雜度O(n*n), 空間復雜度O(1)
2.折半插入排序
算法講解：
動態圖沒找到，只能用上面這張圖片了
折半插入和折半查找思想差不多，對于一個有序的數組，將一個數字插入之后任然有序
k=要插入的值? low=1, high=length , mid=(low+high)+1? ?mid對應的值比k大， high=low-1,否則 low=mid+1,
當low >high ，low后面就是k插入的位置
代碼：
void?BinSort?(RecordType??r[],??int?length)
/*對記錄數組r進行折半插入排序，length為數組的長度*/
{
int?i,j;
????RecordType?x;
????int?low,high,mid;
for?(i=2;?i<=length?;?++i?)?
{
x=?r[i];??low=1;??high=i-1;
while?(low<=high?)??????????????????/*?確定插入位置*/?
{
mid=(low+high)?/?2;
if?(?x.key<?r[mid].key)?high=mid-1;
else? low=mid+1;
}
for?(?j=i-1?;?j>=?low;?--j?)???r[j+1]=?r[j];????/*??記錄依次向后移動?*/?
r[low]=x;???/*?插入記錄?*/?
}
}/*BinSort*/
特點：?
穩定排序
時間復雜度O(n*n), 空間復雜度O(1)
3.希爾排序
動態演示：
算法講解：?
對于希爾排序來說取增量 d (d一般為奇數，并且逐次遞減)
上圖第一次排序d等于5，將第一個作為起始點，下標+5取下一個值，一直到最后，將去到的值從小到達排序，然后將第二個作為起始點，3 4 5依次作為起始點排序
第二次是d等于3
第三次是d等于1
代碼：
void??ShellInsert(RecordType?r[],?int?length,??int??delta)
/*對記錄數組r做一趟希爾插入排序，length為數組的長度,delta?為增量*/
{ int?i,j;
for(i=1+delta;i<=?length;?i++)?????/*?1+delta為第一個子序列的第二個元素的下標?*/
if(r[i].key?<?r[i-delta].key)
{
r[0]=?r[i];??????????/*??備份r[i]??(不做監視哨)?*/
for(j=i-delta;?j>0?&&r[0].key?<?r[j].key;?j-=delta)
r[j+delta]=?r[j];
r[j+delta]=?r[0];
}
}/*ShellInsert*/
特點：
不穩定排序方法
增量序列的d取值無除1之外的公因子，最后一個增量值必須為1
時間復雜度O(nlogn)? 空間復雜度O(1)
四、交換類排序
1.冒泡排序
動態演示：
算法講解：?
設立兩個指針，i，j
每一次排序都會把最大的一個數放到后面，依次類推，假設執行2次以后，那么最后2個數就不需要比較了
執行n-1次排序，結果完成
代碼：
void??BubbleSort(RecordType?r[],?int?length?)
/*對記錄數組r做冒泡排序，length為數組的長度*/
{ int?n,i,j;?nt?change;?RecordType?x;?n=length;??change=TRUE;
for?(?i=1?;?i<=?n-1?&&?change?;++i?)?
{ change=FALSE;
for?(?j=1?;?j<=?n-i?;?++j)?
if?(r[j].key?>?r[j+1].key?)??
{
x=?r[j];
r[j]=?r[j+1];
r[j+1]=?x;
change=TRUE;
}?
}
}?/*??BubbleSort
特點：
穩定排序
時間復雜度O(n*n), 空間復雜度O(1)
2.快速排序
動態演示：
算法講解：
快速排序講起來稍微有點復雜，其實就是劃分區域
建立兩個指針low high 分別指向第一個和第二個元素，把第一個元素的值賦給x變量
high向前移動，假如high指向的值小于x，則high指向的值與x互換
low向后移動，假如low指向的值大于x，則low指向的值與x互換
重復3 4兩步，知道high==low，第一次結束
將low指向第二個元素，把第二個元素的值賦給x變量
重復操作，知道元素有序
代碼：
1.遞歸算法:
void?QKSort(RecordType?r[],int?low,?int?high?)
/*對記錄數組r[low..high]用快速排序算法進行排序*/
{
int?pos;
if(low<high)
{
pos=QKPass(r,?low,?high);??/*調用一趟快速排序，將樞軸元素為界劃分兩個子表*/
QKSort(r,?low,?pos-1);?????/*對左部子表快速排序*/
QKSort(r,?pos+1,?high);?/*對右部子表快速排序*/
}
}
2.非遞歸算法：
int?QKPass(RecordType?r[],int?left,int?right)
/*對記錄數組r?中的r[left]至r[right]部分進行一趟排序，并得到基準的位置，使得排序后的結果滿足其之后（前）的記錄的關鍵字均不小于（大于）于基準記錄*/
{?
RecordType?x; int?low,high;
x=?r[left];?????????????/*?選擇基準記錄*/?
low=left;?? high=right;
while?(?low<high?)
{
while?(low<?high?&&?r[high].key>=x.key?)???/*?high從右到左找小于x.key的記錄?*/
high--;
if?(?low?<high?)?{r[low]=?r[high];??low++;}??/*?找到小于x.key的記錄，則進行交換*/
while?(low<high?&&?r[low].key<x.key??)???/*?low從左到右找大于x.key的記錄?*/
low++;?
if?(??low<high??){?r[high]=?r[low];?high--;?}?/*?找到大于x.key的記錄，則交換*/
}
r[low]=x;?????????????????????/*將基準記錄保存到low=high的位置*/
return?low;?????????????????????/*返回基準記錄的位置*/
}?/*?QKPass?*/
特點：
不穩定排序，但內部排序中公認效率最好的一種
時間復雜度O(nlogn)? 空間復雜度O(logn)
五、總結比較
關于如何進行C語言數據結構與算法中的排序總結就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：niceseo99@gmail.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
評論