数据结构排序算法之快速排序

《数据结构排序算法之快速排序》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构排序算法之快速排序l算法介绍快速排序也是交换类排序的一种。快速排序是选择一个数据作为枢纽，将啊序列分为两部分，枢纽的一边比它小(至少不大于)，另一边比它大(至少不小于)。l执行流程原始序列：234512907856IJ进行第一趟排序，选择23作为枢纽，整个过程是一次交替扫描的过程1)使用最后一个元素J=56开始从右向左扫描23451290785656>23不交换,J--IJ23451290785678>23J--IJ23451290785612<23交换I++IJ124590785645>23交换J--IJ1245907856此时I

2、=J所以这个位置为枢纽的位置IJ122345907856一趟排序结束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性能分析本算法的时间复杂度是n的平方，空间复杂度是O(1)。l更多内容请关注个人文库http://wenku.baidu.com/p/helpylee