在中已经讨论过关于快速排序如何优化的问题，这次就直接贴出完整已优化的代码。此代码优化步骤包括了三数取中选取枢轴+小数组使用插排+三向切分。

完整代码：

#include 
    
     #include 
     
      #define MAXSIZE 100	//用于要排序数组的最大值 #define MAX_LENGTH_INSERT_SORT 7	//数组长度阈值 typedef struct		//定义一个顺序表结构 {
        int r[MAXSIZE+1];	//用于存储要排序数组，r[0]用作哨兵或者临时变量     int length;			//用于存储顺序表的最大长度 }SqList;void swap(SqList *L,int i,int j);void InsertSort(SqList *L);void PickMiddle(SqList *L,int low,int high);int Partition(SqList *L,int low,int high);void QSort(SqList *L,int low,int high);void QuickSort(SqList *L);int main(){    int i;    int array[] = {
   39,80,76,41,13,29,50,78,30,11,100,7,41,86,41,11,30};    SqList L;    L.length = sizeof(array)/sizeof(array[0]);	//获取数组长度      printf("Before sorting:");    for(i=0;i
      
       r[i];    L->r[i]=L->r[j];    L->r[j]=temp;}/*快速排序主函数*/void QuickSort(SqList *L){    QSort(L,1,L->length);	//L->r[0]作为哨兵，low从1开始 }/*快排处理函数*/void QSort(SqList *L,int low,int high){	    /* if-else条件语句用于处理小数组处理的问题，     * 具体序列值说法不一，此处定为7（也有认为50合理）。若数组     * 个数较小采用简单插入排序，效率更高。*/    if((high-low) <= MAX_LENGTH_INSERT_SORT)    {    	InsertSort(L);    	return;    }        PickMiddle(L,low,high);	//三数取中函数        int lt = low;	//low此时为枢轴位置    int gt = high;    int i = low +1;	//low位置的元素为枢轴元素，所以用于比较的元素从low+1开始        L->r[0]=L->r[low];	//将枢轴的元素储存到L->r[0]中         while(i<=gt)    {    	if(L->r[i] < L->r[0])		//小于枢轴元素的放在lt左边     	    swap(L,lt++,i++);		//即交换lt和i位置的元素，此时枢纽位置(lt)右移一位，i也因此右移    	else if(L->r[i] > L->r[0])	//大于枢轴元素的放在gt右边     	    swap(L,i,gt--);			//交换i和gt位置的元素，gt需要左移，i由于变为gt位置元素，所以不需要移动    	else		//相等时，无需交换，只需把i右移一位    	    i++;    }    //lt-gt的元素已经排定（相等的元素），只需对it左边和gt右边的元素进行递归求解    QSort(L,low,lt-1);    QSort(L,gt+1,high);	}/*三数取中函数*/void PickMiddle(SqList *L,int low,int high){    int mid = (low+high) / 2;	//计算数组中间元素的下标        if(L->r[low]>L->r[high])     	swap(L,low,high);	//目标[low]<=[high]     if(L->r[mid]>L->r[high])    	swap(L,mid,high);	//目标[mid]<=[high]     						//以上两步保证把最大移到最右端     if(L->r[mid]>L->r[low])    	swap(L,mid,low);		//目标[low]>=[mid],即把中间值移到最左端     	    //此时，L->r[mid] <= L->r[low] <= L->r[high]}/*直接插入排序*/void InsertSort(SqList *L){    int i,j;    for(i=2; i<=L->length; i++)    {    	if(L->r[i] < L->r[i-1])    	{            L->r[0]=L->r[i];            for(j=i-1; L->r[j] > L->r[0]; j--)            	L->r[j+1]=L->r[j];            L->r[j+1]=L->r[0];    	}    }}复制代码
      
     
    

运行结果为：