数据结构 | 排序

插入排序

---

直接插入排序（空间复杂度为1，排序后稳定）

思路：

       在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
  但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
      最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1) 

---

 

折半查找（数列应该有顺序）

   时间复杂度（减少比较次数，而记录移动的次数不变）

---

 

希尔排序（缩小增量法）

---

交换排序 

---

 

冒泡排序

---

 

 快速排序

---

选择排序

---

 

直接选择排序

---

 

归并排序

动图演示：

---

 

 

基数排序

总结 

---

 

时间及空间复杂度