数据结构及其应用: 几种经典的插入排序算法详细解析及其代码实现(C++版本)

#内容归纳

内部排序类型索引：
-->插入排序
- 交换排序
- 选择排序
- 归并排序
- 计数排序

插入排序：(Insertion Sort)

插入排序的核心理念在于：在每次操作中，选取一个待处理的数据元素，依据其关键字的数值大小，将其放置至此前已排序好的子序列中合适的位置，直至所有数据元素均被正确安置。

目前共有五种不同的插入排序实现方式：
(1) 直接插入排序；
(2) 对半插入排序；
(3) 双向插入排序；
(4) 链表插入排序；
(5) 希尔排序。

（1）直接插入排序（Straight Insertion Sort）：

一种基础的排序方式，其核心理念是依次将待插入的数据项与已排序的部分进行比对，从而明确其应放置的具体位置。

算法的C++代码实现如下：

    	// 直接插入排序法，对容器 nums 进行排序
    void sInsertion(vector<int> &nums){
        int len = nums.size();
    
        for(int i = 1; i < len; i++){               // 以第一个数（nums[0]）为已排好序的部分，