插入排序

发表于 | 分类于 |
字数统计: 291 字 | 阅读时长 ≈ 1 分钟

插入排序是一种最简单直观的的排序算法，它的工作原理是通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

插入排序的原理应该是最容易理解的，因为只要打过扑克牌的人都应该能够秒懂。

算法步骤

  1. 将第一待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；
  2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置；

动图演示

insertionSort

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename T>
void insertionSort(T arr[], size_t len) {
    for (int i = 1; i < len; i++) {
        T temp_v = arr[i];
        
        // 从后往前遍历，查找合适的插入位置
        int j = i-1;
        while (j >= 0 && temp_v < arr[j]) {
            // 不合适的元素往后移
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp_v;
    }
}

int main(int argc, const char * argv[]) {
    int arr2[] = {99, 4, 6, 8, 5, 9, -1, -2, 100};
    insertionSort(arr2, sizeof(arr2) / sizeof(int));
    return 0;
}