java快速排序算法代码

当我们谈论快速排序算法时，通常是指使用递归和分治思想的快速排序。

java
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        
        System.out.println("Original array: " + Arrays.toString(array));
        
        quickSort(array, 0, array.length - 1);
        
        System.out.println("Sorted array: " + Arrays.toString(array));
    }

    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(array, low, high);
            
            quickSort(array, low, partitionIndex - 1);
            quickSort(array, partitionIndex + 1, high);
        }
    }

    public static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                swap(array, i, j);
            }
        }
        
        swap(array, i + 1, high);
        return i + 1;
    }

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

这个例子中，quickSort 方法是递归调用的入口点，而 partition 方法用于找到基准元素的正确位置，并将数组划分为两个子数组。 swap 方法用于交换数组中的两个元素。

这是

java
import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        
        System.out.println("Original array: " + Arrays.toString(array));
        
        quickSort(array, 0, array.length - 1);
        
        System.out.println("Sorted array: " + Arrays.toString(array));
    }

    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(array, low, high);
            
            quickSort(array, low, partitionIndex - 1);
            quickSort(array, partitionIndex + 1, high);
        }
    }

    public static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                swap(array, i, j);
            }
        }
        
        swap(array, i + 1, high);
        return i + 1;
    }

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

这个代码演示了快速排序算法的基本原理。在 main 方法中，我们创建一个整数数组，然后调用 quickSort 方法进行排序，最后输出排序后的数组。

快速排序的基本思想是选择一个基准元素，然后将数组划分为两个部分，小于基准的放在左边，大于基准的放在右边。接着对这两部分分别进行递归排序。这个过程是原地排序的，因为它不需要额外的空间来存储临时数组。

这里的实现是一种基本的快速排序，可能在某些情况下会有性能问题。在实际应用中，可能需要对算法进行一些优化，比如使用随机化选择基准元素来避免最坏情况的发生。