數(shù)據(jù)結(jié)構(gòu)排序算法之快速排序

《數(shù)據(jù)結(jié)構(gòu)排序算法之快速排序》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)排序算法之快速排序l算法介紹快速排序也是交換類排序的一種。快速排序是選擇一個數(shù)據(jù)作為樞紐，將啊序列分為兩部分，樞紐的一邊比它小(至少不大于)，另一邊比它大(至少不小于)。l執(zhí)行流程原始序列：234512907856IJ進行第一趟排序，選擇23作為樞紐，整個過程是一次交替掃描的過程1)使用最后一個元素J=56開始從右向左掃描23451290785656>23不交換,J--IJ23451290785678>23J--IJ23451290785612<23交換I++IJ124590785645>23交換J--IJ1245907856此時I

2、=J所以這個位置為樞紐的位置IJ122345907856一趟排序結(jié)束2)然后從樞紐的位置開始分為兩部分，按照同樣的方法進行排序即可，也就遞歸。l示例代碼#includevoidquick_sort(inta[],ints,inte){inttmp;inti=s;intj=e;if(si&&a[j]>tmp)j--;if(ii&&a[i]

3、i]=tmp;quick_sort(a,s,i-1);quick_sort(a,i+1,e);}}intmain(){inta[]={-12,23,1,46,6,23423,456,1,56,0,2,24,46,68,4,5234,234,436,654,576,43,354,432,32,4,23,4,2,3243,45,6,432,423,6,5,7,86,8,54,4,5435,3,5343,43,543,6,54,6,45,654,654,3,45,3,423,4,2,34,547,87,686867,4,53,32,23,

4、432,34,43,5667,8897646,35,3,45,3,53,4,333,54,765,7,5,66,45,45353,534,5,34,6547,685,4,543,5,3,53,234,2,34,23,4,2,43,6,765,7,8,9,9,9,0,0,4534,52,3,234,2,41,435,23,123,235,436,7,43,23,243,3121};inti=0;for(i=0;i

5、);quick_sort(a,0,sizeof(a)/sizeof(int)-1);for(i=0;i

6、34564324236578685445435353434354365464565465434534234234547876868674533223432344356678897646353453534333547657566454535353453465476854543535323423423424367657899900453452323424143523123235436743232433121-120001122222233333334444444445555666666777788999232323232323243232343

7、4343435414343434343454545454546465253535354545456666886871232342342342352433333544234234324324324354364364565345435435475766546546546857657653121324345345234534354355667654723423453536868678897646l性能分析本算法的時間復(fù)雜度是n的平方，空間復(fù)雜度是O(1)。l更多內(nèi)容請關(guān)注個人文庫http://wenku.baidu.com/p/helpylee