您好,登錄后才能下訂單哦!
這篇文章主要介紹“C語(yǔ)言中有哪些簡(jiǎn)單的排序算法”的相關(guān)知識(shí),小編通過(guò)實(shí)際案例向大家展示操作過(guò)程,操作方法簡(jiǎn)單快捷,實(shí)用性強(qiáng),希望這篇“C語(yǔ)言中有哪些簡(jiǎn)單的排序算法”文章能幫助大家解決問(wèn)題。
冒泡排序是一個(gè)非常好理解的排序,顧名思義——冒泡,此時(shí)將要排序的數(shù)據(jù)從上至下排列,從最上面的數(shù)(第一個(gè)數(shù)據(jù))開(kāi)始對(duì)相鄰的兩個(gè)數(shù)據(jù)進(jìn)行比較,較小的數(shù)據(jù)往上浮,較大的數(shù)據(jù)往下沉,達(dá)到排序的效果。
(1)對(duì)每一對(duì)相鄰的元素進(jìn)行比較,若第一個(gè)比第二個(gè)大,則調(diào)換這兩個(gè)元素的位置,依次兩兩比較直到數(shù)據(jù)的最后一對(duì),此為一輪操作。
(2)重復(fù)n輪此操作(n為元素的個(gè)數(shù)),不過(guò)每輪結(jié)束后的最后一個(gè)元素不用參與下一輪的比較,因?yàn)榻?jīng)歷一輪排序后,最后一個(gè)元素一定比前面所有的元素都要大。
(3)因此每一輪需要比較的元素都在減少,一直到?jīng)]有數(shù)可比較為止。(不過(guò)為了減少比較次數(shù),可以記錄每輪是否有數(shù)據(jù)的交換,如果沒(méi)有交換,表明當(dāng)前數(shù)據(jù)已經(jīng)按從小到大的順序拍好了,可直接跳出循環(huán))
#include<stdio.h> int main() { int n, m, i, j, temp; int arr[100]; scanf_s("%d", &n); //scnaf_s是更為安全的輸入方式;n為元素的個(gè)數(shù); for (i = 0; i < n; i++) { scanf_s("%d", &arr[i]); //輸入數(shù)據(jù); } m = n; //因?yàn)槊窟M(jìn)行一次第一輪循環(huán),需要排序的數(shù)據(jù)都要“--”,因此定義變量m=n; for (i = 0; i < n; i++) { int exchange = 0; //記錄這一輪會(huì)不會(huì)有數(shù)據(jù)的交換; for (j = 0; j < m-1; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; exchange = 1; } } m--; if (!exchange) //若沒(méi)有數(shù)據(jù)的交換,則數(shù)據(jù)已經(jīng)排列完畢,跳出循環(huán); break; } for (i = 0; i < n; i++) { printf("%d ", arr[i]); //輸出 } return 0; }
快速排序是這五類(lèi)中平均性能最優(yōu)的排序算法,其中運(yùn)用了分治的思想,并且調(diào)用了遞歸函數(shù),因此也是這五類(lèi)中最難的一個(gè)。
快速排序的重點(diǎn)在于找一個(gè)基準(zhǔn)值,將數(shù)列分為兩部分——大于基準(zhǔn)值的放在右邊,小于基準(zhǔn)值的 放在左邊。然后分別對(duì)這兩部分重復(fù)次操作,一分為二,二分為四······直到每個(gè)元素自成一部分。
1.將數(shù)據(jù)的中間元素設(shè)為基準(zhǔn)值,初始化令 指向最左邊個(gè)元素,令 指向最右邊個(gè)元素,通過(guò)從左往右找一個(gè)大于基準(zhǔn)數(shù)的數(shù),通過(guò)從右往左找一個(gè)小于基準(zhǔn)數(shù)的數(shù),交換兩數(shù)的位置,直到。
2.如此不斷的細(xì)分遞歸,達(dá)到排序的目的
#include<stdio.h> void Quicksort(int a[], int left, int right) { //快排函數(shù) int temp; int mid = a[(left + right) / 2]; //找基準(zhǔn)值 int i = left; int j = right; //在左側(cè)找一個(gè)大于基準(zhǔn)值的數(shù),在右側(cè)找一個(gè)小于基準(zhǔn)數(shù)的數(shù),然后交換位置 while (i <= j) { while (a[i] < mid) i++; while (a[j] > mid) j--; if (i <= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } } if (i < right) Quicksort(a, i, right); //遞歸 if (j > left) Quicksort(a, left, j); //遞歸 } int main() { int n, m, i; int arr[100]; scanf_s("%d", &n); for (i = 0; i < n; i++) { scanf_s("%d", &arr[i]); //輸入 } Quicksort(arr, 0, n - 1); //調(diào)用函數(shù) for (i = 0; i < n; i++) { printf("%d ", arr[i]); //輸出 } return 0; }
將數(shù)據(jù)分為兩組——一組是有序的,一組是無(wú)序的,將無(wú)序數(shù)據(jù)中的元素依次插入到有序數(shù)據(jù)中,從而將整個(gè)數(shù)據(jù)變?yōu)橛行虻模ㄟ@里的分組是潛意識(shí)的,實(shí)際上并不會(huì)用兩個(gè)數(shù)組來(lái)分)
1.初始時(shí),將第一個(gè)元素分為有序組(因?yàn)橹挥幸粋€(gè)元素,所以認(rèn)為它是排好序的),其余元素分為無(wú)序組
2.因此只需從第二個(gè)元素開(kāi)始,依次在有序組中找到自己的位置,插入即可,直到最后一個(gè)元素。
3.但這并不意味著只需要一次循環(huán),因?yàn)樵凇罢易约旱奈恢谩钡倪^(guò)程中,需要將自己與前面的元素相比較,若是自己較小,則將那個(gè)元素后移一位;若是自己較大,則將自己插入到上一次比較的位置
#include<stdio.h> int main() { int n, m, i, j, temp; int arr[100]; scanf_s("%d", &n); for (i = 0; i < n; i++) { scanf_s("%d", &arr[i]); //輸入 } for(i=1; i<n; i++) //從無(wú)序組的第一個(gè)元素開(kāi)始 if(arr[i] < arr[i-1]) // 判斷是否要向前尋找插入的位置 { int temp = arr[i]; for(j=i-1; j>=0 && arr[j]>temp; j--) //將大于自己的數(shù)依次向后挪位 arr[j+1] = arr[j]; arr[j+1] = temp; //插入 } for (i = 0; i < n; i++) { printf("%d ", arr[i]); //輸出 } return 0; }
設(shè)一個(gè)數(shù)據(jù)集有n個(gè)元素,選擇這n個(gè)元素中最小的一個(gè)與第一個(gè)元素交換位置,再在剩下的n-1個(gè)元素中選擇最小的一個(gè)與第二個(gè)元素交換位置,直到在最后兩個(gè)元素中選擇最小的一個(gè)放在倒數(shù)第二的位置上,排序完成。
#include<stdio.h> int main() { int n, m, i, j, p, temp; int arr[100]; scanf_s("%d", &n); for (i = 0; i < n; i++) { scanf_s("%d", &arr[i]); //輸入 } for (i = 0; i < n - 1; i++) { p = i; //p用于記錄最小元素的下標(biāo) for (j = i + 1; j < n; j++) { //找到剩下元素中最小的那一個(gè) if (arr[p] > arr[j]) p = j; } temp = arr[i]; //temp是交換兩數(shù)時(shí)的中間變量 arr[i] = arr[p]; arr[p] = temp; } for (i = 0; i < n; i++) { printf("%d ", arr[i]); //輸出 } return 0; }
希爾排序是插入排序的優(yōu)化,它先將待排序列進(jìn)行預(yù)排序,然后對(duì)次序列進(jìn)行一次插入排序,不一樣的是經(jīng)過(guò)預(yù)處理之后的插入排序時(shí)間復(fù)雜度為
定義一個(gè)間隔gap,在一組數(shù)據(jù)中,將相隔為gap的元素作為一個(gè)組,對(duì)組內(nèi)元素執(zhí)行簡(jiǎn)單的插入排序,然后不斷縮小gap重復(fù)此操作,完成數(shù)據(jù)的預(yù)處理,直到gap=1,表示對(duì)所有數(shù)進(jìn)行插入排序,算法終止。
1.初始化(n為元素個(gè)數(shù)),將數(shù)據(jù)中所有距離為gap的元素分在一組(此時(shí)這組數(shù)據(jù)會(huì)被分成個(gè)組,每組有兩個(gè)元素,對(duì)每個(gè)組進(jìn)行排序)
2.接著縮小gap至,將數(shù)據(jù)中所有距離為gap的元素分在一組(此時(shí)這組數(shù)據(jù)會(huì)被分成個(gè)組,每組有四個(gè)元素,對(duì)每個(gè)組進(jìn)行排序)
3.重復(fù)直到gap=1,此時(shí)數(shù)據(jù)為一組,有n個(gè)元素,簡(jiǎn)單插入排序即可。
#include<stdio.h> int main() { int n, m, i, j, temp,gap; int arr[100]; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &arr[i]); //輸入 } for(gap=n/2; gap>0; gap/=2) for(i=gap; i<n; i++) for(j=i-gap; j>=0 && arr[j]>arr[j+gap]; j-=gap){ temp=arr[j]; arr[j]=arr[j+gap]; arr[j+gap]=temp; } for (i = 0; i < n; i++) { printf("%d ", arr[i]); //輸出 } return 0; }
關(guān)于“C語(yǔ)言中有哪些簡(jiǎn)單的排序算法”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí),可以關(guān)注億速云行業(yè)資訊頻道,小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。
免責(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)容。