数据结构作业W6-526互联

题号：T231564 【模板题】直接插入排序

题目链接：https://www.luogu.com.cn/problem/T226636

题目描述

读入

这里排序指的是升序。

输入格式

两行，第一行一个正整数

第二行为

输出格式

一行，排序后的

输入输出样例

输入

5
4 2 4 5 1

输出

1 2 4 4 5

说明/提示

每个数不超过

直接插入排序把新的数据插入已经排序好的数列中
排序的基本方法是：每一步将一个待排序的元素按其排序码的大小插入到前面已经排好序的一组元素的适当位置上去直到元素全部插入为止。
实质上就是从第二个元素从后往前开始进行扫描，把扫描到的元素当"极小值"与前面元素作比较
如果前面的元素大于当前扫描到的"极小值"，则把数组元素就往后挪，直到找到合适位置插入

参考代码：

#include <iostream>
using namespace std;

const int maxSize = 100;

template<typename T>//定义类模板，虚拟类型名为T
void insertSort(T arr[], int length)
{
    for(int i = 1; i < length; i++)//这里从第二个开始遍历到最后一个元素
    {
        int temp = arr[i]; // 把当前扫描的"极小值"记下来
        int j = i - 1;//记下前面的元素，与极小值做对比;

        while(j >= 0 && arr[j] > temp) { // 往前找插入的位置
            //遍历前面元素，与"极小值"做对比，当前面的元素大于极小值时，这时候因为极小值已经被temp给记录下来了，可以挪动数组元素，让前面的元素往后挪。
            // 这里的j之所以可以等于0，是因为从后往前比较，比较时要比较到第0个元素。
            arr[j+1] = arr[j]; //极小值元素已经记录，可直接挪动数组元素 往后移
            j--;
        }
        arr[j+1] = temp;//最后让j+1的数组直接等于极小值元素，也就是插入到合适的位置，
    }

}

int main(void)//用main函数
{
    int i, n, arr[maxSize];

    cin >> n;//输入要排序的数的个数
    for(i = 0; i < n; i++)
        cin >> arr[i];//输入要排序的数
    insertSort(arr, n);
    for(i = 0; i < n; i++)
        cout << arr[i] << " ";//输出排序后的数
    cout << endl;
    return 0;
}