快速排序

一. 算法描述

快速排序：快速排序采用分治法进行排序，首先是分割，选取数组中的任意一个元素value（默认选用第一个），将数组划分为两段，前一段小于value，后一段大于value；然后再分别对前半段和后半段进行递归快速排序。其实现细节如下图所示：

关键问题：将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素

为方便理解我还准备了动图：

二. 算法分析

平均时间复杂度：O(nlog2n)

空间复杂度：O(n)

稳定性：不稳定

三. 算法实现

int Quicksort(int s[],int start,int end)    //自定义函数 qusort()
{
    int i,j;    //定义变量为基本整型
    i=start;    //将每组首个元素赋给i
    j = end;    //将每组末尾元素赋给j
    s[0]=s[start];    //设置基准值
    while(i<j)
    {
        while(i<j&&s[0]<s[j])
        j--;    //位置左移
        if(i<j)
        {
            s[i]=s[j];    //将s[j]放到s[i]的位置上
            i++;    //位置右移
        }
        while(i<j&&s[i]<=s[0])
            i++;    //位置左移
        if(i<j)
        {
            s[j]=s[i];    //将大于基准值的s[j]放到s[i]位置
            j--;    //位置左移
        }
    }
    s[i]=s[0];    //将基准值放入指定位置
    if (start<i)
        Quicksort(s,start,j-1);    //对分割出的部分递归调用quicksort()函数
    if (i<end)
        Quicksort(s,j+1,end);
    return 0;
}