数据结构与算法-算法篇：排序—插入排序（三）

数据结构与算法系列文章：数据结构与算法目录

算法步骤：

1、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；

2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

实现：

/// <summary>
/// 插入排序
/// </summary>
/// <param name="arr"></param>
public void InsertSort(int[] arr)
{
    int len = arr.Length;
    for (int i = 1; i < len; i++)
    {
        int temp = arr[i];

        // 在已经排序好的元素中，从后往前比较
        for (int j = i - 1; j >= 0; j--)
        {
            if (arr[j] > temp)
            {
                // 交换元素
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
            else
            {
                // 有序元素未比较的元素中，没有比此元素大的了
                break;
            }
        }
    }
}

从代码里我们可以看出，如果找到了合适的位置，就不会再进行比较了，就好比牌堆里抽出的一张牌本身就比我手里的牌都小，那么我只需要直接放在末尾就行了，不用一个一个去移动数据腾出位置插入到中间。