冒泡排序 && 快排(hoare递归)

这篇具有很好参考价值的文章主要介绍了冒泡排序 && 快排(hoare递归)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

今天要讲一个是冒泡排序,进一个是快排,首先是冒泡排序,我相信大家接触的第一个排序并且比较有用的算法就是冒泡排序了,冒泡排序是算法里面比较简单的一种,所以我们先看看一下冒泡排序

还是个前面一样,我们先看一下单趟排序

假设我们又以下数组

冒泡排序 && 快排(hoare递归)

我们想要对他进行排序

那么此时我们先看第一个位置和第二个位置

冒泡排序 && 快排(hoare递归) 

i和j位置,如果这里i位置的值大于j位置的值,那么我们就让他们交换,否则就让i和j同时向后走一位

冒泡排序 && 快排(hoare递归) 

 让i和j位置的值进行交换,然后让i和j同时向后走一位

冒泡排序 && 快排(hoare递归)

 然后就继续比较i和j位置的值

冒泡排序 && 快排(hoare递归)

 然后最后排好就是这样子的,此时我们一趟就排序结束了,这时候我们可以看到,我们数组的最后一个元素是最大的,所以我们继续排序,从第0和位置开始到现在9后面的位置,依次比较,如果i大于j位置的元素就交换否则就让i和j同时向后走

下面我们就看一下代码

冒泡排序 && 快排(hoare递归)

代码也是很简单基本没什么好看的

下面我们看一个🐂的排序 ,快排,听名字就知道一定很快

下面就看一下

假设我们是这一组数据

冒泡排序 && 快排(hoare递归)

 我们先说思想,这里就是先选一个数,然后左边找比选定的key大的,右边找小的,然后两个位置交换,然后让最后两个位置相遇后与key位置的值交换,最后就可以让key位置的值的左边都是比key小的,右边都是比key大的

就是这样,所以我们现在来看一下

冒泡排序 && 快排(hoare递归)

 首先左边找大,右边找小,然后找到了就交换

冒泡排序 && 快排(hoare递归)

 然后继续找,找到了就交换

冒泡排序 && 快排(hoare递归)

 最后直到left不小于right说明就剩下最后一个了,然后我们就让相遇的位置与key位置的值交换,最后我们就可以看到

6的左边都是小于他的,6的右边都是大于他的

到了这里我们一趟排序就结束了,我们想一下刚才排序的过程,我们用左边第一个值作为key,然后我们右边先开始找的小于key位置的值,我们这里就先记住,如果是左边为key那么就右边先走,如果右边为key那么就左边先走,其中这里的key并不是某一个固定的值,我们可以选数组其他位置的值为key但是那样的话容易出错,所以我们可以选择左边或者右边的值为key,那么这样我们就一趟排序结束了

这时候我们就可以想,怎么样可以把他排序好

我们这时候继续看一下

冒泡排序 && 快排(hoare递归) 

这时候我们的6已经拍好了,所以我们就不需要在管6了,我们就可以让他继续 

冒泡排序 && 快排(hoare递归)

递归下去,以一边的right以6这个位置-1为末尾,另一边以6这个位置+1为起始点

冒泡排序 && 快排(hoare递归) 

 然后我们继续递归

冒泡排序 && 快排(hoare递归)

就这样下去我们就可以依次拍好,让每一个值的左边都是小于他的右边都是大于他的,这里我们认为如果只剩下一个数字那么就是有序的。所以这里如果l不小于r那么就 只剩下一个数字

最后排序好就是这样

冒泡排序 && 快排(hoare递归)

 就是这样,然后我们就排序好了

下面我们就来看一下代码

冒泡排序 && 快排(hoare递归)

 文章来源地址https://www.toymoban.com/news/detail-400094.html

 首先我们这里定义key为left,然后我们就开始找大和小,然后让他们交换,知道left不小于right说明已经找完了,最后让left和right相遇的位置和key位置的值交换,然后就进行递归

你们可以画一下递归展开图

就是这样,主要是这里画递归展开图太麻烦了,就不画了,而且之前在树遍历那一块画了很多遍,思想已经传达到了

这个就是快排

完了介绍快排的时间复杂度

 

 

到了这里,关于冒泡排序 && 快排(hoare递归)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包