目录
零、写在前面
一、主要知识点
1.插入排序
二、课后习题
88. 合并两个有序数组
611. 有效三角形的个数
147. 对链表进行插入排序
写在最后
零、写在前面
今天是打卡的第35天，今天的难度一般般，赶紧写写复习考试了-.-知识点在：
《算法零基础100讲》(第35讲) 基础排序 - 插入排序https://blog.csdn.net/WhereIsHeroFrom/article/details/120876265
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; }
