最基础的快速排序
优点：编码简单，清晰
缺点：对于排好序的输入，时间复杂度为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;
}
改进：小数组直接用插入排序实现，中枢值取(begin,mid,end)三者的中间值，对有序数组排序仍为O(nlogn)。减少了边界条件检查
缺点：编码复杂。
#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;
}