可以插入排序嗎？

-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

可以插入排序嗎？

回答

相關問題