前言

学习python数据结构与算法，学习常用的算法，

16.快速排序原理介绍

快速排序：快 快速排序思路： 取一个元素p(第一个元素)，使元素p归位； 列表被p分成两部分，左边都比p小，右边都比p大； 递归完成排序 先将5完成归位，然后将列表分成左边和右边两个部分，左边再进行归位，将2归位，分成1和4，3 两个部分，再使右边的4归位。右边列表也一样。现在主要实现归位的算法，再递归左边和右边就能实现整个代码。 快速排序-框架 quick_sort(data,left,right)中，left的下标是0，right的下标是8，left<right时，列表至少有两个元素，left=right时，只有一个元素，意思是有两个或两个以上的元素需要递归，否则不需要递归，一个元素是有序的，然后把列表分为两部分，递归调用quick_sort。

然后实现partition这部分代码 先把5用一个变量存起来，然后从right处找比5小的数放到5本来的空位上，找到2，把2放过去，这时右边2本来的位置空了出来，我们要把比5大的数放在右边，所以这时从左找，7比5大，放到右边去，这个过程是从left的位置的数，放到rightd的位置。 放完继续从右边开始找，把比5小的数放到左边空缺的位置上，这里也是，把right位置上的数放到左边left的位置，然后重复这个过程， 最后3放到位置上从左边找比5大的数放右边时，left和right重合了，说明这个位置就为中间了，这时把5放进去，就归位了。

17.快速排序代码实现

先存一个变量tmp, 直到left = right 算是找到了，所以 while left <right: 在最外面。 如果列表左边的1，2，3，4也是6，7，8，9，那么从右边的列表往左边找，就一直成立，因为都比5大，就跳不出这个循环了，所以while li[right] >= tmp: 要在这里检测一下,当left<right时才成立，left=right时说明找到这个位置，就退出这个循环了。 right= right-1 往左走一格，找到比tmp小的数，就把right的值写到left位置上。 从左边找同理。

最后把5归位了。

18.快速排序代码实现2

快速排序的效率： 快速排序的时间复杂度O(nlogn) 每次把列表分成一半，一共logn层，每一层是O(n)的复杂度，所以时间复杂度是O(nlogn) 如果在这里加装饰器，因为它是个递归函数，所以它每次递归也要调用装饰器，会打印很多次时间， 所以我们把他套一个马甲，正好把传入的参数就变成一个列表，这时就不会是递归函数，就只会打印一次时间了， ,这里用copy的深拷贝，复制了和li列表一摸一样的两个列表，进行排序时间比较，发现时间差的很多，差了100倍，效率很高。 快速排序的问题： 递归对于python来说设计到一个最大深度的问题，递归会消耗很相当一部分的系统资源 最坏情况：列表[9,8,7,6,5,4,3,2,1] 把9归位，9归位在最右边，分为两个部分，9一个部分，1，8，7，6，5，4，3，2 一个部分，并没有少一半，下面过程类似，每次只少了一个值，就不会出现nlogn,而是O(n^2)。

这里时间就慢很多了 优化： 将第一个数随机与列表中的一个数先交换，就会使最坏情况的出现率大大降低，也会可能随机到，但不能设计出来了。 冒泡排序的最好情况只有一个为O(n),一般情况为O(n^2) 快速排序的最坏情况只有一个为O(n^2),一般情况为O(nlogn) 上网还找到一个优化方式，尾递归， 优化后时间明显减少。

总结

学习了快排原理和实现