今天要讲一个是冒泡排序,进一个是快排,首先是冒泡排序,我相信大家接触的第一个排序并且比较有用的算法就是冒泡排序了,冒泡排序是算法里面比较简单的一种,所以我们先看看一下冒泡排序
还是个前面一样,我们先看一下单趟排序
假设我们又以下数组
我们想要对他进行排序
那么此时我们先看第一个位置和第二个位置
i和j位置,如果这里i位置的值大于j位置的值,那么我们就让他们交换,否则就让i和j同时向后走一位
让i和j位置的值进行交换,然后让i和j同时向后走一位
然后就继续比较i和j位置的值
然后最后排好就是这样子的,此时我们一趟就排序结束了,这时候我们可以看到,我们数组的最后一个元素是最大的,所以我们继续排序,从第0和位置开始到现在9后面的位置,依次比较,如果i大于j位置的元素就交换否则就让i和j同时向后走
下面我们就看一下代码
代码也是很简单基本没什么好看的
下面我们看一个🐂的排序 ,快排,听名字就知道一定很快
下面就看一下
假设我们是这一组数据
我们先说思想,这里就是先选一个数,然后左边找比选定的key大的,右边找小的,然后两个位置交换,然后让最后两个位置相遇后与key位置的值交换,最后就可以让key位置的值的左边都是比key小的,右边都是比key大的
就是这样,所以我们现在来看一下
首先左边找大,右边找小,然后找到了就交换
然后继续找,找到了就交换
最后直到left不小于right说明就剩下最后一个了,然后我们就让相遇的位置与key位置的值交换,最后我们就可以看到
6的左边都是小于他的,6的右边都是大于他的
到了这里我们一趟排序就结束了,我们想一下刚才排序的过程,我们用左边第一个值作为key,然后我们右边先开始找的小于key位置的值,我们这里就先记住,如果是左边为key那么就右边先走,如果右边为key那么就左边先走,其中这里的key并不是某一个固定的值,我们可以选数组其他位置的值为key但是那样的话容易出错,所以我们可以选择左边或者右边的值为key,那么这样我们就一趟排序结束了
这时候我们就可以想,怎么样可以把他排序好
我们这时候继续看一下
这时候我们的6已经拍好了,所以我们就不需要在管6了,我们就可以让他继续
递归下去,以一边的right以6这个位置-1为末尾,另一边以6这个位置+1为起始点
然后我们继续递归
就这样下去我们就可以依次拍好,让每一个值的左边都是小于他的右边都是大于他的,这里我们认为如果只剩下一个数字那么就是有序的。所以这里如果l不小于r那么就 只剩下一个数字
最后排序好就是这样
就是这样,然后我们就排序好了
下面我们就来看一下代码
文章来源地址https://www.toymoban.com/news/detail-400094.html
首先我们这里定义key为left,然后我们就开始找大和小,然后让他们交换,知道left不小于right说明已经找完了,最后让left和right相遇的位置和key位置的值交换,然后就进行递归
你们可以画一下递归展开图
就是这样,主要是这里画递归展开图太麻烦了,就不画了,而且之前在树遍历那一块画了很多遍,思想已经传达到了
这个就是快排
完了介绍快排的时间复杂度
文章来源:https://www.toymoban.com/news/detail-400094.html
到了这里,关于冒泡排序 && 快排(hoare递归)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!