Java实现快排算法

代码工匠 2019-02-14 ⋅ 13 阅读

快速排序是一种常用的排序算法,其基本思想是采用分治法,将待排序的数组元素分成两个子数组,然后对子数组进行递归排序,最终得到有序数组。以下是使用Java实现快速排序的代码示例:

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 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;
    }
}

在上面的代码中,我们定义了一个quickSort方法,该方法接受一个待排序的数组、左边界和右边界作为参数,并使用递归的方式对子数组进行排序。在quickSort方法中,我们首先判断左边界是否小于右边界,如果是,则选择一个基准元素(这里选择最右边的元素),然后将数组分成两部分,一部分比基准元素小,另一部分比基准元素大。接着,我们递归地对左右两部分进行排序。在partition方法中,我们将基准元素放在正确的位置上,并返回基准元素的索引。最后,我们定义了一个swap方法,用于交换数组中的两个元素。

使用以上代码,我们可以轻松地对一个整数数组进行快速排序。例如:

int[] arr = {3, 6, 8, 10, 2, 1, 0};
QuickSort.quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // [0, 1, 2, 3, 6, 8, 10]

全部评论: 0

    我有话说: