算法稳定性

算法稳定性：相同元素，排序后不会改变相对位置，则为稳定的排序算法；

BubbleSort

冒泡：不断比较相邻两个数大小，进行交换 复杂度：

• 平均时间复杂度：$O(n^2)$
• 稳定排序（因为碰到相等元素不做处理）

QuickSort

快排：以第一个数为基准，小于基准放左边，大于放右边，分成两部分，递归下去； 复杂度：

• 平均时间复杂度：$O(nlog(n))$
• 空间：$O(1)$
• 不稳定（两数相等，会改变相对位置）

MergeSort

归并排序：先不断对半分割，再排序放回； 复杂度：

• 平均时间复杂度：$O(nlog(n))$
• 最差时间复杂度：$O(n^2)$
• 空间：$O(n)$
• 稳定

MaxHeap

复杂度：

• 平均时间复杂度：$O(nlog(n))$
• 空间：$O(1)$
• 不稳定（两数相等，会改变相对位置）

SelectionSort

选择排序：每次遍历剩余数组，找到最值放到前面； 复杂度：

• 平均时间复杂度：$O(n^2)$
• 空间：$O(1)$
• 不稳定

InsertSort

插入排序：从０维护一个窗口，两两相比，最小值移到最前，不断扩大窗口；

• 每一个窗口，都是已经排好序的； 复杂度：
• 平均时间复杂度：$O(n^2)$
• 空间：$O(1)$
• 稳定（因为碰到相等元素不做处理）

RadixSort

基数排序：比较数字每一位进行排序；放入新数组；直到每一位都比较完成；

• 需要额外空间；
• 排序次数取决于元素最大位数（111，1111，11111）

复杂度：

• 平均时间复杂度：$O(n*k)$
• 空间：$O(n+k)$
• 稳定（相同元素不做处理）

K-way MergeSort

K路归并排序：

• 解决K个数组，排序成一个数组的问题； 思路：

1. 每次从K个数组中，选出最大值，放入最大堆中；
2. 将堆顶元素，取出，放入结果数组中；
3. 再从堆顶原来所在数组取出最大值，放入最大堆；
4. 依次类推，直到最大堆内元素为0；