插入排序（InsertSort）

本文主要总结了插入排序的相关知识，其中包括插入排序的特点、原理和直接插入排序的完整实现代码。

插入排序

插入排序特点

• 稳定排序
• 算法简便，且容易实现
• 空间复杂度：O(1)；时间复杂度：平均O(n^2)
• 也适合用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针
• 更适合于初始记录基本有序（正序）的情况，当初始记录无序，n较大时，此算法时间复杂度较高，不宜采用

插入排序过程(原理)

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

完整代码实现（直接插入排序）

#include<iostream>
#include<string>

using namespace std;

//插入排序
void InsertSort(int arr[], int len)
{
    int j = 0;		//保存要替换的位置（数组下标）
    int temp = 0; //保存提取的未排序的元素值
    for (int i = 1; i < len; i++)
    {
        //提取未排序的元素
        temp = arr[i];
        for (j = i-1; j >= 0&&arr[j]>temp; j--)
        {
            arr[j + 1] = arr[j]; 
        }
        arr[j+1] = temp;
    }
}
//数组打印
void printArr(int arr[],int len,int start = 0)
{
    cout << "{";
    for (int k = 0; k < len; k++)
    {
        if (k == len - 1)
        {
            cout << arr[k] << " }";
        }
        else
        {
            cout << arr[k] << "，";
        }
    }
    cout << endl;
}

void test02()
{
    int arr[8] = {3,5,2,6,1,4,9,8};
    int len = 8;
    cout << "插入排序前：" << endl;
    printArr(arr, len);
    cout << "插入排序：" << endl;
    InsertSort(arr, len);
    cout << "插入排序后：" << endl;
    printArr(arr,len);
}
int main()
{
	test02();
	system("pause");
	return 0;
}