跳转至

DS内排—直插排序

时间限制: 1 Sec 内存限制: 128 MB

题目描述

给定一组数据，使用直插排序完成数据的升序排序。

--程序要求-- 若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件，不看代码，作0分处理 不允许使用第三方对象或函数实现本题的要求

输入

数据个数n，n个数据

输出

直插排序的每一趟排序结果

样例输入

1
7 34 23 677 2 1 453 3

样例输出

1
2
3
4
5
6
23 34 677 2 1 453 3
23 34 677 2 1 453 3
2 23 34 677 1 453 3
1 2 23 34 677 453 3
1 2 23 34 453 677 3
1 2 3 23 34 453 677

提示

解决方案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>

int main() {
    int size;
    std::cin >> size;
    std::vector<int> vector(static_cast<size_t>(size));
    for (int i = 0; i < size; ++i) {
        std::cin >> vector[i];
    }

    for (int i1 = 1; i1 < vector.size(); ++i1) {
        int key = vector[i1];
        for (int i2 = i1 - 1; i2 >= 0; --i2) {
            if (vector[i2] > key) {
                vector[i2 + 1] = vector[i2];
                vector[i2] = key;
            } else {
                break;
            }
        }
        std::cout << vector.front();
        for (int i = 1; i < vector.size(); ++i) {
            std::cout << ' ' << vector[i];
        }
        std::cout << std::endl;
    }

    return 0;
}

评论