[题解]《算法零基础100讲》(第35讲) 基础排序 - 插入排序

• • 源码剖析
  • 88. 合并两个有序数组
  • 611. 有效三角形的个数
  • 147. 对链表进行插入排序

for(int i=1;i=0;j--) {
        if(nums1[j]>minn) nums1[j+1]=nums1[j];
        else break;
    }
    nums1[j+1]=minn;
}

从前往后依次遍历数组，对每一个元素都在他前面的位置找一个他应该放在的位置，然后把这个位置后面的所有元素往后推一个，把这个元素插入到里面

直接合并两数组以后对其进行插入排序

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        nums1.resize(m+n);
        for(int i=0;i=0;j--) {
                if(nums1[j]>minn) nums1[j+1]=nums1[j];
                else break;
            }
            nums1[j+1]=minn;
        }
    }
};

class Solution {
public:
    int triangleNumber(vector& nums) {
        int n=nums.size();
        for(int i=1;i=0;j--) {
                if(nums[j]>=minn) nums[j+1]=nums[j];
                else break;
            }
            nums[j+1]=minn;
        }
        int ans=0;
        for(int i=0;i>1;
                    if(nums[mid] 
147. 对链表进行插入排序 
 
 
链表的插排，依据插排的思想进行模拟。由于是单向链表不能反向遍历，所以需要先记录一下当前点
 
 
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
    ListNode* node=new ListNode(0);
    ListNode* pre=node;
    ListNode* cur=head;
    while(cur!=NULL){
            ListNode* tmp=cur->next;
            while(pre->next!=NULL&&pre->next->valval)pre=pre->next;
            cur->next=pre->next;
            pre->next=cur;
            pre=node;
            cur=tmp;
        }
    return node->next;
    }
};