【算法/数据结构】排序算法

插入排序 1.直接插入排序 从第一个元素开始 把 $0...i-1$的区域作为有序区，第 $i$ 个元素作为待插入元素，每次在有序区中查找其插入的位置 2.折半插入排序 与直接插入排序的区别就是每次查找插入位置的时候使用的是折半查找 以上两种排序都在排序区形成全局有序 $O(n^2)$ 3.shell排序 $O(n^{1.3})$ 不稳定 将数组间隔分组，在每个组内进行直接插入排序，逐渐增大每组的元素数量，直到只剩下一组

交换排序 1.冒泡排序 比较相邻元素之间的大小，满足某种排序性质时交换，每一轮实现一个元素的归位 一共进行 $n-1$ 轮 2.快速排序 不稳定 每层递归将该区间内的某个元素归位，使用双指针确定其位置，区间长度为单位长度时返回（递归出口）

选择排序 1.简单选择排序 不稳定 全局有序区初始为空，每次从无序区中选择一个最小元素，加入全局有序区，一共加入 $n-1$ 次 2.堆排序 不稳定 利用堆的根节点最小或最大性质，每次从堆中获取一个最小元素，加入全局有序区 选择排序的时间性能与序列是否有序无关

归并排序 1.二路归并

基数排序 分配和收集 对每个位进行一次