資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究遞迴插入排序的 C 程式
插入排序是一種排序演算法，它是一種基於比較的原地演算法。
該演算法透過將元素放在已排序子陣列中的位置來工作，即元素之前、已排序的子陣列。
演算法
第 1 步−迴圈 1 到 n-1，並執行以下操作−
第 2.1 步−選擇位置 i 處元素 array[i]。
第 2.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("
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
更新於: 2020 年 7 月 17 日
3K+ 瀏覽
廣告