algorithm - 插入排序可以是后序吗？

Question

public class insSort {
int i,j,key; //j=1

public void rec(int a[],int pos){

    if(pos>a.length-1){
        return;
    }
    key= a[pos];
    i=pos-1;
    while((i>=0)&&(a[i]>key)){//swapping
            a[i+1]=a[i];
            i--;
            a[i+1]=key;
        }
        pos++;
        rec(a,pos);//post order
    }

它可以被视为插入排序吗？还是应该有序？递归算法按顺序使用是一种普遍做法吗？如果是，为什么会这样？

Answer 1

问题中的示例代码是尾递归版本，编译器可能会将其优化为循环（无递归）。我通过一些小的清理将示例代码转换为 C++。初始调用应该是 rec(1)（初始值 pos == 1）。

class insSort
{
public:
    int a[8];

    void rec(int pos){
    int i,value;
        if(pos >= (sizeof(a)/sizeof(a[0])))
            return;
        value = a[pos];                       // get value
        i = pos-1;
        while((i >= 0) && (a[i] > value)){    // shift up
            a[i+1] = a[i];
            i--;
        }
        a[i+1] = value;                       // insert value
        pos++;
        rec(pos);
    }
};