快速排序个人笔记
程序员文章站
2024-03-16 10:57:58
...
快速排序
在待排序的n个元素中任取一个元素(通常取第一个元素)作为基准,把该元素放入最终位置后,整个数据序列被基准分割成两个子序列,所有小于基准的元素放置在前子序列中,所有大于基准的元素放置在后子序列中,并把基准排在这两个子序列的中间,这个过程称作划分。
然后对两个子序列分别重复上述过程,直至每个子序列内只有一个记录或空为止。
策略
① 分解:将原序列a[s…t]分解成两个子序列a[s…i-1]和a[i+1…t],其中i为划分的基准位置。
② 求解子问题:若子序列的长度为0或为1,则它是有序的,直接返回;否则递归地求解各个子问题。
③ 合并:由于整个序列存放在数组中a中,排序过程是就地进行的,合并步骤不需要执行任何操作。
代码
//快速排序算法
#include <stdio.h>
void disp(int a[],int n) //输出a中所有元素
{ int i;
for (i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
int Partition(int a[],int s,int t) //划分算法
{ int i=s,j=t;
int tmp=a[s]; //用序列的第1个记录作为基准
while (i!=j) //从序列两端交替向中间扫描,直至i=j为止
{ while (j>i && a[j]>=tmp)
j--; //从右向左扫描,找第1个关键字小于tmp的a[j]
a[i]=a[j]; //将a[j]前移到a[i]的位置
while (i<j && a[i]<=tmp)
i++; //从左向右扫描,找第1个关键字大于tmp的a[i]
a[j]=a[i]; //将a[i]后移到a[j]的位置
}
a[i]=tmp;
return i;
}
void QuickSort(int a[],int s,int t) //对a[s..t]元素序列进行递增排序
{ int i;
if (s<t) //序列内至少存在2个元素的情况
{ i=Partition(a,s,t);
QuickSort(a,s,i-1); //对左子序列递归排序
QuickSort(a,i+1,t); //对右子序列递归排序
}
}
void main()
{ int n=10;
int a[]={2,5,1,7,10,6,9,4,3,8};
printf("排序前:"); disp(a,n);
QuickSort(a,0,n-1);
printf("排序后:"); disp(a,n);
}
分析
快速排序的时间主要耗费在划分操作上,对长度为n的区间进行划分,共需n-1次关键字的比较,时间复杂度为O(n)
对n个记录进行快速排序的过程构成一棵递归树,在这样的递归树中,每一层至多对n个记录进行划分,所花时间为O(n)。
当初始排序数据正序或反序时,此时的递归树高度为n,快速排序呈现最坏情况,即最坏情况下的时间复杂度为O(n2);
当初始排序数据随机分布,使每次分成的两个子区间中的记录个数大致相等,此时的递归树高度为log2n,快速排序呈现最好情况,即最好情况下的时间复杂度为O(nlog2n)。快速排序算法的平均时间复杂度也是O(nlog2n)。
上一篇: 用python实现带有透明通道的图片像PS图层那样进行叠加
下一篇: 数字识别、显示边缘