冒泡排序 快排(hoare递归)

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

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

假设我们又以下数组

我们想要对他进行排序

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

 

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那么就 只剩下一个数字

最后排序好就是这样

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

下面我们就来看一下代码

 

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

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

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

这个就是快排

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