菜鸟笔记
提升您的技术认知

快速排序

阅读 : 751

一. 算法描述

快速排序:快速排序采用分治法进行排序,首先是分割,选取数组中的任意一个元素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;
}

笔记 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址