分类
排序算法 时间复杂度 是否基于比较 是否稳定排序 是否原地排序
冒泡 O(n^2) 是 是 是
插入 O(n^2) 是 是 是
选择 O(n^2) 是 否 是
快排 O(n*logn) 是 否 是
归并 O(n*logn) 是 是 否
桶 O(n) 否 是 否
计数 O(n+k) k是数据范围 否 是 否
基数 O(k*n) k是维度 否 是 否
如何分析排序算法
算法执行效率
1.分析最好情况、最坏情况、平均情况时间复杂度 && 排序算法在不同数据下的性能表现
2.时间复杂度考虑系数、常数、低阶
3.考虑比较次数和交换（或移动）次数
基于比较的排序算法执行过程，会涉及两种操作: 元素比较大小 和 元素交换或移动
衡量空间复杂度
算法稳定性: 稳定的排序算法(针对数据多次排序后的前后顺序始终不变)和不稳定多排序算法
冒泡排序(Bubble Sort)
特点
冒泡排序只会有操作相邻的两个数据，两种操作: 比较 和 交换
排序过程
每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。
如果不满足就让它俩互换。
一次冒泡会让至少一个元素移动到它应该在的位置，重复n次就完成n个数据的排序工作
属于原地排序算法
冒泡过程只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为O(1)
稳定的排序算法
当相邻两个元素大小相等时，我们不做交换，相同大小的数据在排序前后不会改变顺序
时间复杂度
最好情况时间复杂度为O(n): 数据已顺序排列
最坏情况时间复杂度为O(n^2): 数据已倒序排列
平均情况时间复杂度为O(n^2)
简单分析方式:有序度 和 逆序度 两个概念来进行分析
有序度: 数组中具有有序关系的元素对的个数(有序元素对：a[i] <= a[j]，如果i < j)
逆序度: 数组中具有逆序关系的元素对的个数(逆序元素对：a[i] > a[j]，如果i < j)
满有序度: 完全有序的有序度，计算公式: n*(n-1)/2
公式: 逆序度 = 满有序度 - 有序度
排序的过程是一种增加有序度，减少逆序度的过程，最后达到满有序度，即排序完成
示例: 我们要对一组数据4、5、6、3、2、1，从小到到大进行排序，冒泡排序过程如下:
插入排序(Insertion Sort)
特点
插入排序会操作当前数据与已排序区间数据，两种操作: 比较 和 移动
数组中的数据分为两个区间: 已排序区间和未排序区间。
初始已排序区间只有一个元素，就是数组的第一个元素。
排序过程
取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。
重复这个过程，直到未排序区间中元素为空，算法结束。
属于原地排序算法
插入排序算法的运行并不需要额外的存储空间，空间复杂度为O(1)
稳定的排序算法
对于值相同的元素，可以将后面出现的元素，固定插入到前面出现元素的后面
时间复杂度
最好情况时间复杂度为O(n): 数据已顺序排列
最坏情况时间复杂度为O(n^2): 数据已倒序排列
平均情况时间复杂度为O(n^2)
每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作
示例: 我们要对一组数据4、5、6、3、2、1，从小到到大进行排序，插入排序过程如下:
选择排序(Selection Sort)
特点
数组中的数据分为两个区间: 已排序区间和未排序区间。
排序过程
选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾
属于原地排序算法
插入排序算法的运行并不需要额外的存储空间，空间复杂度为O(1)
不稳定的排序算法
每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，破坏了稳定性
时间复杂度
最好情况时间复杂度为O(n^2): 数据已顺序排列
最坏情况时间复杂度为O(n^2): 数据已倒序排列
平均情况时间复杂度为O(n^2)
示例: 我们要对一组数据4、5、6、3、2、1，从小到到大进行排序，选择排序过程如下:
总结
是否原地排序 是否稳定 最好、最坏、平均时间复杂度
冒泡排序 是 是 O(n) O(n^2) O(n^2)
插入排序 是 是 O(n) O(n^2) O(n^2)
选择排序 是 否 O(n^2) O(n^2) O(n^2)
排序算法优先级: 插入排序 > 冒泡排序 > 选择排序
插入排序对比冒泡排序，时间复杂度一样但赋值代码次数少，执行时间效率高于冒泡排序
归并排序(Merge Sort)
特点
分治思想,将一个大问题分解成小的子问题来解决
分治算法一般是用递归来实现。分治是一种解决问题的处理思想，递归是一种编程技巧
排序过程
递推公式
merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1...r))
终止条件
p >= r 不用再继续分解
merge_sort(p...r)表示，给下标从p到r之间的数组排序
merge_sort(p...r)拆分为: merge_sort(p...q)和merge_sort(q+1...r)，下标q = (p+r)/2
将下标 从p到q 和 从q+1到r 这两个子数组分别排序，递归拆分
最后将两个有序的子数组合并，即排序完成
不是原地排序算法
归并排序中合并函数，合并两个有序数组为一个数组时，需借助额外存储空间
空间复杂度为O(n):
任意时刻，CPU只会有一个函数在执行，只会使用一个临时内存空间
临时内存空间最大也不会超过n个数据的大小
稳定的排序算法
关键点合并函数: 两个有序子数组合并成一个有序数组的代码
保证固定顺序合并,可以保证合并前后的先后顺序不变
时间复杂度
最好/最坏/平均情况时间复杂度为O(nlogn)
T(1) = C； n=1时，只需要常量级的执行时间，所以表示为C
T(n) = 2 * T(n/2) + n； n>1
T(n) = Cn + n*logn
T(n) = O(n*logn)
示例: 我们对一组数据11、8、3、9、7、1、2、3，从小到到大进行排序，归并排序过程如下:
快速排序(Quick Sort)
特点
分治思想
排序过程
选择分区点(pivot): 从数列中挑出一个元素
分区(partition): 重排数列，小于pivot放左边，大于pivot放右边，将pivot放中间
递归(recursive)把小于pivot元素的子数列和大于pivot元素的子数列各自排序
递推公式：
quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1, r)
终止条件：
p >= r
原地排序算法
关键点在于分区函数,分区函数原地完成分区操作,来实现空间复杂度为O(1)即可
见 原地分区操作实现图
不稳定的排序算法
分区操作时出现数据交换,相同的数值无法实现稳定点排序
时间复杂度
最好情况时间复杂度为O(nlogn): 分区极其均衡
每次分区都能拆分为两个大小接近相等的小区间
T(1) = C；当n=1时，只需要常量级的执行时间，所以表示为C
T(n) = 2 * T(n / 2) + n；n>1
最坏情况时间复杂度为O(n^2): 分区极其不均衡
例如有序数组每次取最后一个做为分区点
平均情况时间复杂度为O(n*logn)
T(n)在大部分情况下时间复杂度为O(n*logn)，只有在极端情况下，才会退化到O(n^2)
归并排序 PK 快速排序
快排和归并 -> 分治思想
归并排序: 由下到上先处理再合并,稳定排序、时间复杂度O(nlogn)、非原地排序
快速排序: 由上到下先分区再处理,不稳定排序、时间复杂度O(nlogn)、原地排序(内存占用少)
