1.之前介紹的冒泡和選擇排序都是適用于少量的資料，一旦資料量比較大，效率就很低的，因為他們的時間復雜度是O(n²），
2.今天介紹一種演算法不是很難，速度很快的排序演算法，快速排序，
一 快速排序
1）通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，
整個排序程序可以遞回執行，
2）排序程序動圖（來自百度百科）
3）步驟：
（1）設定兩個變數 i，j,令i=0,j=n-1
(2) 選擇一個元素作為分割點(key)，通常選第一個元素，令key=arrary[0]
(3) 從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A[j]，將A[j]和A[i]的值交換
(4) 從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]的值交換
(5) 重復第3、4步，直到i==j，此時排序完成
二 代碼
1 #include<stdio.h> 2 void quickSort(int *arr,int left,int right) 3 { 4 int i,j,temp; 5 i=left; 6 j=right; 7 if(i==j)//遞回結束條件 8 return; 9 temp=arr[left]; 10 while(j>i) 11 { 12 while(j>i&&arr[j]>=temp) 13 j--; 14 arr[i]=arr[j]; 15 while(i<j&&arr[i]<=temp) 16 i++; 17 arr[j]=arr[i]; 18 } 19 arr[j]=temp; 20 quickSort(arr,0,i);//遞回執行，對左半分進行排序 21 quickSort(arr,i+1,right);//遞回執行，對右半分進行排序 22 } 23 int main() 24 { 25 int i; 26 int arr[10]={1,3,-9,0,10,2,8,9,19,-1}; 27 quickSort(arr,0,9);//選擇排序 28 for(i=0;i<10;i++) 29 printf("%d\n",arr[i]); 30 return 0; 31 }
快速排序是冒泡排序的一種改進，的時間復雜度是O(nlog?n)，是線性級，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40809.html
標籤：C
上一篇：g++鏈接gcc編譯的庫報錯“undefined reference to xxx”
下一篇：POJ_Prob.ID：3255