# 排序

# 排序算法

• 不稳定：快速排序，选择排序，堆排序，希尔排序（快选堆希）

• 稳定：插入排序，冒泡排序，归并排序，基数排序（插冒归基）

算法的稳定性判断：排序前2个相等的数在序列中的前后位置顺序与排序后它们两个的前后位置顺序相同

# 归并排序

归并排序是一种递归算法，不断将列表拆分为一半，如果列表为空或有一个项，则按定义进行排序。

如果列表有多个项，我们分割列表，并递归调用两个半部分的合并排序。

一旦对两半排序完成，获取两个较小的排序列表并将它们组合成单个排序的新列表的过程。

# 快速排序

一种快速对数字进行大小排序的算法 时间复杂度为o（n2）空间复杂度为O（log2n）

而快速排序每次递归都会返回一个中间值的位置，必须使用栈

快速排序思想:

• 先找数组的最中间的一个数为基准
• 把数组通过此基准分为小于基准的left数组和大于基准的right数组
• 递归重复上面的两个步骤

# 冒泡排序

（应用于数据规模很小） 冒泡通俗讲就是参与排序的数据就像水中的气泡慢慢浮出水面一样“浮”到数列顶端。

冒泡排序要点：

• 两层循环，外层循环控制走访数列重复进行的次数，内层循环进行数据的比较、交换，是数据“上浮”。

• 内层循环是相邻的数据进行比较。

• 数组外循环次数就为数组长度。每一次外循环在内循环两两比较后，得到一个最大的值排到数组尾部