算法排序学习

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

算法基础

插入排序

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

• 插入排序的工作方式像排序一手扑克牌，开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，然后找到合适的位置将其插入。然后重复抓牌，插入。
• 理解原理之后，我们开始着手实现。先定义一个的数组 int arr[128] = { 5,1,8,7,4,2,3,9,6 }; 可以理解为洗好的牌。
• 第二部开始抓第一张牌，然后再抓第二张拍，做比较，然后根据比较结果插入。这里我们采用一个 while 判断循环来实现 对比 → 插入 的过程。并且有多少张牌我们就要重复抓取几次，因此我们写一个 for 循环来进行抓牌。

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() 使之变降序排列

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;
    }
}