从今天开始逐步开始学习算法部分的内容。
算法基础
插入排序
时间复杂度:$O(n^2)$
- 插入排序的工作方式像排序一手扑克牌,开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较,然后找到合适的位置将其插入。然后重复抓牌,插入。
- 理解原理之后,我们开始着手实现。先定义一个的数组 int arr[128] = { 5,1,8,7,4,2,3,9,6 }; 可以理解为洗好的牌。
- 第二部开始抓第一张牌,然后再抓第二张拍,做比较,然后根据比较结果插入。这里我们采用一个 while 判断循环来实现
对比 → 插入
的过程。并且有多少张牌我们就要重复抓取几次,因此我们写一个 for 循环来进行抓牌。
|
|
下面用一个插图形象表示下
练习:
- [x] 根据上图为模型重写
void InsertionSort()
使之变降序排列
|
|