设计出(冒泡排序、快速排序和归并排序)的递归和非递归排序算法;对数组中的数据进行排序(按从小到大的顺序排序);
时间: 2024-09-30 07:05:27 浏览: 10
下面是三种常见排序算法(冒泡排序、快速排序和归并排序)的非递归和递归版本的描述。
1. **冒泡排序**(非递归版):
- 非递归:通过嵌套循环,比较相邻元素并交换,直到整个序列排序完成。
```java
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
```
- 递归版:将大数组分解成小数组,然后逐层处理。
```java
public static void recursiveBubbleSort(int[] arr, int left, int right) {
if (left >= right) return;
for (int i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) swap(arr, i, i + 1);
}
recursiveBubbleSort(arr, left + 1, right);
}
```
2. **快速排序**(非递归版):
- 非递归:使用两个指针,一个指向开始,另一个指向结束,不断交换元素并调整分区边界,直到完全排序。
```java
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
```
- 递归版:直接应用分治策略,将问题分解为较小的子问题。
```java
public static void recursiveQuickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
recursiveQuickSort(arr, low, pivotIndex - 1);
recursiveQuickSort(arr, pivotIndex + 1, high);
}
}
```
3. **归并排序**(非递归版):
- 非递归:采用“分而治之”的策略,先将数组分为两半,然后分别排序,最后合并两个已排序的部分。
```java
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
```
- 递归版:同上,只是名称不同。
```java
public static void recursiveMergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
recursiveMergeSort(arr, left, mid);
recursiveMergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
```
在以上每个方法中,`swap()`和`partition()`分别是交换元素和分区操作的辅助函数。