InsertSort-插入排序

​ 老实讲，自己算法水平就是个战五渣，大二数据结构学的还行，但是过了一学期也记忆模糊，加上从来没有接触过算法训练，而且下学期的算法课……

​ 种种原因促使我得靠假期恶补下自己的算法水平，算法还是用c++写吧，java总觉得怪怪的，类似于拿着叉子吃面？也算是个人偏见吧==

/*
	Name: InsertSort 插入排序 
	Copyright: SUST 
	Author: SunnyGrocery  
	Date: 12/07/19 00:49
	Description: 空间复杂度要求为O(1)  
*/
#include<iostream>
#include<stack>
#include<string>
using namespace std;

static const int SIZE = 10; 

stack<int> insertSort(int* random){

    stack<int> R ;//random
    stack<int> S ;//sorted

    for(int i ;i<SIZE;i++){
        R.push(random[i]);
    }
    //取出待排序栈栈顶元素 ,以临时变量t保存 
    int t = R.top();R.pop();
    /**
    *(!S.empty() && S.top() > t)是为了当判定当R为空时，t是否小于S的栈顶元素
    *如果小于，则还需要进入循环(首先进入else),直到最后当R为空时，t将大于有序列的栈顶元素
    *保证了将最后的t压入时，S不受最后t的影响，仍有序
    */
    while(!R.empty() || (!S.empty() && t < S.top())){
        //小于等于号保证了此算法为稳定排序 
        if(S.empty()||S.top() <= t){
            S.push(t);//有序列压入t
            t = R.top(); R.pop();//更新t 
        }else{
            R.push(S.top());S.pop();//显然S不为空，若t比S栈顶元素小则 将S中元素放入R中暂存 
        }
    }
    //将最后的t压入S中 
    S.push(t);
    return S;
} 
int main(){
	int random[SIZE] = {5,7,6,9,8,1,0,3,2,4};
	stack<int> T = insertSort(random);
	while(!T.empty()){
		cout << T.top()<<" ";
		T.pop();
	}
}