C++排序數組遞歸

我正在創建一個小程序，應該按升序對數組中的整數進行排序，但我非常卡在我應該使用的算法中。我不能迭代數組，我必須使用遞歸函數。我被允許有一個輔助函數，它可以在數組中找到最小的索引，我已經成功完成了這個工作，但是我正在最困難的時候弄清楚如何使用該函數對遞歸函數中的數組進行排序。這裏是我到目前爲止的代碼，我明白我的sortIntegers函數是關閉的。C++排序數組遞歸

int main() 
{ 
    int numbers[] = {8, 2, 5, 1, 3}; 
    sortingIntegers(numbers, 5); 
    return 0; 
} 

void sortingIntegers(int *list, int size) { 
    if (size == 1) { 
     for (int i = 0; i < size; i++) { 
      cout << list[i] << ", "; 
     } 
    } else { 
     for (int z = 0; z < size; z++) { 
      if (list[size - 1] == smallestIndex(list)) { 
       for (int y = 0; y < size; y++) { 
        swap(list[z], list[y]); 
       } 
      } 
     } 
     sortingIntegers(list, size - 1); 
    } 

} 

int smallestIndex(int *array) { 
    int smallest = array[0]; 
    for (int i = 1; i < sizeof(array); i++) { 
     if (array[i] < smallest) { 
      smallest = array[i]; 
     } 
    } 
    return smallest; 
}

來源

2015-02-10 andayn

您是否需要使用遞歸實現一些特定的排序算法？ – DixonD 2015-02-10 07:25:17

@DixonD，我不需要使用任何特定的排序算法，除了它必須利用遞歸函數進行排序。 – andayn 2015-02-10 07:34:54

如果你正在遞歸，你不應該循環。 – molbdnilo 2015-02-10 07:41:27

int main() 
{ 
    int numbers[] = {8, 2, 5, 1, 0}; 
    sortingIntegers(numbers, 0, 5); 
    for (int i=0;i<5;i++) 
     cout << numbers[i] << ' '; 
    return 0; 
} 

void sortingIntegers(int *list, int left, int size) { 
    if (left == size) 
     return; 
    int smallest = smallestIndex(list, left, size); 
    int c = list[smallest]; 
    list[smallest] = list[left]; 
    list[left] = c; 
    sortingIntegers(list, left+1 ,size); 
} 

int smallestIndex(int *array, int left, int size) { 
    int smallest = array[left]; 
    int smIndex = left; 
    for (int i = left+1; i < size; i++) { 
     if (array[i] < smallest) { 
      smallest = array[i]; 
      smIndex = i; 
     } 
    } 
    return smIndex; 
}

這是基於你的我的解決方案。首先sizeof(array)返回指針的大小。其次，我返回最小項目的索引，而不是它的值，然後將它與列表中的第一個元素進行交換。然後我從另一個元素（left參數）開始，爲列表調用排序，因爲我知道列表最多爲left-1已經排序。

來源

2015-02-10 07:47:55 prajmus

非常感謝你，我在想如何才能找到數組中的哪個元素是最小的，所以我可以將它傳遞給sortedIntegers函數，答案非常明顯，但我看不到它。再次感謝。 – andayn 2015-02-10 07:53:02

一個完全遞歸溶液：

要排序的陣列，找出最小的元素，並將其交換到第一位置。然後對數組的其餘部分進行排序，直到剩下單個元素。

要找到數組中最小的元素，取第一個元素和數組其餘元素中最小的元素中最小的元素，直到剩下單個元素。

int SmallestIndex(int Array[], int From, int To) 
{ 
    if (From == To-1) 
    return From; // Single element left 

    // Index of the smallest in the rest 
    int Index= SmallestIndex(Array, From + 1, To); 

    // Index of the smallest 
    return Array[From] < Array[Index] ? From : Index; 
} 

void Sort(int Array[], int From, int To) 
{ 
    if (From == To-1) 
    return; // Single element left 

    // Locate the smallest element 
    int Index= SmallestIndex(Array, From, To); 

    // Swap it to the first place 
    int Swap= Array[Index]; Array[Index]= Array[From]; Array[From]= Swap; 

    // Sort the rest 
    Sort(Array, From + 1, To); 
}

撥打電話Sort與(Array, 0, N)。

來源

2015-02-10 09:04:48

C++排序數組遞歸

回答

相關問題