您好,登錄后才能下訂單哦!
這篇文章主要為大家展示了“C語(yǔ)言中排序算法怎么用”,內(nèi)容簡(jiǎn)而易懂,條理清晰,希望能夠幫助大家解決疑惑,下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“C語(yǔ)言中排序算法怎么用”這篇文章吧。
排序:所謂排序,就是使一串記錄,按照其中的某個(gè)或某些關(guān)鍵字的大小,遞增或遞減的排列起來(lái)的操作。
穩(wěn)定性:假定在待排序的記錄序列中,存在多個(gè)具有相同的關(guān)鍵字的記錄,若經(jīng)過(guò)排序,這些記錄的相對(duì)次
序保持不變,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,則稱(chēng)這種排
序算法是穩(wěn)定的;否則稱(chēng)為不穩(wěn)定的。 內(nèi)部排序:數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序:數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中,根據(jù)排序過(guò)程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。
高校排名:
接下來(lái),我會(huì)一一介紹幾種常見(jiàn)的排序算法
直接插入排序是一種簡(jiǎn)單的插入排序法
基本思想: 把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中,直到所有的記錄插入完為止,得到一個(gè)新的有序序列
代碼的實(shí)現(xiàn)
//直接插入排序 void InsertSort(int* a, int n) { assert(a);//傳入數(shù)組不為空指針 int i; for (i = 0; i < n - 1; i++) { int end = i; int x = a[end + 1]; while (end >= 0) { //升序 if (a[end] >x) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = x; } }
解析
希爾排序在直接排序之前,進(jìn)行預(yù)排列,將某些極端數(shù)據(jù)更快的排列到數(shù)列前面,構(gòu)成一個(gè)接近排列好的序列,最后再進(jìn)行一次直接插入排序
預(yù)排列的原理也是插入排列,只不過(guò)這里的將數(shù)組分成了gap組,分別對(duì)每一個(gè)小組進(jìn)行插入排序
// 希爾排序 void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap /= 2; for (int i = 0; i < n - gap; i++) { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end-=gap; } else break; } a[end + gap] = x; } } }
當(dāng)gap > 1時(shí)都是預(yù)排序,目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí),數(shù)組已經(jīng)接近有序的了,這樣就會(huì)很快。這樣整體而言,可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比
解析
每一次遍歷待排序的數(shù)據(jù)元素從中選出最小(或最大)的一個(gè)元素,存放在序列的起始(或者末尾)位置,直到全部待排序的數(shù)據(jù)元素排完
代碼的實(shí)現(xiàn)
// 選擇排序 void SelectSort(int* a, int n) { int begin = 0, end = n - 1;//記錄下標(biāo) while (begin < end) { int mini = begin; for (int i = begin; i <= end; i++) { //遍歷找到最小數(shù)據(jù)并記錄下標(biāo) if (a[i] < a[mini]) mini = i; } Swap(&a[begin], &a[mini]);//交換 begin++;//縮小范圍 } }
總結(jié)
時(shí)間復(fù)雜度:O(N^2)
空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
不推薦使用
堆排序是指利用堆(數(shù)據(jù)結(jié)構(gòu))進(jìn)行選擇數(shù)據(jù)的一種排序算法
基礎(chǔ)思想:
原則:
先將原數(shù)組建成堆,需要注意的是排升序要建大堆,排降序建小堆
注:以大堆為例
建堆:
一個(gè)根節(jié)點(diǎn)與子節(jié)點(diǎn)數(shù)據(jù)如果不符合大堆結(jié)構(gòu),那么則對(duì)根節(jié)點(diǎn)數(shù)據(jù)進(jìn)行向下調(diào)整,而向下調(diào)整的前提是左右子樹(shù)也符合大堆結(jié)構(gòu),所以從堆尾數(shù)據(jù)的根節(jié)點(diǎn)位置開(kāi)始向下調(diào)整建大堆
排序:
大堆堆頂數(shù)據(jù)一定是待排數(shù)據(jù)中最大的,將堆頂數(shù)據(jù)與堆尾數(shù)據(jù)交換,交換后將除堆尾數(shù)據(jù)看成新堆,對(duì)現(xiàn)堆頂數(shù)據(jù)進(jìn)行向下調(diào)整成大堆,以此循環(huán)直至排列完畢
向下調(diào)整:
找到子節(jié)點(diǎn)中的較大數(shù)據(jù)節(jié)點(diǎn)比較,如果父節(jié)點(diǎn)數(shù)據(jù)比大子節(jié)點(diǎn)小則交換,直到不符合則停止向下交換,此時(shí)再次構(gòu)成了一個(gè)大堆結(jié)構(gòu).
代碼的實(shí)現(xiàn)
void Adjustdown(int* a, int n,int parent) { int child = parent * 2 + 1; while (child < n) { //找到數(shù)據(jù)大的子結(jié)點(diǎn) if (child + 1 < n && a[child + 1] > a[child]) { child++; } //父節(jié)點(diǎn)數(shù)據(jù)小于子節(jié)點(diǎn)就交換 if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); //更新下標(biāo) parent = child; child = parent * 2 + 1; } else//否則向下調(diào)整完畢 break; } } // 堆排序(升序)建大堆 void HeapSort(int* a, int n) { int i; //建大堆 for (i = (n - 1 - 1) / 2; i >= 0; i--) { Adjustdown(a, n, i); } //交換調(diào)整 for (i = n - 1; i >= 0; i--) { Swap(&a[0], &a[i]);//與當(dāng)前堆尾數(shù)據(jù)交換 Adjustdown(a, i, 0);//對(duì)交換后堆頂數(shù)據(jù)進(jìn)行向下調(diào)整 } }
總結(jié):
堆排序使用堆來(lái)選數(shù),效率就高了很多。
時(shí)間復(fù)雜度:O(N*logN)
空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
冒泡排序
每次遍歷數(shù)組,對(duì)相鄰數(shù)據(jù)進(jìn)行比較,不符合排序要求則交換
代碼的實(shí)現(xiàn)
// 冒泡排序 void BubbleSort(int* a, int n) { int i, j; for (i = 0; i < n - 1; i++)//趟數(shù) { for (j = 0; j < n - 1 - i; j++)//比較次數(shù) { if (a[j] > a[j + 1])//滿足條件 Swap(&a[j], &a[j + 1]);//交換 } } }
以上是“C語(yǔ)言中排序算法怎么用”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對(duì)大家有所幫助,如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。