您好,登錄后才能下訂單哦!
這篇文章主要介紹“C語言數(shù)據(jù)結(jié)構(gòu)與算法排序的方法有哪些”,在日常操作中,相信很多人在C語言數(shù)據(jù)結(jié)構(gòu)與算法排序的方法有哪些問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對大家解答”C語言數(shù)據(jù)結(jié)構(gòu)與算法排序的方法有哪些”的疑惑有所幫助!接下來,請跟著小編一起來學(xué)習(xí)吧!
主要介紹選擇類排序中的簡單、樹形和堆排序,歸并排序、分配類排序的基數(shù)排序
選擇類:每次從待排序的無序序列中,選擇一個最大或最小的數(shù)字,放到前面,數(shù)據(jù)元素為空時排序結(jié)束
動態(tài)演示:
算法講解:
首先通過n-1次比較,從n個記錄中找出最小值,將它與第一個元素交換
再通過n-2次比較,從剩余的n-1個記錄中找出次小的值,將它與第二個記錄交換
重復(fù)上述操作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)定排序
時間復(fù)雜度O(n*n), 空間復(fù)雜度O(1)
靜態(tài)演示:
算法講解:
最下面一行21 25 49 25 16 08 63是給定需要從小到大排序的數(shù)字
相鄰的兩個選出一個最小的向上移一層,只有一個的補一個值無窮大的數(shù)
倒數(shù)第二層再次兩兩組合,直到最頂端
此時,最頂端08就是值最小的數(shù),輸出08,把所有08至為無窮大
再次選出一個最小值,以此類推
特點:
算法不作要求
穩(wěn)定排序, 增加額外的存儲空間
時間復(fù)雜度O(nlogn),空間復(fù)雜度O(n-1)
動態(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è)r[k..m]是以r[k]為根的完全二叉樹,且分別以r[2k]和r[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ù)奈恢?nbsp;*/ }
堆排序:
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值較大的排序
時間復(fù)雜度O(n*logn),空間復(fù)雜度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)定排序
時間復(fù)雜度O(nlogn),空間復(fù)雜度O(n)
附加空間比較大,很少用于內(nèi)部排序,主要是外部排序
高位優(yōu)先:按照花色大小分成四類,在每一類中按照面值進行排序
低位優(yōu)先:按照面值大小分成13類,將相同面值的不同花色進行排序
算法講解:
對于上面的9個三位數(shù),第一步我們按照個位數(shù)從小到大排序
接著第一步的結(jié)果,按照十位數(shù)從小到達排序
最后借助第二步的結(jié)果,按照百位數(shù)從小到大排序
同樣的,對于4位 5 位方法一樣
特點:
時間復(fù)雜度O(d*n),d是關(guān)鍵字數(shù),n是記錄數(shù)
穩(wěn)定的排序
空間復(fù)雜度=2個隊列指針+n個指針域
到此,關(guān)于“C語言數(shù)據(jù)結(jié)構(gòu)與算法排序的方法有哪些”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識,請繼續(xù)關(guān)注億速云網(wǎng)站,小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。