算法描述

假设待排数据存放在一维数组L[n]中，待排表在某一时刻的状态可分为三部分：（1）前面i个数据L[0],···,L[i-1]是已经使用直接插入排序排好的有序子表，简记为A。（2）第i个元素L[i]是本轮排序待排元素，简记为B。（3）后面n-i-1个元素L[i+1],···,L[n]是未排序的原始数据，简记为C。

每一轮排序需要做三件事：（1）找到B在A中的插入位置k；（2）将L[n]中位置k（包括L[k]）到i之间所有元素往后移一位；（3）将B复制覆盖元素L[k]。

从第二个元素到最后一个元素，需要进行n-1轮上述排序操作。

代码实现

// 直接插入排序，由小到大
#include <iostream>
#include <fstream>  // 从文件中读入数组元素
using namespace std;

const int n = 8;   // 数组长度恒为8

void insert_sort(int arr[], int i){
    int j = 0, elem = arr[i];
    while(arr[j] < elem && j < i) j++;
    for(int k=i; k>j; --k)
        arr[k] = arr[k-1];
    arr[j] = elem;
}

int main(){
    ifstream inFile;
    inFile.open("in.txt");
    int *arr = new int[n];

    for(int i=0; i<n; ++i) // 从文件读入元素
        inFile >> arr[i];
        
    for(int i=0; i<n; ++i) // 逐个排序
        insert_sort(arr, i);

    for(int i=0; i<n; ++i) // 输出排序后数组
        cout << arr[i] << " ";

    inFile.close(); // 关闭文件
    delete[] arr;   // 释放所申请空间
    return 0;
}

算法分析

（1）时间复杂度为O(n²)，空间复杂度为O(1)。（2）是个稳定的排序方法。（3）适用于以顺序表和链表形式存储的数据。