首页 > 代码库 > 排序算法总结

排序算法总结

2024-07-08 04:03:10   230人阅读

概述：排序算法可分为比较性的排序，以及运算性的排序；这里详细介绍这些排序的原理，性能，实现，以及应用场合。

比较排序

一：快速排序

1：原理

采用了分治思想，在序列A[p...r]中选取一个元素，当然这里是用了p或者r处的元素（规格一致）；找到该元素的，满足前面的值都比它小，后面的都比它大；同理让子序列递归下去。

2：性能

最坏时间复杂度：θ(n²)---出现在序列是顺序的，导致极度不平衡划分，1:0效果划分。

最好时间复杂度：θ(nlog2(n))---出现在每次划分都是在中间处；

中间状态：比如划分比例是a:b；则复杂度就是a/(b+a);b/(b+a)取大的（假设为a/(b+a)），则复杂度为θ(nlog(b+a)/a(n))其实也可以是θ(nlog(n))

平均复杂度也就是θ(nlog(n))；

空间复杂度为：0；

3：应用

实际排序中比较好，适合对平均时间复杂度有要求，要求原址排序，且隐含因子比较小；应用场景多。

4：实现----c++代码实现如下

void exchang(int * sort,int i,int j){    int temp=0;    temp=sort[i];    sort[i]=sort[j];    sort[j]=temp;}int partition(int *sort ,int p,int r){    int x=sort[r];    int i=p-1;    for(int j=p;j<r;j++)//p--->r-1    if(sort[j]<=x)    {        i++;        if(i!=j)            exchang(sort,i,j);    }    if((i+1)<r)        exchang(sort,i+1,r);        return i+1;}//栈溢出，原因是它递归太深了void QuickSort(int *sort ,int sn,int en){    if(sn<en)    {        int q=partition(sort,sn,en);        QuickSort(sort,sn,q-1);        QuickSort(sort,q+1,en);    }}
QuickSort

 

 

 

 

 

 

 


联系
我们