快速排序java递归

好的，以下是快速排序的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);
    }
}

private 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;
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

相关问题

java快速排序非递归版本

快速排序是一种常用的排序算法，它通过选择一个基准元素，将数组分成两部分，一部分小于基准元素，一部分大于基准元素，然后对这两部分分别进行快速排序。非递归版本的快速排序使用栈来模拟递归过程，避免了递归带来的函数调用开销。

以下是Java实现的非递归版本快速排序的代码：

import java.util.Stack;

public class QuickSortNonRecursive {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(arr.length - 1);
        
        while (!stack.isEmpty()) {
            int end = stack.pop();            int start = stack.pop();
            
            int pivotIndex = partition(arr, start, end);
            
            if (pivotIndex - 1 > start) {
                stack.push(start);
                stack.push(pivotIndex - 1);
            }
            
            if (pivotIndex + 1 < end) {
                stack.push(pivotIndex + 1);
                stack.push(end);
            }
        }
    }
    
    private static int partition(int[] arr, int start, int end) {
        int pivot = arr[end];
        int i = start - 1;
        
        for (int j = start; j < end; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        
        swap(arr, i + 1, end);
        return i + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

使用示例：

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 9, 1, 3};
        
        QuickSortNonRecursive.quickSort(arr);
        
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

输出结果为：1 2 3 5 8 9

快速排序递归算法java

快排序是一种使用递归原理的排序算法，其平均性能在所有O(n log n)数量级的排序方法中最好。它将待排序的数组分成两部分，一部分是小于锚点的元素，另一部分是大于等于锚点的元素，然后递归地对这两部分进行快速排序。下面是一个使用递归实现的快速排序的Java代码：

private void quickSort(int[] arr, int startPos, int endPos){
    if(startPos >= endPos){
        return;
    }
    int leftIndex = startPos;
    int rightIndex = endPos;
    int mid = arr[leftIndex];
    
    while (leftIndex < rightIndex){
        while (leftIndex < rightIndex && arr[rightIndex] >= mid){
            rightIndex--;
        }
        arr[leftIndex] = arr[rightIndex];
        
        while (leftIndex < rightIndex && arr[leftIndex] < mid){
            leftIndex++;
        }
        arr[rightIndex] = arr[leftIndex];
    }
    
    arr[leftIndex] = mid;
    quickSort(arr, startPos, leftIndex-1);
    quickSort(arr, leftIndex+1, endPos);
}