简单分析几个常见的排序算法（C语言）
目錄
1.冒泡排序：
冒泡排序簡單優化：
2.簡單選擇排序：
3.直接插入排序：
插入排序優化：二分插入排序
4.希爾排序（直接插入排序的一種優化）：
5.快速排序：
swap(int *a,int *b){int temp=*a;*a=*b;*b=temp; }
? ? ? ? ? ? ? ? ? ? （為方便閱讀代碼，每段代碼前定義這個函數用來交換兩個數。）
1.冒泡排序：
? -冒泡排序的基本思想：兩兩比較相鄰記錄的關鍵字，若反序則交換，直到沒有反序的記錄為止。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??↓基本代碼↓
int main(){int num=10,i,j;int a[num]={2,9,8,3,4,8,1,7,5,6};for(i=0;i<num-1;i++){for(j=0;j<num-i-1;j++){if(a[j]>a[j+1])swap(&a[j],&a[j+1]);}}for(i=0;i<num;i++)printf("%d ",a[i]); }? ? ? （這樣的冒泡程序存在一個缺點，即序列在循環過程中有序后程序仍會繼續進行。）
冒泡排序簡單優化：
? ? ? ? 增加一個標記變量flag，讓序列有序后自動停止。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?↓優化后的代碼↓
int main(){int num=10,i,j,flag=1;int a[num]={2,9,8,3,4,8,1,7,5,6};for(i=0;i<num-1;i++){if(flag==0)break;flag = 0;for(j=0;j<num-i-1;j++){if(a[j]>a[j+1]){swap(&a[j],&a[j+1]);flag = 1;}}}for(i=0;i<num;i++)printf("%d ",a[i]); }2.簡單選擇排序：
-選擇排序的基本思想：每一趟在n-i（i = 0,1......n-2）個記錄中選取關鍵字最小的記錄作為有序序列的第i+1個記錄。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ↓基本代碼↓
int main(){int num=10,i,j,min;int a[num]={2,9,8,3,4,8,1,7,5,6};for(i=0;i<num;i++){min = i;for(j=i;j<num;j++){if(a[min]>a[j])min=j;}if(i!=min)swap(&a[i],&a[min]);}for(i=0;i<num;i++)printf("%d ",a[i]); }分析：從過程來看，簡單選擇排序的最大特點是交換移動數據的次數很少。
3.直接插入排序：
-直接插入排序的基本思想：將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數增1的有序表。
形象的描述如圖：設初始數列為5 3 4 6 2 設s[6]={0,5,3,4,6,2}
數列下標 s[0] s[1] s[2] s[3] s[4] s[5](設置s[0]作為跳板，默認s[1]已經放好位置) 初始數列 X 5 3 4 6 2 第一次排序 3 5 X 4 6 2 (比較a[2]與a[1]→3比5小故將3放在a[0] )X 3 5 4 6 2 (通過for循環將數列調整并復原)第二次排序 4 3 5 X 6 2 (比較a[3]與a[2]→4比5小故放在a[0] )X 3 4 5 6 2 (通過for循環將數列調整并復原)第三次排序 X 3 4 5 6 2 (比較a[4]與a[3]→6比5大故不進行操作) 第四次排序 2 3 4 5 6 X (比較a[5]與a[3]→2比6小故放在a[0] )X 2 3 4 5 6 (通過for循環將數列調整并復原，數列有序)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ↓基本代碼↓
#include <stdio.h> int main(){int s[6]={0,5,3,4,6,2}; //建立數組，注意設置跳板s[0]。 int i,j;for(i=2;i<6;i++){if(s[i]<s[i-1]){ //s[i]>s[i-1]才進行操作。 s[0]=s[i]; //s[0]賦值。 for(j=i-1;s[j]>s[0];j--)s[j+1]=s[j]; s[j+1]=s[0]; //這兩行目的是調整并后移記錄。 }} }分析：與上述兩個排序方法相比，相同的時間復雜度，直接插入排序的性能更好。
插入排序優化：二分插入排序
????????由于在直接插入排序過程中，待插入數據左邊的序列總是有序的，針對有序序列，就可以用二分法去插入數據了，也就是二分插入排序法。適用于數據量比較大的情況。
-二分插入排序法基本思想：（1）計算 0 ~ i-1 的中間點，用 i 索引處的元素與中間值進行比較，如果 i 索引處的元素大，說明要插入的這個元素應該在中間值和剛加入i索引之間，反之，就是在剛開始的位置 到中間值的位置，這樣很簡單的完成了折半；
（2）在相應的半個范圍里面找插入的位置時，不斷的用（1）步驟縮小范圍，不停的折半，范圍依次縮小為 1/2 1/4 1/8 .......快速的確定出第 i 個元素要插在什么地方；
（3）確定位置之后，將整個序列后移，并將元素插入到相應位置。
4.希爾排序（直接插入排序的一種優化）：
前言：
????????直接插入排序在記錄少或序列內基本有序時效率高，但當序列數目大，序列非常無序時效率一般。
????????這時可以考慮將整個序列分割成多個子序列，在這些子序列內分別進行插入排序。但例如數列{ 9，1，5，8，3，7，4，6，2 }，分成三組{ 9，1，5 }，{ 8，3，7 }，{ 4，6，2}排序再組合之后的{ 1，5，9，3，7，8，2，4，6 }仍然雜亂無章。此時就可以考慮跳躍分割的思想，就有了希爾排序。
-希爾排序基本思想：跳躍分割，即將相距某個“增量”的記錄組成一個子序列后再排序，這樣就保證了在子序列內分別進行直接插入排序后得到的結果是基本有序而不是局部有序。（如圖所示）??
? ?
?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ↓基本代碼↓
void Shellsort(arry[],int length) {int i,j,k=0;int increment=length; //設置增量increment do{increment=increment/3+1; //增量每次取之前的三分之一 for(i=increment;i<=length;i++) //分組進行插入排序 {if(arry[i]<arry[i-increment]){arry[0]=arry[i];for(j=i-increment;j>0 && arry[0]<arry[j];j-=increment)arry[i+increment]=arry[j];arry[j+increment]=r[0];}}} }5.快速排序：
-快速排序基本思想：通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，最終使整個序列有序。
（簡單來說，就是先任選一個數作為支點pivot，將剩下的數分成比pivot大和比pivot小的兩部分，小的部分放左邊，大的部分放右邊。若有一個部分只剩一個數，則這部分排序結束。否則繼續對兩部分分別重復上述操作直到整個序列有序。）
-代碼實現：（以數組arry[6]=19,97,9,17,1,8為例）
? ? ? ? 1.選取兩個下標L（left）和R（right），分別對應數組第一個數和最后一個數。
? ? ? ? 2.方便起見，將第一個數也就是arry[0]作為pivot。此時可以認為arry[0]是空的（如圖所示）。
? ? ? ? ? ? ? ? ? ?? ? ? ??
? ? ? ? ?3.判斷R指向的數：若小于pivot則將R指向的數放在L，然后進行第4步；若大于pivot則數不動，R向左退一位，重新進行第3步。直到L與R重合，將pivot放在重合的位置。
? ? ? ? 4.判斷L指向的數：若大于pivot則將L指向的數放在R，然后進行第3步；若小于pivot則數不動，R向右進一位，重新進行第4步。直到L與R重合，將pivot放在重合的位置。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （如圖所示）
?? ? ? ? ? ? ? ? ? ? ?? ? ?
? ? ? ? 5.重復上述操作直到數列有序。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ↓基本代碼↓
void Quicksort(int arry[],int L,int R){ //輸入數組，最前下標，最后下標 if(L>=R) return;int left=L,right=R;int pivot = arry[left]; //將arry[0]作為第一輪比較的關鍵數while(left<right){ //可將這個循環分成兩個部分 ①和 ②while(left<right&&arry[right]>=pivot) //部分 ① 大于pivot則數不動，R向左退一位{right--;}if(left<right){arry[left]=arry[right];}while(left<right&&arry[left]<=pivot) //部分 ② 小于pivot則數不動，R向右進一位{left++;}if(left<=right){arry[right]=arry[left];}if(left>=right){arry[left]=pivot;}}Quicksort(arry,L,right-1);Quicksort(arry,right+1,R);//對兩個部分重新進行排序 }分析：快速排序的優點是排序速度快。但這個操作有個缺點，即若取得的pivot是數組中較小或較大的數，會增加很多計算量。
簡單優化：三數取中，即取序列左端，中間，右端三個數進行排序，將中間值作為pivot，與數組最左端值交換，其他步驟相同。這個操作大概率減少了不必要的交換。
總結
以上是生活随笔為你收集整理的简单分析几个常见的排序算法（C语言）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： VMDNS服务器未响应,vmware克隆
- 下一篇： 11.10错题集（7-函数）