用递归方法实现简单选择排序和冒泡排序
时间: 2024-05-02 17:12:48 浏览: 19
简单选择排序的递归实现:
```python
def selection_sort_recursive(arr, n):
if n <= 1: # 递归出口
return
max_index = 0
for i in range(1, n):
if arr[i] > arr[max_index]:
max_index = i
arr[n-1], arr[max_index] = arr[max_index], arr[n-1] # 将最大值交换到最后
selection_sort_recursive(arr, n-1) # 递归排序剩余部分
```
冒泡排序的递归实现:
```python
def bubble_sort_recursive(arr, n):
if n <= 1: # 递归出口
return
for i in range(n-1):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i] # 将相邻的元素交换
bubble_sort_recursive(arr, n-1) # 递归排序剩余部分
```
需要注意的是,递归实现的简单选择排序和冒泡排序在实际使用中并不常见,因为它们的时间复杂度较高,不如非递归实现的版本效率高。
相关问题
C语言,用递归方法实现简单选择排序和冒泡排序
简单选择排序的递归实现:
```
void selectionSortRecursive(int arr[], int n, int index) {
// Base case
if (index == n-1)
return;
// Find the minimum element in unsorted array
int minIndex = index;
for (int i = index+1; i < n; i++)
if (arr[i] < arr[minIndex])
minIndex = i;
// Swap the found minimum element with the first element
int temp = arr[index];
arr[index] = arr[minIndex];
arr[minIndex] = temp;
// Recursive call for remaining unsorted array
selectionSortRecursive(arr, n, index+1);
}
```
冒泡排序的递归实现:
```
void bubbleSortRecursive(int arr[], int n) {
// Base case
if (n == 1)
return;
// One pass of bubble sort. After this pass, the largest element is moved (or bubbled) to end.
for (int i = 0; i < n-1; i++)
if (arr[i] > arr[i+1]) {
// Swap arr[i], arr[i+1]
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
// Recursive call for remaining array
bubbleSortRecursive(arr, n-1);
}
```
c++利用递归思想,选择简单排序或冒泡排序,实现一组数据的递增排序
好的,以下是使用递归实现简单排序和冒泡排序的示例代码:
1. 简单排序
```c++
void simpleSort(int* arr, int size) {
if (size == 1) {
return;
}
for (int i = 0; i < size - 1; ++i) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
simpleSort(arr, size - 1);
}
```
2. 冒泡排序
```c++
void bubbleSort(int* arr, int size) {
if (size == 1) {
return;
}
for (int i = 0; i < size - 1; ++i) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
bubbleSort(arr, size - 1);
}
```
上述两个函数都接受一个整数数组和数组大小作为参数,使用递归的思想实现了简单排序和冒泡排序。简单排序每次都将最小的数移到数组的最前面,冒泡排序每次都将最大的数移到数组的最后面。这两种排序算法时间复杂度都是 $O(n^2)$,不过对于小规模的数据还是很实用的。