2011年軟考程序員考試復(fù)習(xí)筆試知識點(diǎn)整理(5)

　　快速排序

　　算法思想：將原問題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。

　　遞歸地解這些子問題，然后將這些子問題的解組合成為原問題的解。

　　時(shí)間復(fù)雜度 o(nlogn)

　　空間復(fù)雜度 o(logn)

　　比較次數(shù) ?

　　*/

　　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;

　　}

　　/*

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)