遞歸插入排序的C程序

插入排序是一種排序演算法，它是一種基於就地比較的演算法。

此演算法的工作原理是將元素放置在已排序子數組中的位置，即元素之前的子數組是排序子數組。

演算法

Step1 - 從 1 到 n-1 迴圈並執行 -

Step2 .1 - 選擇位置 i 處的元素，array[i]。

Step2.2 - 將元素插入已排序的子數組 array[0] 中其位置到 arr[i]。

我們透過一個例子來理解演算法

陣列 = [34, 7, 12, 90, 51]

對於i = 1，arr[1] = 7，放入子數組arr[0] - arr[1] 中的位置。

[7, 34, 12, 90, 51]

對於 i = 2，arr[2] = 12，放入子陣列 arr[0] - arr[2] 中的位置。

[7, 12, 34, 90, 51]

對於 i = 3，arr[3] = 90，將其放置在子數組 arr[0] - arr[3] 的位置。

[7, 12, 34, 90, 51]

對於 i = 4，arr[4] = 51，在子數組 arr[0] - arr[4] 中將其放置在正確的位置。

[7, 12, 34, 54, 90]

在這裡，我們將看到遞歸插入排序的工作原理。它以相反的方式運作，即與當前迭代相比，我們將遞歸呼叫recursiveInsertionSort()函數來對n-1個元素的陣列進行排序。然後在由函數傳回的已排序數組中，我們將第n個元素插入到其在已排序數組中的位置。

遞迴插入排序的程式如下：

範例

 示範

#include <stdio.h>
void recursiveInsertionSort(int arr[], int n){
   if (n <= 1)
      return;
   recursiveInsertionSort( arr, n-1 );
   int nth = arr[n-1];
   int j = n-2;
   while (j >= 0 && arr[j] > nth){
      arr[j+1] = arr[j];
      j--;
   }
   arr[j+1] = nth;
}
int main(){
   int array[] = {34, 7, 12, 90, 51};
   int n = sizeof(array)/sizeof(array[0]);
   printf("Unsorted Array:\t");
      for (int i=0; i < n; i++)
   printf("%d ",array[i]);
      recursiveInsertionSort(array, n);
   printf("</p><p>Sorted Array:\t");
   for (int i=0; i < n; i++)
      printf("%d ",array[i]);
   return 0;
}

輸出

Unsorted Array: 34 7 12 90 51
Sorted Array: 7 12 34 51 90

#

以上是遞歸插入排序的C程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！