盒子
盒子
文章目录
  1. 算法基础
    1. 插入排序

算法排序学习

从今天开始逐步开始学习算法部分的内容。

算法基础

插入排序

时间复杂度:$O(n^2)$

  • 插入排序的工作方式像排序一手扑克牌,开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较,然后找到合适的位置将其插入。然后重复抓牌,插入。
  • 理解原理之后,我们开始着手实现。先定义一个的数组 int arr[128] = { 5,1,8,7,4,2,3,9,6 }; 可以理解为洗好的牌。
  • 第二部开始抓第一张牌,然后再抓第二张拍,做比较,然后根据比较结果插入。这里我们采用一个 while 判断循环来实现 对比 → 插入 的过程。并且有多少张牌我们就要重复抓取几次,因此我们写一个 for 循环来进行抓牌。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int mun = 6; //假如现在有 6 张牌
int a[6] = { 5,2,4,6,1,3 }; //然后我们将 6 张牌洗乱
void InsertionSort()
{
for (int i = 1; i < mun; i++) //第一张牌不需要比较,对比是第二张牌开始的,所以 i = 1 。
{
int key = a[i]; //将牌抓到右手,避免插入的时候 arr[i] 被覆盖掉导致对比出错
int j = i - 1; //左手的牌是从第一张开始的,因此 j = i - 1 ,第一次循环时为 0 ,第二次为1,······
while (j >= 0 && a[j] > key)//这里开始进行从右到左的对比,直到最左边没牌为止。
{
a[j + 1] = a[j]; //若左手中右边的牌比左边的小,那么将左边的向右移一位
j--; //然后继续向左,
} //跳到 `while` 继续对比,直到左边比右边小结束循环。
arr[j + 1] = key; //对比完之后,将右手的牌插入进去,由于上面 `j--` 了一次,然后跳出了循环,因此这里需要`j+1`加一次,保证牌不会插左边去了。
} //第二张牌插完后,继续抓第三张对比插入,再第四张·····直到全部抓完。
}

下面用一个插图形象表示下

算法工作流程

练习:

  • [x] 根据上图为模型重写 void InsertionSort() 使之变降序排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int mun = 6;
int a[6] = { 5,2,4,6,1,3 };
void InsertionSort()
{
for (int i = 1; i < mun; i++)
{
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] < key) //将 > 改成 < ,变为降序排列
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
支持一下
扫一扫,支持 Lany