插入排序

算法思路

插入排序：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，知道全部插入完成。

详细思路

从第二个元素开始寻找前面是否有比自己小的数，也就是要做到寻找的数的前面的所有数据都已经排好序了
利用类似交换位置的方法，利用 $temp = 待排数字$ ，相当于把这个位置移出去了，这个数字前面的数字可以直接往后依次移动一个位置（占据了带牌数字的位置）
因为待排数字已经记录了，并且比它大的数字向后挪，刚好给他空出一个比他小的数字后面一个的位置，这是就把他放进这个位置，这轮排序就结束了
要排序从第二数字到最后一个数字（第一个数字前面没有数字更没有比它大的数字，所以不用排）

时空间复杂度

时间复杂度

当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为 $O(N)$ 。
当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为 $O(N^2)$ 。
==总之，数据越接近正序，直接插入排序的算法性能越好。==

空间复杂度

由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 $O(1)$ 。

稳定性

直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。

动态图像理解

动态示意图

优化

因为在一个有序序列中查找一个插入位置，以保证有序序列的序列不变，所以可以使用二分查找，减少元素比较次数提高效率。
==这里的优化思路和冒泡排序的isswap比较类似，都是是想要减少交换次数，但是插入排序不能那么暴力直接结束，但是也可以用二分查找，找到下一个未排序好序的位置==

例如：当序列排序一轮后为1、2、3、2、4正常情况来说，会拿着这个三和前面比较两次（但实际上3不会先前移动，所以这次的比较是无意义的），所以就可以通过Binary Search来避免这种无意义的排序

==二分查找==是对于有序数组而言的，假设如果数组是升序排序的。那么，二分查找算法就是不断对数组进行对半分割，每次拿中间元素和目标数字进行比较，如果中间元素小于目标数字，则说明目标数字应该在右侧被分割的数组中，如果中间元素大于目标数字，则说明目标数字应该在左侧被分割的数组中。

源文件

未优化源文件

vector 更通用模板

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
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> insertSort(vector<int> list){
    vector<int> result;
    if (list.empty()){
        return result;
    }
    result = list;
    // 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
    for (int i = 1; i < result.size(); i++){
        // 取出第i个数，和前i-1个数比较后，插入合适位置
        int temp = result[i];
        // 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
        int j = i - 1;
        for (j; j >= 0 && result[j] > temp; j--){
            result[j + 1] = result[j];
        }
        result[j + 1] = temp;
    }
    return result;
}
 
int main(){
    int arr[] = { 6, 4, 8, 9, 2, 3, 1 };
    vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
    cout << "排序前" << endl;
    for (int i = 0; i < test.size(); i++){
        cout << test[i] << " ";
    }
    cout << endl;
    vector<int> result;
    result = insertSort(test);
    cout << "排序后" << endl;
    for (int i = 0; i < result.size(); i++){
        cout << result[i] << " ";
    }
}

数组简单理解

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
#include <iostream>

using namespace std;

void insertsort()//插入排序入口
{
    int a[] = {10, 8, 11, 7, 4, 12, 9, 6, 5, 3}; //待排序数组

    int size = sizeof(a) / sizeof(int);
    for (int i = 1; i < size; i++)
    {
        int temp = a[i]; //记录要排序是数据
        int j = i - 1;
        while (j >= 0 && a[j] > temp) //一直向前找是否有比temp小的数字，如果有比temp小的数字那么temp刚好排在它后面，结束寻找
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp; //排在这个数的后面，所以先j+1
    }
    for (int i = 0; i < size; i++)
        cout << a[i] << " ";
}

int main()
{
    insertsort();//调用插入排序
}

优化后源代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
 
using namespace std;
 
// 给定一个有序的数组，查找(第一个大于等于)value的下标，不存在返回-1,与普通的Binary Search有点不一样
int BinarySearch(vector<int> list, int n, int value){
    int left = -1;
    int right = n;
 
    while (left <= right){
        int middle = left + ((right - left) >> 1);
        if (list[middle] > value){
            right = middle;
        }
        else{
            left = middle;
        }
    }
    return (left < n) ? left : -1;
}
 
vector<int> BinaryInsertSort(vector<int> list){
    vector<int> result = list;
    for (int i = 1; i < result.size(); i++){
        int insert_index = BinarySearch(result, i, result[i]);
        if (insert_index != -1){
            int temp = result[i];
            int j = i - 1;
            while (j >= insert_index){
                result[j + 1] = result[j];
                j--;
            }
            result[j + 1] = temp;
        }
    }
    return result;
}
 
int main(){
    int arr[] = { 6, 4, 8, 9, 2, 3, 1 };
    vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
    cout << "排序前" << endl;
    for (int i = 0; i < test.size(); i++){
        cout << test[i] << " ";
    }
    cout << endl;
    vector<int> result;
    result = BinaryInsertSort(test);
    cout << "排序后" << endl;
    for (int i = 0; i < result.size(); i++){
        cout << result[i] << " ";
    }
}