C語言中如何實(shí)現(xiàn)排序

這篇文章將為大家詳細(xì)講解有關(guān)C語言中如何實(shí)現(xiàn)排序，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

1.冒泡排序

思路：比較相鄰的兩個(gè)數(shù)字，如果前一個(gè)數(shù)字大，那么就交換兩個(gè)數(shù)字，直到有序。

時(shí)間復(fù)雜度O(n^2)，穩(wěn)定性：這是一種穩(wěn)定的算法。

代碼實(shí)現(xiàn)：

void bubble_sort(int arr[],size_t len){ size_t i,j; for(i=0;i<len;i++){  bool hasSwap = false; //優(yōu)化，判斷數(shù)組是否已經(jīng)有序，如果有序可以提前退出循環(huán) for(j=1;j<len-i;j++){ //這里j<len-i是因?yàn)樽詈竺娴目隙ǘ际亲畲蟮?，不需要多進(jìn)行比較 if(arr[j-1]>arr[j]){ //如果前一個(gè)比后一個(gè)大 swap(&arr[j-1],&arr[j]); //交換兩個(gè)數(shù)據(jù) hasSwap = true; }  } if(!hasSwap){ break;  } }}

2.插入排序

思路：把一個(gè)數(shù)字插入一個(gè)有序的序列中，使之仍然保持有序，如對(duì)于需要我們進(jìn)行排序的數(shù)組，我們可以使它的前i個(gè)數(shù)字有序，然后再插入i+1個(gè)數(shù)字，插入到合適的位置使之仍然保持有序，直到所有的數(shù)字有序。

時(shí)間復(fù)雜度：O(n^2) 穩(wěn)定性：穩(wěn)定的算法

代碼實(shí)現(xiàn)：

void insert_sort(int arr[],int len){ int i,j; for(i=1;i<len;i++){ int key = arr[i]; //記錄當(dāng)前需要插入的數(shù)據(jù) for(j= i-1;i>=0&&arr[j]>key;j--){ //找到插入的位置 arr[j+1] = arr[j]; //把需要插入的元素后面的元素往后移 } arr[j+1] = key; //插入該元素 }}

3.折半插入排序

思路：本質(zhì)上是插入排序，但是通過半分查找法找到插入的位置，讓效率稍微快一點(diǎn)。

時(shí)間復(fù)雜度：O(n^2)，穩(wěn)定性：穩(wěn)定的算法。

代碼實(shí)現(xiàn)：

void half_insert_sort(int arr[],int len){ int i,j; for(i=1;i<len;i++){ int key = arr[i]; int left = 0; int right = i-1; while(left<=right){ //半分查找找到插入的位置 int mid = (left+right)/2; if(key<arr[mid]){ right = mid-1;  }else{ left = mid+1;  }  } for(j=i-1;j>=left;j--){ //把后面的元素往后移 arr[j+1]=arr[j];  } arr[j+1] = key; //插入元素 }}

4.希爾排序

思路：先取一個(gè)正整數(shù)d1<n，把所有序號(hào)相隔d1的數(shù)組元素放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2<d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹埂?/p>

時(shí)間復(fù)雜度：O(n^1.3) ,算法效率上大大提高 。穩(wěn)定性：不穩(wěn)定的算法。

代碼實(shí)現(xiàn)：

void shell_sort(int arr[],int len){ //本質(zhì)上也是一種插入排序，避免了大量數(shù)據(jù)的移動(dòng)，在每一組排序過后，每個(gè)數(shù)據(jù)已經(jīng)到了大致的位置。 int i,j; int step=0; for(step = len/2;step>=1;step=step/2){ //分組 分為step組,對(duì)每組的元素進(jìn)行插入排序 for(i=step;i<len;i++){ int key = arr[i]; for(j=i-step;j>=0&&arr[j]>key;j=j-step){ arr[j+step] = arr[j];  }  arr[j+step] = key; } }}

5.選擇排序

思路：通過循環(huán)找到最大值所在的位置，然后把最大值和最后一個(gè)元素進(jìn)行交換，通過循環(huán)直到所有的數(shù)據(jù)有序。時(shí)間復(fù)雜度：O(n^2) 穩(wěn)定性：不穩(wěn)定的算法

代碼實(shí)現(xiàn)：

void select_sort(int arr[],size_t len){ size_t i,j; for(i=0;i<len-1;i++){ int max = 0; //最大值下標(biāo) for(j=1;j<len-i;j++){ if(arr[max]<arr[j]){ //找到最大值的下標(biāo) max = j;  }  } if(max!=j-1){  swap(&arr[max],&arr[j-1]); //把最后一個(gè)元素和最大值進(jìn)行交換 } }}

6.雞尾酒排序

思路：選擇排序的一種改進(jìn)，一次循環(huán)直接找到最大值和最小值的位置，把最大值和最后一個(gè)元素進(jìn)行交換，最小值和最前一個(gè)元素進(jìn)行交換，所以最外層的循環(huán)只需要執(zhí)行l(wèi)en/2次即可

時(shí)間復(fù)雜度：O(n^2) 穩(wěn)定性：不穩(wěn)定的算法

代碼實(shí)現(xiàn)：

void cocktail_sort(int arr[],size_t len){ size_t i,j; for(i=0;i<len/2;i++){ int max = i; //最大值下標(biāo) int min = i; //最小值下標(biāo) for(j=i+1;j<len-i;j++){ if(arr[max]<arr[j]){ //找到最大值下標(biāo) max = j;  }  if(arr[min]>arr[j]){ //找到最小值下標(biāo) min = j;  } } if(max!=j-1){ swap(&arr[max],&arr[j-1]); //交換最大值和未進(jìn)行排序的最后一個(gè)元素 } if(min == j-1){ //如果最小值在未進(jìn)行排序的最后一個(gè)位置，那么經(jīng)過最大值的交換，已經(jīng)交換到了最大值所在的位置 min = max; //把最小值的坐標(biāo)進(jìn)行改變 } if(min!=i){ swap(&arr[i],&arr[min]); //交換最小值和未進(jìn)行排序的最前的元素 } }}

7.堆排序

思路：把數(shù)據(jù)進(jìn)行大堆化，然后依次交換堆頂(最大值)和最后一個(gè)元素,在使堆頂重新大堆化，最后循環(huán)過后數(shù)組便有序。過程：

最大堆調(diào)整（Max Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)創(chuàng)建最大堆（Build Max Heap）：將堆中的所有數(shù)據(jù)重新排序

堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算時(shí)間復(fù)雜度：O(nlgn) 穩(wěn)定性：不穩(wěn)定的算法

實(shí)現(xiàn)代碼：

void re_heap(int arr[],size_t index,size_t len){ size_t child = 2*index+1; //左節(jié)點(diǎn)坐標(biāo) int key = arr[index]; //當(dāng)前節(jié)點(diǎn)值 while(child<len){ if(child+1<len&&arr[child]<arr[child+1]){ //如果右節(jié)點(diǎn)存在且右節(jié)點(diǎn)的值比左節(jié)點(diǎn)大，那就child記錄較大字節(jié)點(diǎn)的坐標(biāo) child++;  }  if(arr[child]>key){ //如果子節(jié)點(diǎn)的值比根節(jié)點(diǎn)的值大 arr[index] = arr[child]; //改變根節(jié)點(diǎn)的值 }else{ break;  } index = child; child = 2*index+1; } arr[index] = key; //插入記錄好的值}void heap_sort(int arr[],size_t len){ int i; for(i=len/2;i>=0;i--){ re_heap(arr,i,len); //對(duì)第i個(gè)根節(jié)點(diǎn)進(jìn)行大堆化 } for(i=len-1;i>0;i--){ swap(&arr[0],&arr[i]); //交換第一個(gè)和最后一個(gè)元素 re_heap(arr,0,i); //對(duì)第一個(gè)元素進(jìn)行大堆化 }}

8.快速排序

思路：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。過程：

(1)首先設(shè)定一個(gè)分界值，通過該分界值將數(shù)組分成左右兩部分

(2)將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時(shí)，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。

(3)然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。

(4)重復(fù)上述過程，可以看出，這是一個(gè)遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當(dāng)左、右兩個(gè)部分各數(shù)據(jù)排序完成后，整個(gè)數(shù)組的排序也就完成了。時(shí)間復(fù)雜度：O(nlog2n) 穩(wěn)定性：不穩(wěn)定的算法

代碼實(shí)現(xiàn)：

void quick_sort(int arr[],size_t left,size_t right){ if(left>=right){ //如果只有一個(gè)元素，那就是有序的，返回 return;  } int i = left; int j = right; int key = arr[left]; //基準(zhǔn)值 while(i<j){ //找到基準(zhǔn)值的位置，使得基準(zhǔn)值右邊的元素都比基準(zhǔn)值大，左邊的元素都比基準(zhǔn)值小 while(i<j&&arr[j]>=key){ //從右邊找一個(gè)比基準(zhǔn)值小的數(shù)， --j; } arr[i] = arr[j];//把這個(gè)值放到基準(zhǔn)值的位置處 while(i<j&&arr[i]<=key){ //從左邊找一個(gè)比基準(zhǔn)值大的數(shù) ++i;  } arr[j] = arr[i]; //把這個(gè)元素放到j(luò)的位置 } arr[i] = key; if(i-left>1) //元素個(gè)數(shù)至少兩個(gè)才進(jìn)行遞歸調(diào)用，這樣可以少一次遞歸 quick_sort(arr,left,i-1); //對(duì)基準(zhǔn)值左邊的元素進(jìn)行排序 if(right-i>1) quick_sort(arr,i+1,right); //對(duì)基準(zhǔn)值右邊的元素進(jìn)行排序}

9.歸并排序

思路：對(duì)于兩個(gè)有序的子序列，可以把它們合并在一起，變成一個(gè)新的完全有序的序列，因此歸并排序和快排差不多，都是遞歸的進(jìn)行。時(shí)間復(fù)雜度：O(nlog2n) 穩(wěn)定性：穩(wěn)定的算法代碼實(shí)現(xiàn)：

void merge(int arr[],int left,int right){ int i,j,k; int mid = (left+right)/2; int len = mid-left+1; int *temp = malloc(sizeof(arr[0])*len); for(i=0;i<len;i++){ temp[i] = arr[i+left]; //把這個(gè)數(shù)組的所有元素都復(fù)制到臨時(shí)數(shù)組中 } i=0,j=mid+1,k=left; while(i<len&&j<=right){ if(temp[i]<arr[j]){ //把臨時(shí)數(shù)組的元素和 [mid+1,right]這部分的元素一個(gè)一個(gè)的進(jìn)行比較，如果誰小，那么arr里就存放誰的元素 arr[k++] = temp[i++];  }else{ arr[k++] = arr[j++];  } } while(i<len){ //如果temp這個(gè)數(shù)組的元素還沒有全部遍歷完，那就把temp后面的元素都復(fù)制到arr里面去， //因?yàn)閍rr[mid+1,right] 這部分的元素本來就是arr后面部分的有序的元素，所以如果arr[mid+1,right]這部分沒有遍歷完也沒關(guān)系的， arr[k++] = temp[i++];  } free(temp);}void merge_sort(int arr[],int left,int right){ if(left>=right){ //如果只有一個(gè)元素說明這個(gè)序列有序，那就返回 return;  }  int mid = (left+right)/2; //對(duì)兩個(gè)有序的數(shù)組進(jìn)行排序， merge_sort(arr,left,mid); //對(duì)[left,mid]這個(gè)區(qū)間的元素進(jìn)行排序 merge_sort(arr,mid+1,right); //對(duì)[mid+1,right]這個(gè)區(qū)間內(nèi)的元素進(jìn)行排序 merge(arr,left,right); //這個(gè)序列的[left,mid]為有序的序列 [mid+1,right]也為有序的序列}

10.計(jì)數(shù)排序

思路：這是一種基于比較的算法，我們用一個(gè)大數(shù)組來存放這些數(shù)據(jù)，這些數(shù)據(jù)在這個(gè)大數(shù)組中的表現(xiàn)形式是以這個(gè)大數(shù)組的下標(biāo)存在的，比如57,60,42這三個(gè)數(shù)字進(jìn)行排序，那么用一個(gè)大數(shù)組，這個(gè)大數(shù)組的arr[57] = 1,arr[60] = 1,arr[42] = 1，然后遍歷這個(gè)大數(shù)組就行了。

時(shí)間復(fù)雜度：O(n+k),其中這個(gè)k為數(shù)據(jù)的范圍，所以計(jì)數(shù)排序最適合數(shù)據(jù)比較集中的數(shù)組排序。穩(wěn)定性：穩(wěn)定的算法

代碼實(shí)現(xiàn)：

void count_sort(int arr[],size_t len){ int max = arr[0]; //最大值 int min = arr[0]; //最小值 size_t i; for(i=0;i<len;i++){ if(max<arr[i]){ //找到最大值 max =arr[i];  } if(min > arr[i]){ //找到最小值 min = arr[i];  } } int cnt = max-min+1; //范圍 int *prr = malloc(cnt*sizeof(int)); //申請(qǐng)臨時(shí)空間 for(i=0;i<cnt;i++){ //這個(gè)臨時(shí)數(shù)組全部置0 prr[i] = 0;  } for(i=0;i<len;i++){ //對(duì)需要進(jìn)行排序的序列進(jìn)行遍歷 prr[arr[i]-min]++; //讓下標(biāo)為(arr[i]-min)的臨時(shí)大數(shù)組的值+1 } size_t j=0; for(i=0;i<cnt;i++){ //遍歷這個(gè)臨時(shí)數(shù)組 while(prr[i]){ //如果這個(gè)數(shù)組下標(biāo)為i的值不等于0 arr[j++] = i+min; //那就讓需要進(jìn)行排序的數(shù)組的值為i+min; --prr[i]; }  } free(prr); //釋放掉申請(qǐng)的動(dòng)態(tài)內(nèi)存}

11.桶排序

思路：工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。這是一種以消耗大量空間來換取高效率的排序方式，時(shí)間復(fù)雜度：O(N+C)，其中C=N*(logN-logM)，M為桶的數(shù)量。所以對(duì)于桶排序，桶的數(shù)量越多，其排序效率越高。穩(wěn)定性：穩(wěn)定的算法代碼實(shí)現(xiàn)：首先定義桶這個(gè)類型：

typedef struct Bucket{ int vect[100]; //其實(shí)這里使用鏈表更好，但是我比較懶，就懶得用鏈表了 int cnt; //當(dāng)前桶內(nèi)存放數(shù)據(jù)的個(gè)數(shù)}

Bucket;

void bucket_sort(int arr[],size_t len){ int min = arr[0]; int max = arr[0]; size_t i; for(i=0;i<len;i++){ if(min>arr[i]){ //找到最小值 min = arr[i];  } if(max<arr[i]){ //找到最大值 max = arr[i];  } } int size = max-min+1; Bucket bucket[5] = {}; //其實(shí)桶可以動(dòng)態(tài)規(guī)劃，但為了方便我這里直接分為5個(gè)桶 for(i=0;i<len;i++){ //遍歷待排序的數(shù)組，把每個(gè)元素放到相應(yīng)的桶當(dāng)中， //比如[0,200]之間的元素放到下標(biāo)為0的桶中，[201,400]之間的元素放到下標(biāo)為1的桶中.. //以此類推，直到放完所有的數(shù)據(jù) int index = (arr[i]-min)/(size/5); //用來判斷當(dāng)前元素arr[i]需要放到哪個(gè)桶當(dāng)中 bucket[index].vect[bucket[index].cnt++] = arr[i]; } size_t j=0,k=0; for(i=0;i<5;i++){ //對(duì)這五個(gè)桶進(jìn)行遍歷 count_sort(bucket[i].vect,bucket[i].cnt); //首先對(duì)這個(gè)桶內(nèi)的元素進(jìn)行排序， //這里可以調(diào)用其他排序方法，也可以遞歸調(diào)用當(dāng)前排序方法，但是為了節(jié)省內(nèi)存，我選擇調(diào)用其他排序方法， for(j=0;j<bucket[i].cnt;j++){ arr[k++] = bucket[i].vect[j]; //對(duì)排序好的桶進(jìn)行遍歷，并且把里面的元素復(fù)制到arr中去  } }}

12.基數(shù)排序

基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog&reg;m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。

解法：

1.首先根據(jù)個(gè)位數(shù)的數(shù)值，在走訪數(shù)值時(shí)將它們分配至編號(hào)0到9的桶子中； 2.接下來將這些桶子中的數(shù)值重新串接起來，接著再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配； 3.接下來將這些桶子中的數(shù)值重新串接起來，持續(xù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止。時(shí)間復(fù)雜度：設(shè)待排序列為n個(gè)記錄，d個(gè)關(guān)鍵碼，關(guān)鍵碼的取值范圍為radix，則進(jìn)行鏈?zhǔn)交鶖?shù)排序的時(shí)間復(fù)雜度為O(d(n+radix))，其中，一趟分配時(shí)間復(fù)雜度為O(n)，一趟收集時(shí)間復(fù)雜度為O(radix)，共進(jìn)行d趟分配和收集。穩(wěn)定性：穩(wěn)定的算法；

代碼實(shí)現(xiàn)：

還是定義桶的類型：

typedef struct Bucket{ int vect[100]; //同樣的可以用鏈表 int cnt;}Bucket;void base_sort(int arr[],size_t len){ size_t i; Bucket bucket[10] = {}; //十個(gè)桶 int max = arr[0]; for(i=0;i<len;i++){ //尋找最大值，就可以判斷最大值的位數(shù) if(arr[i]>max){ max = arr[i];  }  } size_t j,k; int num = 1; //用來獲得相應(yīng)位數(shù)上的數(shù)字的關(guān)鍵參數(shù)， //比如要獲得個(gè)位上的參數(shù)時(shí)num = 1; //獲得十位上的數(shù)字時(shí)num = 10; //以此類推 do{ for(i=0;i<len;i++){ //遍歷待排序的數(shù)組，把每個(gè)元素放入相應(yīng)的桶中 //比如251，當(dāng)獲得個(gè)位上的數(shù)字時(shí)，251放到下標(biāo)為1的桶當(dāng)中 //當(dāng)獲得十位上的數(shù)字時(shí),251放到下標(biāo)為5的桶當(dāng)中 //當(dāng)獲得百位上的數(shù)字時(shí),251放到下標(biāo)為2的桶當(dāng)中 //當(dāng)獲得千位上的數(shù)字時(shí),251放到下標(biāo)為0的桶當(dāng)中 //以此類推 int index = arr[i]/num%10; //獲得相應(yīng)位數(shù)上的數(shù)字 bucket[index].vect[bucket[index].cnt++] = arr[i]; //把這個(gè)數(shù)字放到相應(yīng)的桶中 } k=0; for(i=0;i<10;i++){ for(j=0;j<bucket[i].cnt;j++){ arr[k++] = bucket[i].vect[j]; //把這些桶按順序依次遍歷， //把桶中的元素重新放回arr當(dāng)中 }  bucket[i].cnt = 0; //記得讓桶中的cnt變?yōu)?,方便下一次存放 } num*=10; //num*10 }while(max/=10);//循環(huán)條件}

關(guān)于C語言中如何實(shí)現(xiàn)排序就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。