零、写在前面

????????今天是打卡的第35天，今天的难度一般般，赶紧写写复习考试了-.-知识点在：

《算法零基础100讲》(第35讲) 基础排序 - 插入排序https://blog.csdn.net/WhereIsHeroFrom/article/details/120876265

一、主要知识点

1.插入排序

每次选择一个元素插入前半部分，保证前半部分有序。

void InsertSort(int n, int *a) {       //插入排序
    int i, j;             //j用于查找插入位置
    for(i = 1; i < n; ++i) {
        int x = a[i];                  // 选择一个元素
        for(j = i-1; j >= 0; --j) {    // 查找插入位置
            if(x <= a[j]) {            // 后移
                a[j+1] = a[j];         
            }else
                break;                 // 找到位置
        }
        a[j+1] = x;                    // 插入
    }
}

二、课后习题?

88. 合并两个有序数组

88. 合并两个有序数组https://leetcode-cn.com/problems/merge-sorted-array/

题目描述

给你两个按非递减顺序排列的整数数组?nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

思路

合并之后的长度是 m + n，从后往前依次根据大小关系依次插入nums1就好了。其实就是归并排序的思想。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int size = m + n;//最终长度
    for(int i = m - 1,j = n - 1;i>=0||j>=0;){
        if(i<0) nums1[--size] = nums2[j--];  //nums1插入完了
        else if(j<0||nums1[i] > nums2[j]) nums1[--size] = nums1[i--];//nums2元素小于nums1
        else nums1[--size] = nums2[j--];        
    }
}

611. 有效三角形的个数

611. 有效三角形的个数https://leetcode-cn.com/problems/valid-triangle-number/

题目描述

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。?

这个看昨天的把

[解题报告]《算法零基础100讲》(第34讲) 排序入门 - 选择排序

147. 对链表进行插入排序

147. 对链表进行插入排序https://leetcode-cn.com/problems/insertion-sort-list/

题目描述

对链表进行插入排序。

思路

找到插入位置的前一个位置，然后按照头插法插入就好了。加入头节点可以统一操作。

struct ListNode* insertionSortList(struct ListNode* head){
    if(!head->next||!head)  return head;
    struct ListNode *p = head->next;
    struct ListNode anshead;    //头节点
    anshead.next = head;
    head = &anshead;
    head->next->next = NULL;  //分表 同时将第一个节点插入
    while(p){
        struct ListNode *q = head,*temp = p->next;
        while(q->next && q->next->val < p->val) q = q->next;//找到插入的前一个节点
        p->next = q->next;//头插法
        q->next = p;
        p = temp;
    }
    return head->next;
}