个人技术笔记

快速排序

发布时间：2015-11-24  栏目：软件算法  评论：0 Comments

快速排序法原理也是用了分治法，主要原理是将数组分为A[p..q-1] 和A[q+1..r]，然后调整元素使得A[p..q-1]小于等于q，也小于等于A[q+1..r]。然后不断的递归，到最后就排序完成。

 
#include
#include

size_t partition(int* datas,int beg,int last);
void quick_sort(int* datas,int beg,int last);
void swap(int *a,int *b);

int main()
{
size_t i;
int datas[10] = {78,13,9,23,45,14,35,65,56,79};
printf(“After quick sort,the datas is:\n”);
quick_sort(datas,0,9);
for(i=0;i<10;++i)
printf(“%d “,datas[i]);
printf(“\n”,datas[i]);
exit(0);
}

void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

size_t partition(int* datas,int beg,int last)
{
int pivot = datas[last];
int i,j;
i = beg -1;
for(j=beg;j<last;j++)
{
if(datas[j] < pivot)
{
i = i+1;
swap(datas+i,datas+j);
}
}
swap(datas+i+1,datas+last);
return (i+1);
}

void quick_sort(int* datas,int beg,int last)
{
int pivot;
if(beg < last)
{
pivot = partition(datas,beg,last);
quick_sort(datas,beg,pivot-1);
quick_sort(datas,pivot+1,last);
}

}

 

 

其中第一次分治法调用示意图如下：

留下评论

You must be logged in to post a comment.