欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速排序个人笔记

程序员文章站 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)。