[基础算法复习]快速排序

最基础的快速排序
优点:编码简单,清晰
缺点:对于排好序的输入,时间复杂度为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;
}






posted on 2009-07-14 21:58 YZY 阅读(291) 评论(0)  编辑 收藏 引用 所属分类: Algorithm基础算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜