插入排序

1. 概念定义

插入排序（Insertion Sort），一般也被称为直接插入排序，是一种简单直观的排序算法。

工作原理：将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。

这个过程类似于平时打扑克牌时摸牌的操作：右手摸牌，根据牌面大小，放到左手中正确的位置。

这里有张动图，但是好像放不上来

比如：1 2 6 3 4 7 5 ，将其从小到大排序。

第一次参与排序的数据：2 6 3 4 7 5（因为最开始没有[已排序的]，所以第一个数可以直接作为[已排序的]）

第一次循环：

当前的数：2

当前已有序列表：1

2 > 1 : 2 放在 1 之后

第二次参与排序的数据：6 3 4 7 5

第二次循环：

当前的数：6

当前已有序列表：1 2

6 > 2 : 6 放在 2 之后

第三次参与排序的数据：3 4 7 5

第三次循环：

当前的数：3

当前已有序列表：1 2 6

3 < 6 :

3 > 2 : 3 放在 2 之后

第四次参与排序的数据：4 7 5

第四次循环：

当前的数：4

当前已有序列表：1 2 3 6

4 < 6 :

4 > 3 : 4 放在 3 之后

第五次参与排序的数据：7 5

第五次循环：

当前的数：7

当前已有序列表：1 2 3 4 6

7 > 6 : 7 放在 6 之后

第六次参与排序的数据：5

第六次循环：

当前的数：5

当前已有序列表：1 2 3 4 6 7

5 < 7 :

5 < 6 :

5 > 4 : 5 放在 4 之后

至此，数据全部排序为：1 2 3 4 5 6 7

具体实现：使用双层循环，外层循环枚举除了第一个元素之外的所有元素，内层循环遍历当前元素前面的有序表，进行待插入位置查找，并进行移动。时间复杂度为O(n^2^)，空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insertionSort(int *number, int n)    //定义一个插入函数"insertionSort" 
{
    int i, j, tmp;  
    for(i = 1; i < n; i++)  //循环遍历 
    {
        tmp = number[i];  //将tmp每一次赋值为number[i]  
        for(j = i-1; j >= 0; j--)  //比较
        {
            if(tmp < number[j]) number[j+1] = number[j];  //更小交换
            else break;
        }
        number[j+1] = tmp;   //否则添加到最后
    }
}

2. 题目练习

  1. 合并两个有序数组（基础题）
  2. 对链表进行插入排序（提高题）

3. 解题报告

合并两个有序数组

题目描述

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

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

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

解题思路

先将 nums2 的元素放到 nums1 里去，然后对整个 nums1 数组进行插入排序。

C代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void insertionSort(int *number, int n)    //定义一个插入函数"insertionSort" 
{
    int i, j, tmp;  
    for(i = 1; i < n; i++)  //循环遍历 
    {
        tmp = number[i];  //将tmp每一次赋值为number[i]  
        for(j = i-1; j >= 0; j--)  //比较
        {
            if(tmp < number[j]) number[j+1] = number[j];  //更小交换
            else break;
        }
        number[j+1] = tmp;   //否则添加到最后
    }
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int i,j= 0;
    for(i = m; i < m+n; i++)  //合并数组
    {  
        nums1[i] = nums2[j];
        j++;
    }
    int size = m + n;
    insertionSort(nums1, size);  //排序
}

对链表进行插入排序

题目描述

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

解题思路

利用直接插入排序的算法思想，单链表无法向前遍历，需要通过三个指针完成操作。

C代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* insertionSortList(struct ListNode* head){
    if(head == NULL)                                                        //链表为空
        return NULL;
    
    struct ListNode* L = (struct ListNode*)malloc(sizeof(struct ListNode)); //辅助结点
    L->next = head;
    struct ListNode *cur = head->next, *pre = head, *tmp;

    while(cur != NULL){                                                     //遍历链表
        if(cur->val >= pre->val){                                           //寻找需要向前插入的结点
            cur = cur->next;
            pre = pre->next;
        }else{
            tmp = L;
            while(tmp->next->val < cur->val)                                //寻找插入位置
                tmp = tmp->next;
            pre->next = cur->next;                                          //进行插入
            cur->next = tmp->next;
            tmp->next = cur;
            cur = pre->next;
        }
    }

    return L->next;
}