2011軟考程序員算法實(shí)例解析：快速排序算法

　　代碼:

　　void QuickSort(int low,int high,int *array)

　　{

　　int pos;

　　if(low{

　　pos=SPLIT(low,high,array); //以array[low]進(jìn)行劃分,pos最為劃分點(diǎn)

　　//前一部分后一部分,反之

　　QuickSort(low,pos-1,array); //對(duì)劃分后的前一部分遞歸處理

　　QuickSort(pos+1,high,array); //對(duì)劃分后的后一部分遞歸處理

　　}

　　}

　　int SPLIT(int low,int high,int *array)

　　{

　　int temp=array[low]; //用temp來(lái)記錄劃分?jǐn)?shù)

　　while(low{

　　while(array[high]>temp&&low尋找小于temp的數(shù)

　　high--;

　　if(low==high)

　　break;

　　else

　　{

　　array[low]=array[high];

　　low++;

　　}

　　while(array[low]尋找大于temp的數(shù)

　　low++;

　　if(low==high)

　　break;

　　else

　　{

　　array[high]=array[low];

　　high--;

　　}

　　}

　　array[low]=temp; //最終low=high作為劃分點(diǎn),并將劃分?jǐn)?shù)存于array[low]

　　return low;

　　}

　　思想:

　　就是你從數(shù)組中任取一個(gè)元素p(可隨機(jī)取,現(xiàn)在以取第一個(gè)為例);

　　以P作為主元,對(duì)數(shù)組 進(jìn)行劃分 ,前一部分小于 P,后一部分大于p;

　　最后劃分處存儲(chǔ) p;

　　然后分別對(duì)劃分后的前一部分和后一部分遞歸調(diào)用;

　　算法平均時(shí)間復(fù)雜度: O(nlogn)。

　　相關(guān)推薦：

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

　　2010年下半年軟考成績(jī)查詢時(shí)間及方式匯總

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