一. 算法描述
快速排序：快速排序采用分治法进行排序，首先是分割，选取数组中的任意一个元素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[] = {,,,,,,,,,};
int n = sizeof (intArr) / sizeof (intArr[]); // 数组长度
int i = ;
//快速排序
fastSortImp(intArr,n);
//打印输出
for(;i<n;i++){
printf("%d ",intArr[i]);
}
printf("\n");
} //快速排序，应该分为两步：首先找到分割点，然后在对分割点的左侧和右侧分别进行递归
void fastSortImp(int* intArrStart, int len){
if(len > ){
int i = ;
int j = len-;
int intTmp = intArrStart[];
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 + , len - i-); }
}
三. 算法分析
- 平均时间复杂度：O(nlog2n)
- 空间复杂度：O(n)
- 稳定性：不稳定
参考资料
[1] http://blog.csdn.net/cjf_iceking/article/details/7925470
[2] http://blog.csdn.net/morewindows/article/details/6684558