資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++遞迴選擇排序
選擇排序是一種排序演算法，透過從陣列開頭迭代並用列表中最小的元素替換每個元素來對資料進行排序。隨著我們的前進，左側陣列被排序，而右側陣列未排序。每次移動都會透過交換將下一個最小的元素放置到索引的當前位置。
選擇排序演算法
int arr[5]= { 5,4,2,1,3 };
int i, j ;
從索引 i=0 遍歷到 i<陣列大小 -1
從索引 j=i+1 遍歷到陣列大小 - 1
找到最小值並存儲其索引 pos
將找到的索引 pos 處的元素與 arr[i] 交換
結束
遞迴選擇排序
找到最小元素的索引
如果找到的最小元素索引等於陣列大小，則返回。
否則，將當前元素與最小元素交換
對其餘陣列（不包括已排序的元素）遞迴執行上述步驟
示例
輸入 − Arr[] = { 5,7,2,3,1,4 }; length=6
輸出 − 已排序陣列：1 2 3 4 5 7
解釋−
First Pass :- 5 7 2 3 1 4 → swap → 1 2 7 3 5 4 1 2 7 3 5 4 → no swap 1 2 7 3 5 4 → swap → 1 2 3 7 5 4 1 2 3 7 5 4 → swap → 1 2 3 4 5 7 1 2 3 4 5 7 → no swap
輸入 − Arr[] = { 1, 2, 3, 3, 2 };
輸出 − 已排序陣列：1 2 2 3 3
解釋 −
1 2 3 3 2 → no swap 1 2 3 2 3 → no swap 1 2 3 2 3 → swap → 1 2 2 3 3 1 2 2 3 3 → no swap
下面程式中使用的演算法如下
在選擇排序的遞迴方法中，基本情況是最小索引 = 陣列大小-1。否則，從陣列中找到最小值，與當前索引交換，並遞迴排序右側未排序的陣列。
獲取輸入陣列 Arr[] 和長度作為其中的元素個數。
函式 findMin(int arr[], int i, int j) 獲取陣列及其索引，並返回 arr[i+1] 到 arr[j] 之間最小元素的索引。
獲取一個變數 minpos。
如果 i 和 j 都相同，則返回 i 作為最小元素的索引，因為兩者相同。
否則，使用 minpos = findMin(arr, i + 1, j) 遞迴查詢位置 i+1 到 j。
如果 (arr[i]<arr[minpos])，則設定 { minpos=i; } 並返回 minpos。
函式 recurselectSort(int arr1[], int len1, int pos1) 獲取輸入陣列，並使用選擇排序中的遞迴按升序對其進行排序。
如果 pos1 == len1，則表示未找到最小值，則返回。
否則設定 minpos1 = findMin(arr1, pos1, len1-1)
如果當前 pos1 索引和最小元素索引 minpos1 不相同，則使用 temp 交換這些索引中的元素。
使用 recurselectSort(arr1, len1, pos1 + 1) 對其餘陣列進行遞迴。
在所有呼叫結束時，當 len 變成 1 時，我們將退出遞迴，並且陣列將被排序。
在 main 函式內列印已排序的陣列。
示例
#include <iostream>
using namespace std;
int findMin(int arr[], int i, int j){
int minpos;
if (i == j){
return i;
}
minpos = findMin(arr, i + 1, j);
if(arr[i]<arr[minpos]){
minpos=i;
}
return (minpos);
}
void recurselectSort(int arr1[], int len1, int pos1){
int temp;
int minpos1;
if (pos1 == len1){
return;
}
minpos1 = findMin(arr1, pos1, len1-1);
if (minpos1 != pos1){
temp=arr1[pos1];
arr1[pos1]=arr1[minpos1];
arr1[minpos1]=temp;
}
recurselectSort(arr1, len1, pos1 + 1);
}
int main(){
int Arr[] = {1,5,3,0,9,3,5};
int length = sizeof(Arr)/sizeof(Arr[0]);
recurselectSort(Arr,length,0);
cout<<"Sorted Array using recursive Selection sort: "<<endl;
for (int i = 0; i<length ; i++){
cout << Arr[i] << " ";
}
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出
Sorted Array using recursive Selection sort: 0 1 3 3 5 5 9
7K+ 次瀏覽
