---
title: Sorting 排序
math: true
---

+ 插入排序
+ 选择排序
+ 冒泡排序

| 排序     | 是否稳定 | 最坏情况时间       | 平均/期望时间      | 空间复杂度 |
|----------|----------|--------------------|--------------------|------------|
| 插入排序 | 稳定     | $ \Theta( n ^ 2) $ | $ \Theta( n ^ 2) $ | O(1)       |
| 选择排序 | 不稳定   | $ \Theta( n ^ 2) $ | $ \Theta( n ^ 2) $ | O(1)       |
| 冒泡排序 | 稳定     | $ O( n ^ 2 ) $     | $ O( n ^ 2 ) $     | O(1)       |
| 二分排序 | 稳定     | $ \Theta( n ^ 2) $ | $ \Theta( n ^ 2) $ | O(1)       |



## 插入排序
从第 **0** 个元素作为有序序列开始, 插入排序将元素 **插入** 到 **已排序序列** 的正确位置 并扩展已排序序列的边界

> 顺序由传入闭包决定

[![Insertion_sort](./insertion_sort.svg)](./insertion_sort.svg)

## 选择排序
选择排序按照指定的 **闭包** 每次找到第i最符合闭包条件的元素 并放到 **i** 上

> 顺序由传入闭包决定

[![Selection_Sort](./selection_sort.svg)](./selection_sort.svg)


## 冒泡排序
比较相邻的元素 如果 **顺序不一样** 则交换

当第 **1** 次循环结束后 ,最后的元素将成为 **最大或最小** 的元素, 并收缩右边界

> 顺序由传入闭包决定

[![Bubble_Sort](./bubble_sort.gif)](./bubble_sort.gif)

## 二分排序
对插入排序的二分优化

将插入点的寻找替换为二分查找 从0开始到的point的序列是有序的