408考研科目《数据结构》第八章第一节：排序的基本概念和插入排序（直接插入排序，折半插入排序，希尔排序）

教程

1. 排序： https://www.bilibili.com/video/BV1b7411N798/?p=77&share_source=copy_web&vd_source=d228985826b563972268952905224139
2. 插入排序：https://www.bilibili.com/video/BV1b7411N798/?p=78&share_source=copy_web&vd_source=d228985826b563972268952905224139
   3.希尔排序 （Shell Sort） https://www.bilibili.com/video/BV1b7411N798/?p=79&share_source=copy_web&vd_source=d228985826b563972268952905224139

1.排序的基本概念

排序(Sort)，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

1.1 排序算法的评价指标

• 时间复杂度
• 空间复杂度
  
  

1.2 排序算法的分类

一个神奇的学习网站:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

这个网站可以模拟每个基本算法的运算过程（推荐）

2. 插入排序

算法思想:每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中,直到全部记录插入完成。

2.1 直接插入排序

---

---

2.1.1 算法效率分析

---

---

2.2 折半插入排序

思路:先用折半查找找到应该插入的位置，再移动元素

总结

2.3 希尔排序 （Shell Sort）

---

---

---

总结

---