搜索

快速排序第一趟结果是什么

gecimao 发表于 2019-07-25 21:49 | 查看: | 回复:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  数据结构里面上课曾经说到过这个算法,一般来说是以第一个为key,在本题中要求key为518,那么,第一趟的排序过程如下:

  205,132,314,181,518,746,946,984,541,827

  快速排序第一趟结果是通过一趟排序将要排序的数据分割成独立的两部分,一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序得到的结果。

  知道合伙人教育行家采纳数:8985获赞数:60498对于基本办公软件比较擅长。向TA提问展开全部每一趟确定一个值的位置,比它大的在右边,小的左边,然后分成两个数组接着排.

  快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

  囧...略乱,竟然与第一次不一样了...我再算下追问哈哈,我只会算以第一个数据位关键数据的算法!果然不是计算机专业不行啊,悲剧了!我看了你的算法,你是按第一个数据做关键数据的,那题目中以中间元素518为基准,什么意思呢?追答541(low),132,984,746,518,181,946,314,205,827(high)

  没有喽,我是以518为枢做的喽,以最原始的快排来看,就是大于518的low与high交换,小于518的high与low交换追问大哥,你的结果是以第一个数组元素为关键数据在算的,这个我也会,但是以数组元素中某个元素为关键数据来算呢?我觉得题目中以中间元素518为基准,应该是以518为key。可是怎么算也得不到这个答案,应该没完全理解这个算法追答

  3)从j开始向前搜索,即由后开始向前搜索(j -- ),找到第一个小于key的值A[j],A[i]与A[j]交换;

  4)从i开始向后搜索,即由前开始向后搜索(i ++ ),找到第一个大于key的A[i],A[i]与A[j]交换;

  我的疑问是你的low初始化追答莫非是key=A[0]这个表达式的影响了你?key随意赋为哪个元素都可以喽。经验上,严蔚敏的《数据结构》上赋为第一个元素,而《算法导论》赋为最后一个元素。原理上,key不过为了将数组进行初始的分割。这道题,key=518。

  而low和high是为了向前和向后遍历当前数组,所以必然是赋为当前数组的第一个元素和最后一个元素的索引。追问还是不理解?网上找到的快排方法不同,虽然你程序的结果可能相同,网上都是518与比他大的数据或者小的数据进行交换位置,最终low=high结束,而你的程序while的循环,518的位置是永远不变的。追答囧...这个真心凑巧呦,给定的数组有4个元素比518小,有5个元素比518大,而518又是第5个元素,所以初始只要以518为枢进行一趟快排,那么518的位置是不会变的。

本文链接:http://baumseelen.com/duipaixu/728.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部