最基礎(chǔ)的快速排序
優(yōu)點(diǎn)：編碼簡單，清晰
缺點(diǎn)：對(duì)于排好序的輸入，時(shí)間復(fù)雜度為O(n^2)
static?int?partition(int?*array,int?start,int?end);
int?quicksort(int?*array,int?start,int?end)
{
????if(array==NULL||start>end)?return?0;
????int?t?=?partition(array,start,end);
????quicksort(array,start,t-1);
????quicksort(array,t+1,end);
????return?1;
}
static?int?partition(int?*array,int?start,int?end)
{
????int?pivot?=?array[start];????
????int?i?=?start;
????int?j?=?end;
????while(?i<j?){
????????while( j>i&& array[j]>=pivot)?j--;
????????array[i]?=?array[j];
????????while( j>i&& array[i]<=pivot )?i++;
????????array[j]?=?array[i];
????}
????array[i]?=?pivot;
????return?i;
}
改進(jìn)：小數(shù)組直接用插入排序?qū)崿F(xiàn)，中樞值取(begin,mid,end)三者的中間值，對(duì)有序數(shù)組排序仍為O(nlogn)。減少了邊界條件檢查
缺點(diǎn)：編碼復(fù)雜。
#include?<stdio.h>
#include?<stdlib.h>
#include?<memory.h>
#define?SMALL_N?10
static?int?partition(int?*array,int?begin,int?end);
void?_quicksort(int?*array,int?begin,int?end);
void?insertsort(int?*array,int?len)
{
????int?i;
????if(array==NULL||len==0)
????????return;
????for(i=1;i<len;++i){
????????int?temp?=?array[i];
????????int?j;
????????for(j=i;j>=1&&temp<array[j-1];--j){
????????????array[j]?=?array[j-1];
????????}
????????array[j]?=?temp;
????}
}
int?quicksort(int?*array,int?len)
{
????if(array==NULL||len==0)
????????return;
????_quicksort(array,0,len-1);
}
void?_quicksort(int?*array,int?begin,int?end)
{
????int?pivot;
????int?pivot_pos;
????if(end-begin+1<=SMALL_N){
????????insertsort(&array[begin],end-begin+1);
????????return;
????}
????pivot_pos?=?partition(array,begin,end);
????_quicksort(array,begin,pivot_pos-1);
????_quicksort(array,pivot_pos+1,end);
}
static?int??mid3(int?*array,int?begin,int?end)
{
????int?mid?=?(end-begin)/2+begin;
????int?tmp;
????tmp?=?array[mid];
????if(tmp<array[begin]){
????????array[mid]?=?array[begin];
????????array[begin]?=?tmp;
????}
????tmp?=?array[end];
????if(tmp<array[mid]){
????????array[end]?=?array[mid];
????????if(tmp<array[begin]){
???????????array[mid]?=?array[begin];
???????????array[begin]?=?tmp;
????????}
????????else{
????????????array[mid]?=?tmp;
????????}
????}
????tmp?=?array[end-1];
????array[end-1]?=?array[mid];
????array[mid]?=?tmp;
????
????return?array[end-1];
}
static?int?partition(int?*array,int?begin,int?end)
{
????int?pivot?=?mid3(array,begin,end);
????int?i,?j;
????int?tmp;
????i?=?begin;
????j?=?end-1;
????while(1){
????????while(array[++i]<pivot)?;
????????while(array[--j]>pivot)?;
???????
???????if(i>j)
??????????break;
???????tmp?=?array[j];
???????array[j]?=?array[i];
???????array[i]?=?tmp;
????}
????tmp?=?array[i];
????array[i]?=?array[end-1];
????array[end-1]?=?tmp;
????return?i;
}