程序员专用复习资料：快速排序

  2013年上半年软考指定教材

2013下半年软考培训：在线辅导 面授班

快速排序

算法思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。

递归地解这些子问题，然后将这些子问题的解组合成为原问题的解。

时间复杂度 o（nlogn）

空间复杂度 o（logn）

比较次数 ?
*/
void quick_sort（int array[],int low,int high）
{
if （low < high）
{
int pivotloc =partition（array,low,high）；
quick_sort（array,low,pivotloc-1）；
quick_sort（array,pivotloc+1,high）；
}
}
int partition（int array[],int low,int high）
{
int pivotkey = array[low];
while （low < high）
{
while（low < high &&array[high] >= pivotkey）
--high;
swap（array[low],array[high]）；
while（low < high &&array[low] <= pivotkey）
++low;
swap（array[low],array[high]）；
}
array[low] = pivotkey;
return low;
}
/*

返回目录：软考程序员专用复习资料

编辑推荐：2013年软考程序员理论知识汇总

　2013年软考程序员常考知识点锦集