快速排序的思想（基于分治策略）：

1. 选择基准点，把比基准点小的数据放在左边，把比基准点大的数据放在右边；一般选择第一个位置作为基准点。
2. 在第一趟遍历完成，把这组数据以基准点的界限，分成两部分，分别为基准点左边部分和基准点右边部分。
3. 这两部分分别取每部分的第一个数据为新的基准点，重复整个过程

图解：

代码实现：

#include <stdio.h>int parition(int arr[],int start,int end)//找到基准点后的基准点下标
{int boundkey=arr[start];while(start<end)//元素没有遍历完，如果start>=end表示所有数据比较完成{while(statr<end && arr[end] >= boundkey)//元素没有遍历完并且大数在后面，不用移动end--;arr[start]=arr[end];//后面有数据小于基准值while(start<end && arr[start] <= boundkey)//元素没有遍历完并且小数在前面，不用移动start++;arr[end]=arr[start];//前面有大于基准值的数据}arr[end]=boundkey;return start;//stare==end
}void Quick(int arr[],int startindex,int endindex)//递归 实现一趟排序
{int k;if(startindex<endindex)//判断这个区间是否需要排序{k=parition(arr,startindex,endindex);//保存基准点下标Quick(startindex,k-1);//递归调用把基准点左边化成一个区间Quick(k+1,endindex);//递归调用把基准点右边化成一个区间}
}void QuickSort(int arr[],inr len)
{Quick(arr,0,len-1);
}void ShowArr(int arr[],int len)
{int i=0;for(i;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[]={15,3,2,43,46,75,12,4,235,45,7};int len=sizeof(arr)/sizeof(arr[0]);ShowArr(arr,len);QuickSort(arr,len);ShowArr(arr,len);return 0;
}

快速排序的优化:

优化一：优化最坏情况---数据有序（数据越有序，递归层次越多，所占空间越大，递归开栈和清栈开销太多，因此效率越差），比如{1，2，3，4，5，6，7，8，9}。

优化方法：随机取基准点，用rand() %(endindex-startindex+1)+startindex取随机值和区间的第一个数据交换,作为随机基准点

#include <stdio.h>
#include <stdlib.h>
void Swap(int arr[],int first,int second)
{int tmp;tmp=arr[first];arr[first]=arr[second];arr[second]=tmp;
}int parition(int arr[],int start,int end)//找到基准点后的基准点下标
{int boundkey=arr[start];while(start<end)//元素没有遍历完，如果start>=end表示所有数据比较完成{while(statr<end && arr[end] >= boundkey)//元素没有遍历完并且大数在后面，不用移动end--;arr[start]=arr[end];//后面有数据小于基准值while(start<end && arr[start] <= boundkey)//元素没有遍历完并且小数在前面，不用移动start++;arr[end]=arr[start];//前面有大于基准值的数据}arr[end]=boundkey;return start;//stare==end
}void Quick(int arr[],int startindex,int endindex)//递归 实现一趟排序
{int k;if(startindex<endindex)//判断这个区间是否需要排序{Swap(arr,startindex,rand() %(endindex-startindex+1)+startindex);//取随机值和startindex交换k=parition(arr,startindex,endindex);//保存基准点下标Quick(startindex,k-1);//递归调用把基准点左边化成一个区间Quick(k+1,endindex);//递归调用把基准点右边化成一个区间}
}void QuickSort(int arr[],inr len)
{Quick(arr,0,len-1);
}void ShowArr(int arr[],int len)
{int i=0;for(i;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[]={15,3,2,43,46,75,12,4,235,45,7};int len=sizeof(arr)/sizeof(arr[0]);ShowArr(arr,len);QuickSort(arr,len);ShowArr(arr,len);return 0;
}

 优化二：数据本身是随机的，数据可能是随机的，可能是有序的

优化方法：三数取中法（三数是区间的第一个数据，区间的中间数据，区间的最后一个数据），在这三个数据里面取中间大的数据做基准值，进行快排

#include <stdio.h>void getMiddleMaxNum(int arr[],int start,int end)
{if(arr[mid]>arr[end]){Swap(arr,mid,end);}if(arr[start]<arr[end])//end 中间大{Swap(arr,start,end);}if(arr[start]>arr[mid])//mid 中间大{Swap(arr,start,mid);}
}int parition(int arr[],int start,int end)//找到基准点后的基准点下标
{int boundkey=arr[start];while(start<end)//元素没有遍历完，如果start>=end表示所有数据比较完成{while(statr<end && arr[end] >= boundkey)//元素没有遍历完并且大数在后面，不用移动end--;arr[start]=arr[end];//后面有数据小于基准值while(start<end && arr[start] <= boundkey)//元素没有遍历完并且小数在前面，不用移动start++;arr[end]=arr[start];//前面有大于基准值的数据}arr[end]=boundkey;return start;//stare==end
}void Quick(int arr[],int startindex,int endindex)//递归 实现一趟排序
{int k;if(startindex<endindex)//判断这个区间是否需要排序{int midindex=(endindex+startindex)/2;计算出中间的数据getMiddleMaxNum(arr，startindex,midindex,endindex);//把中间值放在stare位置k=parition(arr,startindex,endindex);//保存基准点下标Quick(startindex,k-1);//递归调用把基准点左边化成一个区间Quick(k+1,endindex);//递归调用把基准点右边化成一个区间}
}void QuickSort(int arr[],inr len)
{Quick(arr,0,len-1);
}void ShowArr(int arr[],int len)
{int i=0;for(i;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[]={15,3,2,43,46,75,12,4,235,45,7};int len=sizeof(arr)/sizeof(arr[0]);ShowArr(arr,len);QuickSort(arr,len);ShowArr(arr,len);return 0;
}

优化三：快排适合数据量大的排序，因为可以忽略开栈清栈的开销；小数据量用插入排序

优化方法：加一个if语句判断数据量的多少

void InsertSort(int arr[],int start,int end)
{int i=start+1;int j=i-1;int tmp;for(i;i<=end;i++){tmp=arr[i];for(j=i-1;j>=start && arr[j]>tmp;j--){arr[j+1]=arr[j];}arr[j+1]=tmp;}
}
void Quick(int arr[],int startindex,int endindex)//递归 实现一趟排序
{int k;if(startindex<endindex)//判断这个区间是否需要排序{if((endindex-startindex)<20)//判断数据量{InsertSort(arr,startindex,endindex);return;}k=parition(arr,startindex,endindex);//保存基准点下标Quick(startindex,k-1);//递归调用把基准点左边化成一个区间Quick(k+1,endindex);//递归调用把基准点右边化成一个区间}
}

优化四：数据量大且数据重复，重复的数据也要进行递归处理，需要开栈和清栈，要占一定的开销

优化方法：聚集优化，把和基准点相同的数据聚集在一起，减少重复数据的递归处理

void Gather(int arr[],int s,int e,int k,int newleft,int newright)
{int newleft=k-1;int newright=k+1;for(int i=k-1;i>=start;i--){if(arr[i]==arr[k]){if(i!=newleft){int tmp=arr[newleft];arr[newleft]=arr[i];arr[i]=tmp;newleft--;}else{newleft--;}}}for(int j=k+1;j<=end;j++){if(arr[j]==arr[k]){if(j!=newright){int tmp=arr[newright];arr[newright]=arr[j];arr[j]=tmp;newright++;}else{newright++;}}}
}
void Quick(int arr[],int startindex,int endindex)//递归 实现一趟排序
{int k;if(startindex<endindex)//判断这个区间是否需要排序{int left;int right;Gather(arr,startindex,endindex,k,&left,&right);k=parition(arr,startindex,endindex);//保存基准点下标Quick(startindex,k-1);//递归调用把基准点左边化成一个区间Quick(k+1,endindex);//递归调用把基准点右边化成一个区间}
}

优化五：非递归优化，减少了递归过程中的开栈和清栈开销，提高了效率

int parition(int arr[],int start,int end)//找到基准点后的基准点下标
{int boundkey = arr[start];while(start < end){while(start < end && arr[end])end--;arr[start] = arr[end];while(start < end && arr[start] <= boundkey)start++;arr[end] = arr[start]}arr[start] = boundkey;return start;
}
void Quick(int arr[], int startindex,int endindex)
{int k;int * st = (int *)malloc(sizeof(int)*(endindex - startindex + 1));//动态开辟一个数组模拟栈int top = 0;//栈顶指针int left = startindex;int right = endindex;st[top++] = left;//把left放进栈中st[top++] = right;//把right放进栈中  此时栈顶指针是rightwhile(top != 0){right = st[top - 1];//拿到栈顶元素top--;//出栈left = st[top - 1];//继续拿到元素top--;//出栈k = parition(arr,left,right);//栈中元素先进后出，所以先入左边区间元素，再入右边区间元素if(k + 1 < right)//右区间至少有两个元素{st[top++] = k + 1;st[top++] = right;}if(left < k - 1)//右区间至少有两个元素{st[top++] = left;st[top++] = k - 1;}}free(st);
}