[算法训练营] stack sort

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[算法训练营] stack sort，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1404字，纯文字阅读大概需要3分钟。

内容图文

问题描述

利用stack实现insertion sort。

输入

待排序数字序列的个数，以及待排序的数字序列。

输出

已排序的数字序列。

样例输入

10

1 5 4 2 3 9 8 7 2 0

样例输出

0
1
2
2
3
4
5
7
8
9

思路

分为两个栈，栈S储存最终输出的结果，栈R存储待处理的数字。在两个栈之间调用栈的接口实现插入排序即可。

代码

#include <iostream>
#include <stack>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::stack;
using std::vector;

stack<int> sorting(stack<int> myStack);

int main()
{
    int n;
    cin >> n;
    stack<int> myStack;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        myStack.push(tmp);
    }
    stack<int> result = sorting(myStack);
    vector<int> answer;
    while (!result.empty()) {
        answer.push_back(result.top());
        result.pop();
    }
    for (auto i = answer.rbegin(); i != answer.rend(); i++)
        cout << *i << endl;
    return 0;
}

stack<int> sorting(stack<int> myStack)
{
    stack<int> result; // 输出栈

    if (myStack.empty()) // 边界情况
        return result;

    int tmp = myStack.top(); // 下一个要插入到result中的数

    myStack.pop();

    while (!myStack.empty() || (!result.empty() && result.top() > tmp)) { // 判断最后的tmp放进去会不会出现无序的情况
        if (result.empty() || result.top() <= tmp) { // 需要保持稳定性且避免重复元素
            // result.empty()的次数等于原序列中，比它左边所有元素小的元素个数
            result.push(tmp);
            tmp = myStack.top();
            myStack.pop();
        } else {
            // else的次数等于原序列的逆序数
            myStack.push(result.top());
            result.pop();
        }
    }

    result.push(tmp); // 放入最后的tmp

    return result;
}

内容总结

以上是互联网集市为您收集整理的[算法训练营] stack sort全部内容，希望文章能够帮你解决[算法训练营] stack sort所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---