快速排序算法及其注意事项

长平狐 发布于 2013/03/12 13:02
阅读 42
收藏 0

在论坛上看到一篇讲快速排序算法的文章,不记得是谁了,然后出于兴趣自己动手学习了一下,下面是一点心得:
算法:利用分治思想,每次定义一个主元,然后从前后两个方向进行对比和移动,把数据按照基元为中心,分成两份,
前面的为所有大于基于的数,后面的为所有小于基元的数(从小到大排序则相反),然后递归调用,分别再对两侧的数组
进行排序,直到顺序排好为止。

代码:

1 /* ******************************************************* */ 2 /* **函数名:QuickSort 3 /***参数:array-数组名,nBegin-数组的上标,nEnd-数组的下标 4 /***返回值:无 5 /***作用:将数组内的元素从大到小排序 6 /******************************************************* */ 7 void QuickSort( int array[], int nBegin, int nEnd) 8 { 9 /* **结束条件*** */ 10 if (nBegin >= nEnd) 11 { 12 return ; 13 } 14 /* ************* */ 15 16 int nKey = array[nBegin]; // 基元(选第一个数,也可以选其他的,但是容易出问题,后面会讲) 17 18 // test 19 // nKey = 6; 20 // endtest 21 22 int nLow = nBegin; 23 int nHigh = nEnd; 24 while(nLow< nHigh) 25 { 26 while(nLow<nHigh && array[nHigh]<nKey) // 如需从小到大排序,改为array[nHigh]>nKey 27 { 28 nHigh-- ; 29 } 30 array[nLow] = array[nHigh]; 31 while(nLow<nHigh && array[nLow]>nKey) // 如需从小到大排序,改为array[nLow]<nKey 32 { 33 nLow++ ; 34 } 35 array[nHigh] = array[nLow]; 36 37 // test 38 // printf("nlow=%d nhigh=%d narray[nlow]=%d array[nhigh]=%d\n",nLow,nHigh,array[nLow],array[nHigh]); 39 // endtest 40 41 } 42 array[nLow] = nKey; // 将基元插入中间 43 44 // test 45 // PrintArray(array, nBegin, nEnd); 46 // return; 47 // endtest; 48 49 QuickSort(array, nBegin, nLow- 1 ); 50 QuickSort(array, nLow+ 1 , nEnd); 51 } 52 53 void PrintArray( int array[], int nBegin, int nEnd) 54 { 55 for ( int na=nBegin; na<=nEnd; na++ ) 56 { 57 std::cout<<array[na]<< " " ; 58 } 59 } 60 int main( int argc, char * argv[]) 61 { 62 int ch[ 8] = { 2, 4, 9, 3, 6, 7, 1, 5 }; 63 QuickSort(ch, 0, 7 ); 64 PrintArray(ch, 0, 7 ); 65 return 0 ; 66 }

注意事项:
1、选取基元时,最好是选择数组的第一个或者最后一个,这样程序便于编写和理解。如果选其他的,容易陷入死循环。比如上面的例子,如果在第一轮排序时选择6作为基元,那么就会陷入死
循环了。可以把里面的注释项全部去掉然后测试。
2、基元选取要注意:如果选数组第一个作为基元,那么应该从数组尾端开始进行比较,否则上面的程序行不通,因为从头部开始会丢失基元。所以两个while循环的顺序要注意。
3、递归要加入结束条件,否则无法实现。注:论坛上那片文章没有加入结束条件,我运行时无法得到结果,所以在这里提出作为注意事项。

另外:上面的注意事项3,如果没有加入结束条件,本来递归会陷入无尽的循环,但是运行程序过程中却自动退出了,我想是不是编译器对这种无限循环有保护机制,达到一定数量自动退出,以免内存耗尽
所以我对此作了一个简单的测试:

1 void Test( int n) 2 { 3 cout<<n<< endl; 4 Test(-- n); 5 } 6 void main() 7 { 8 Test( 0 ); 9 }

果然,n=-4771时退出。这里只能猜,求知道的朋友给个答复。注:编译器为VS2005,操作系统:widows 7


原文链接:http://www.cnblogs.com/wb-DarkHorse/archive/2012/03/12/wb_DarkHorse.html
加载中
返回顶部
顶部