可以插入排序吗？

-1

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 
    }

它可以被认为是插入排序吗？或者它应该是有序的？这是一个普遍的做法，使用有序的递归算法？如果是的话为什么会这样？可以插入排序吗？

来源

2015-09-02 Muthukumaran R

我不熟悉您在这里使用“按次序”和“后序”。你能解释一下你的意思吗？你问是否在当前做这项工作是正常的，然后*做递归而不是递归到全面的深度并在出路上完成工作？ –

@JimMischel正确！如果代码没有全面深入，不会被认为是递归吗？ –

没有什么说递归必须先深入全面。例如，考虑如何递归扫描目录树。您将访问目录节点，然后访问其所有子节点。或者对二叉树进行预订或按顺序扫描。两者都是递归的。 –

问题中的示例代码是一个尾递归版本，编译器可以优化为一个循环（无递归）。我将示例代码转换为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); 
    } 
};

来源

2015-09-03 03:47:29 rcgldr

可以插入排序吗？

回答

相关问题