（自己手打的python实现代码以及整理的各路大神总结的知识点）
自用学习笔记，由于基于北美cs学习，文章大量中英混杂（谨慎食用）
十大排序算法:
插入排序
1)Insertion Sort 简单插入排序：
2)Shell sort(希尔排序):突破n^2
交换排序
3)Bubble sort:两两比较
4)Quicksort
选择排序
5)Selection Sort选择排序:选出最小的
6)Heap sort (堆排序，二叉树的代言人)：
稳定的nlog，平常一般不用，常数太大
归并排序
7)Merge sort(分治DC的典型代表)
非比较类排序：
8)Counting sort 计数排序：平凡的线性counting/排序
9)Radix Sort 基数排序
10)Bucket Sort 桶排序
Time complexity vs Space Complexity
- 时间复杂度：表示的是计算机的操作次数, 用Big O notation表示
常见的 time complexity 复杂度量级(从快到慢)
- O(1)【无论代码多长，只要没有循环】
- O(logN)【ie. for i
- O(n)【for里循环n遍】
- O(nlogN)【在2)的基础上循环n遍】
- O(n^2)【把O(n)再嵌套循环一次】
- O(n^3)
- O(n^k)
- O(2^n)【ie. T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，斐波那契数列(Fibonacci sequence)通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。所以可以表示为 O((5/3)^n)，简化后为 O(2^n)。】
2.空间复杂度：算法运行过程中临时占用内存储蓄空间大小的一个度量
3.稳定：如果a=b，a原本在b前面，排序之后a仍然在b的前面。
4.不稳定：如果a=b，a原本在b的前面，排序之后 a 可能会出现在 b 的后面
1.插入排序
1）Insertion Sort:简单插入排序
idea: 模拟扑克牌理牌的归类思路
时间复杂度：
- 平均：O(n^2) (每轮操作O(n)次，共O(n)轮)
- worst：O(n^2)
- best: O(n)
稳定性：稳定
适用于: 处理数据量比较少且基本有序的数据
process: 从第二个元素开始，与左边的第一个元素比较，如果比#1元素小，则插在#1的左边；如果比#1元素大，则无需移动，直接进行到#3开始比较，此时前面有两个元素，从最靠近的开始比较，如果比谁大就插入在谁的右边
python 实现代码如下：
2）Shell Sort 希尔排序
idea:插入排序的改进版，把较大的数据集合逻辑上分割(并没有实际分组操作)成若干个小组，然后对每个小组分别进行插入排序，即多了一个增量(gap)以及增量序列
适用于：中等规模数据
稳定性: 不稳定
时间复杂度：
- 平均: O(n^1.3)
- worst：O(n^2) 增量序列为 {1,2,4,8.....}
- best：O(n)
python 实现代码如下：
process：增量的存在是将index相差增量的分到一组
比如arr ：5，7，8，3，1，2，4，6
[index: 0，1，2，3，4，5，6，7]
length = 8, 这个的gap = 4,
此时a[0],a[4]一组，a[1],a[5]一组,...每个组进行insertion sort
for i in range(gap, n) - for i in range(4, 8)：选定index为4，5，6，7的数
lst[i - gap]: index4，5，6，7的分别对应index0，1，2，3
如果index在前面的value大，就换位置，这一轮排序完为
1，2，4，3，5，7，8，6
然后继续缩小增量
第二轮的增量为 gap//=2 为2, 则又变遍历一次for i in range(gap, n) - for i in range(2, 8)
此时为a[0],a[2],a[4],a[6]一组，a[1],a[3],a[5],a[7]一组，每个组进行insertion sort
lst[i - gap] > lst[i]：a[0]先和a[2]比，
- 如果a[2]比a[0]大则跳出while 继续遍历for：开始a[1]和a[3]比，a[2]和a[4]比....(每轮每个组轮流来一个，不是先完成一个组再进行另一个组
- 如果a[0]比a[2]大则交换，i -=gap 的存在原理即为insertion sorting：在本组内，和前面所有元素比，以保证这个元素比左边的所有元素大，则跳出while继续for
直到 i - gap <0 停止（因为是从index大的顺着gap找index小的对应，如果i-dex小于0则表示已经遍历所有了
其他代码实现详情可见https://mp.weixin.qq.com/s/4kJdzLB7qO1sES2FEW0Low
交换排序
1. Bubble sort
- idea: 比较相邻的元素，如果前面的大则交换；针对所有元素重复上述步骤，除了最后一个。即对n个数据操作n-1轮，每轮找出一个最大值(会被移到最后面)
- 时间复杂度：O(n^2)【(n-1)+(n-2)+....+1= n(n-1)/2，等差数列求和，去掉常数系数】(平均=worst)， O(n) (best)
- 稳定性：稳定
- python 代码实现：
2. Quick Sort
idea: 选择一个数作为pivot，把小于这个数的放在左边，大于这个数的放在右边，然后再继续进行分割(partition)和递归(recurision)
时间复杂度：
- O( n
N)(平均&Best)
- O(n^2) worst
稳定性：不稳定
python 代码实现：
未完待续。。