【Algorithm】快速排序

/*=============================================================================
#
#     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("\n");
}

//快速排序，应该分为两步：首先找到分割点，然后在对分割点的左侧和右侧分别进行递归
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);

    }
}