python统计学习原理（学好python拿高薪系列二）

小伙伴们大家好，在前几期我们分享了数据结构中搜索与排序的内容，那么今天我们总结一下搜索与排序算法中的重要知识点，然后结束这一部分。

• 稳定的排序

1、冒泡排序（起泡排序）

2、直接插入排序

3、归并排序

4、基数排序

• 不稳定的排序

1、选择排序

2、快速排序

3、希尔排序

4、堆排序

[注：] 选择排序为什么不稳定呢？

如原始数据序列为 8，5，8，7，9。当查找第二个大的数时，第一个8因为大于7，所以两者会交换位置，导致原始序列中的两个8相对位置发生了变化，所以不稳定。

1、不稳定

2、在同数量级的时间复杂度中O(nlogn)，快速排序性能最好

3、如果初始序列有序，则快速排序退化成冒泡排序，时间复杂度变为O(n^2 )

4、快速排序因为要递归调用，故借助栈来实现，栈最大深度[log2^n] 1向下取整

5、快速排序每次枢轴元素如果能将表分为长度相近的两个子表，此时快速排序速度最快，性 能最好

6、快速排序最大递归深度为n（初始序列有序的时候），最小递归深度为log2^n（枢轴元素将表等分的时候）

7、改进快速排序算法

• 如果进行了几趟快速排序后，子区间序列较小，则可以调整为直接插入排序
• 改变选择中轴值的方法，可以取头、中间、尾部的三个元素，再从三个元素中选取选取中间值作为枢轴元素

1、每一次都会选择一个最小的数放到前面，第i趟会从第i->n个位置进行关键字比较，选出一个最小的数放到i位置

2、与冒泡排序不同的是，选择排序无需进行频繁的元素交换移动，只需要进行关键字的比较，修改赋值即可。但是，不论初始序列如何，对于选择排序，所需要的关键字比较次数都为n(n-1)/2，即复杂度O(n^2)

3、选择排序的升级：

简单选择排序（不稳定，O(n^2)）--->树形选择排序（又叫锦标赛排序，O(nlogn),占用辅助存储空间较大）--->堆排序（不稳定，，O(nlogn)，占用辅助空间小）

好了，至此，搜索与排序的部分就告一段落了，最后用一张各种排序算法的效率比较图来镇楼吧，哈哈！