排序递归法 java
时间: 2023-03-02 19:43:16 浏览: 62
排序算法中最常见的递归算法是快速排序(Quick Sort)和归并排序(Merge Sort),下面分别给出它们的Java实现。
快速排序(Quick Sort):
```java
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
```
归并排序(Merge Sort):
```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);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}
```
以上代码中,快速排序使用了分治思想,首先将数组划分成两个部分,一部分小于基准值,一部分大于基准值,然后递归地对两部分进行排序;归并排序也使用了分治思想,首先将数组划分成两个部分,然后递归地对两部分进行排序,最后将两部分合并起来。