有一组关键字序列(41,34,53,38,26,74),采用快速排序方法由大到小进行排序

有一组关键字序列(41,34,53,38,26,74),采用快速排序方法由大到小进行排序请详细一些... 有一组关键字序列(41,34,53,38,26,74),采用快速排序方法由大到小进行排序请详细一些 展开
 我来答
Coolwriter
2017-12-10 · TA获得超过3806个赞
知道小有建树答主
回答量:787
采纳率:84%
帮助的人:229万
展开全部

快速排序又称分区交换排序,是对冒泡排序的改进,快速排序采用的思想是分治思想。。

算法原理: 
(1)从待排序的n个记录中任意选取一个记录(通常选取第一个记录)为分区标准;

(2)把所有小于该排序列的记录移动到左边,把所有大于该排序码的记录移动到右边,中间放所选记录,称之为第一趟排序;

(3)然后对前后两个子序列分别重复上述过程,直到所有记录都排好序。

稳定性:不稳定排序。

时间复杂度: O(nlog2n)至O(n2),平均时间复杂度为O(nlgn)。

最好的情况:是每趟排序结束后,每次划分使两个子文件的长度大致相等,时间复杂度为O(nlog2n)。

最坏的情况:是待排序记录已经排好序,第一趟经过n-1次比较后第一个记录保持位置不变,并得到一个n-1个元素的子记录;第二趟经过n-2次比较,将第二个记录定位在原来的位置上,并得到一个包括n-2个记录的子文件,依次类推,这样总的比较次数是: 

Cmax=∑i=1n−1(n−i)=n(n−1)/2=O(n2)

//a:待排序数组,low:最低位的下标,high:最高位的下标
void quickSort(int a[],int low, int high)
{
    if(low>=high)
    {
        return;
    }
    int left=low;
    int right=high;
    int key=a[left];    /*用数组的第一个记录作为分区元素*/
    while(left!=right){
        while(left<right&&a[right]>=key)    /*从右向左扫描,找第一个码值小于key的记录,并交换到key*/
            --right;
        a[left]=a[right];
        while(left<right&&a[left]<=key)
            ++left;
        a[right]=a[left];    /*从左向右扫描,找第一个码值大于key的记录,并交换到右边*/
    }
    a[left]=key;    /*分区元素放到正确位置*/
    quickSort(a,low,left-1);
    quickSort(a,left+1,high);
}

题目中对(41,34,53,38,26,74)排序

第一趟     26,34 ,53 ,38,41 ,74

26,34 , 41 ,38,53 ,74

26,34 , 38 ,41,53 ,74

这样序列就这样分割成了两部分,左边部分{26,34 , 38 } 均小于 基准值(41);右边部分 {53 ,74},均大于基准值。这样子我们就达到了分割序列的目标。在接着对子序列用同样的办法进行分割,直至子序列不超过一个元素,那么排序结束,整个序列处于有序状态。

推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式