2011年软考程序员考试复习笔试知识点整理(5)6

 　快速排序

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

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

　　时间复杂度 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]