一. 算法描述
快速排序：快速排序采用分治法进行排序，首先是分割，选取数组中的任意一个元素value（默认选用第一个），将数组划分为两段，前一段小于value，后一段大于value；然后再分别对前半段和后半段进行递归快速排序。其实现细节如下图所示：
二. 算法实现
/*============================================================================= # # FileName: fastSort.c # Algorithm: 快速排序 # Author: Knife # Created: 2014-06-16 21:24:02 # =============================================================================*/ #include<stdio.h> void fastSortImp(int* intArrStart, int len); void main(){ int intArr[] = {8,3,6,4,2,9,5,4,1,7}; int n = sizeof (intArr) / sizeof (intArr[0]); // 数组长度 int i = 0; //快速排序 fastSortImp(intArr,n); //打印输出 for(;i<n;i++){ printf("%d ",intArr[i]); } printf(" "); } //快速排序，应该分为两步：首先找到分割点，然后在对分割点的左侧和右侧分别进行递归 void fastSortImp(int* intArrStart, int len){ if(len > 1){ int i = 0; int j = len-1; int intTmp = intArrStart[0]; while(j > i){ // 从右向左查找比intTmp小的 while(j > i && intArrStart[j] >= intTmp){ j--; } if(j >i ){ intArrStart[i] = intArrStart[j];//将s[j]填到s[i]中,s[i]就形成了一个新的坑 i++; } // 从左向右查找比intTmp大的 while(j > i && intArrStart[i] <= intTmp){ i++; } if(j > i){ intArrStart[j] = intArrStart[i];//将s[i]填到s[j]中,s[j]就形成了一个新的坑 j--; } } intArrStart[i] = intTmp;//找到分割点。此时 i等于j。将intTmp填到这个坑中 // 前半段 fastSortImp(intArrStart, i); // 后半段 fastSortImp(intArrStart + i + 1, len - i-1); } }
三. 算法分析
- 平均时间复杂度：O(nlog2n)
- 空间复杂度：O(n)
- 稳定性：不稳定
参考资料
[1] http://blog.csdn.net/cjf_iceking/article/details/7925470
[2] http://blog.csdn.net/morewindows/article/details/6684558