C++排序算法之插入排序原理和实现解析

插入排序原理

插入排序是一种简单的排序算法，它的基本思想是：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表。

插入排序的实现过程是：先从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤2~5。

插入排序实现

// C++实现插入排序
void InsertionSort(int arr[], int n)
{
    int i, j, temp;
    for (i = 1; i < n; i++)
    {
        temp = arr[i];
        j = i - 1;
        // 将大于temp的元素向后移动
        while (j >= 0 && arr[j] > temp)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

插入排序使用方法

使用插入排序的步骤如下：

• 将第一个元素视为已排序序列，取出下一个元素；
• 从后往前扫描已排序序列，如果发现已排序序列中的元素大于新取出的元素，就将已排序序列中的元素向后移动；
• 重复步骤2，直到找到已排序序列中的元素小于或者等于新取出的元素的位置；
• 将新取出的元素插入到该位置后；
• 重复步骤1~4，直到所有元素排序完毕。