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