快速排序（三指取中法）

快速排序（三指取中法）

排序是算法基础，也是每个学编程的人最早接触的算法之一，快速排序便是排序家族中的一员，其最坏情况O（n^2）,每次划分只能将要排序的序列分成一个元素与其他元素两部分，这时就变身为为冒泡排序，而三指取中法正是为了避免最坏情况存在的（上代码）

#include
int swap(int a[],int l,int r)
{int b = a[l];a[l] = a[r];a[r] = b;
}
int m3(int a[],int left,int right)//三数中值分割法{if(right-left+1>=3){int center=(left+right)/2;if(a[center]<a[left])swap(a,left,center);if(a[center]>a[right])swap(a,center,right);if(a[center]<a[left])swap(a,left,center);swap(a,right-1,center);//选定中值并排序，将中值置于倒数第一位便于排序时插入return a[right-1];}else//针对于少于三个数的处理情况if(a[left]>a[right])swap(a,left,right);return 0;}void q(int a[],int left,int right){int pivot=m3(a,left,right);if(right-left+1>3)//对于长度小于三的情况median函数足以处理{int i=left;int j=right-1;for(;;){while(a[++i]<pivot){}//从第二位向后询值while(a[--j]>pivot){}//从中值之前，即倒数第二位向前询值if(i<j)swap(a,i,j);elsebreak;}swap(a,i,right-1);//当i>j时将其中一个大于中值的值与中值交换位置q(a, left, i-1);q(a, i+1, right);}}int main()
{int a[100], i, j;for(i = 0; i < 10; i ++)scanf("%d", & a[i]);q(a, 0, 9);for(i = 0; i < 10; i++)printf("%d ", a[i]);
}

分享一篇文章
作者： dreamcatcher-cx 出处： http://www.cnblogs.com/chengxiao/
这篇文章中详细讲到了三指取中法的过程

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！