1、算法描述

　　快速排序也是基于分治模式的，下面是一個典型子數組A[p..r]排序的分治過程，主要分為三個步驟：

　　（1）分解：將數組A[p..r]劃分成兩個子數組A[p...q-1]和A[q+1...r],使得前一個數組中每個值都小于等于A[q]，后一個數組每個值都大于A[q],下標q也在這個分解過程中求得。

　　（2）解決：通過遞歸調用對兩個子數組分別進行排序。

　　（3）合并：兩個子數組是就地進行排序的，所以他們的合并并不需要操作，這個數組已經有序了。。

2、具體實現：

　　形參和實參的區別：

　　（1）實現一：

View Code 1 #include<stdio.h> 2 int partition(int *ptr,int p,int r)//一次劃分過程 3 { 4 int i,j,temp; 5 int x=*(ptr+r-1); 6 i=p-1; 7 for(j=p;j<r;j++) 8 { 9 if(*(ptr+j-1)<=x) 10 { 11 i++; 12 temp=*(ptr+j-1); 13 *(ptr+j-1)=*(ptr+i-1); 14 *(ptr+i-1)=temp; 15 } 16 } 17 i++; 18 temp=*(ptr+i-1); 19 *(ptr+i-1)=*(ptr+r-1); 20 *(ptr+r-1)=temp; 21 return(i); 22 } 23 void quicksort(int *ptr,int p,int r)//遞歸排序 24 { 25 int q; 26 if(p<r) 27 { 28 q=partition(ptr,p,r); 29 quicksort(ptr,p,q-1); 30 quicksort(ptr,q+1,r); 31 } 32 } 33 void main() 34 { 35 int a[8]={2,8,7,1,3,5,6,4}; 36 quicksort(a,1,8); 37 for(int i=0;i<8;i++) 38 printf("%d ",a[i]); 39 }

　　（2）實現二：

View Code 1 #include<stdio.h> 2 int partition(int ptr[],int p,int r)//一次劃分過程 3 { 4 int i,j,temp; 5 int x=ptr[r-1]; 6 i=p-1; 7 for(j=p;j<r;j++) 8 { 9 if(ptr[j-1]<=x) 10 { 11 i++; 12 temp=ptr[j-1]; 13 ptr[j-1]=ptr[i-1]; 14 ptr[i-1]=temp; 15 } 16 } 17 i++; 18 temp=ptr[i-1]; 19 ptr[i-1]=ptr[r-1]; 20 ptr[r-1]=temp; 21 return(i); 22 } 23 void quicksort(int ptr[],int p,int r)//遞歸排序 24 { 25 int q; 26 if(p<r) 27 { 28 q=partition(ptr,p,r); 29 quicksort(ptr,p,q-1); 30 quicksort(ptr,q+1,r); 31 } 32 } 33 void main() 34 { 35 int a[8]={2,8,7,1,3,5,6,4}; 36 quicksort(a,1,8); 37 for(int i=0;i<8;i++) 38 printf("%d ",a[i]); 39 }

?

總結

以上是生活随笔為你收集整理的【算法导论】第7章快速排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。