快速排序

partition函数

首先需要一个partition函数，partition就是分区的意思，即这个函数的作用是把输入的数组分成左右两部分，返回一个下标；左边的数都比下标对应的数小，右边的数都比下标对应的数大。对于一个算法理解过程最重要，注意细节能够让代码精致。

过程理解

这个函数有三个重要的点

Small指针指向的是最后一个比最后一个元素还要小的元素，small左边的元素都比end指向的元素小；

index指向当前需要审查的元素

small和index之间（不包括边界）的元素都是比end指向的元素大的元素；

函数执行的原则是用index遍历数组，一旦审查元素比end指向的元素小，就把它放在small指向的那部分的左边；如果比end指向的元素大，就先放留在small和index之间。这种换位置的方法就是使用small指向小元素和大元素的交界处，当待查元素是小元素时，与small指向的元素的下一个元素互换，并更新small和index的位置；

整个过程其实像是三个共享一段内存的栈，small指向小元素栈的栈顶，只能push，而index指向的是待查元素的栈，只能Pop,pop出来的如果比end元素小泽push进small栈，被挤掉的大元素放在空出来的位置，这样大元素栈的元素数量不变；如果大，大元素是一个从右边进左边出的队列；

代码：

int partition(int data[],int length,int start,int end)
{
    //下面这个产生异常的方法很好 
    if(data == NULL || length <= 0 || start < 0 || end >= length)
        throw "Invalid Parameters";
    //找一个令旗标； 
    int index = randomInRange(start,end); 
    swap(data,index,end);
    //开始遍历分区;
    int small = start - 1;
    for(index = start;index < end;index++ )
    {
        if(data[index] < data[end])
        {
            small ++;
            if(small != index)//说明small与index之间有大于data[end]的元素； 
                swap(data,index,small);//其实不用判断，直接交换就可以了;
             
        }
    }
    small++;
    swap(data,small,end); 
    return small;
}

randomInRange函数

用来在start和end两个区间内产生随机数

int randomInRange(int start,int end)
{
    srand ( time(NULL) );
    return rand() % (end-start+1) + start; 

}

主函数

递归代码

void quickSort(int data[],int len,int start,int end)
{
    int mid = partition(data, len, start, end);
    if(mid > start)
        quickSort(data,len,start,mid - 1);
    if(mid < end)
        quickSort(data,len,mid+1,end);
}

性能分析：

时间复杂度分析

快排在最好情况下时间复杂度为O().最坏情况下为O(),平均时间复杂度为O()，就平均时间而言，快排是所有排序算法中最优的。快排的排序趟数和初试序列有关。

空间复杂度分析

空间复杂度为O(),快排是递归的，需要栈的调用，因此他需要的辅助空间比较多