Java编程实现快速排序及优化代码详解

什么是快速排序

快速排序是一种高效的排序算法，其基本思路是将待排序序列分成两个子序列，其中一个子序列中的所有元素都比另一个子序列中的元素小，然后分别对这两个子序列递归排序。具体实现过程中需要选取一个基准元素，将待排序序列中的其他元素与基准元素进行比较，将小于等于基准的元素放入左半部分，大于基准的元素放入右半部分。如此递归排序，最终实现整个序列有序。在实践中，快速排序被证明具有较高的效率和可靠性。

快速排序的实现

下面是Java实现的快速排序代码。

public class QuickSort {

    /**
     * 使用快速排序算法对数组进行排序
     * @param arr 待排序数组
     */
    public static void quickSort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 对数组中指定的子序列进行排序
     * @param arr 待排序数组
     * @param left 子序列左端点
     * @param right 子序列右端点
     */
    public static void sort(int[] arr, int left, int right) {
        if (left < right) {
            int i = left, j = right, pivot = arr[left];
            while (i < j) {
                //从右向左遍历，查找小于等于基准数的位置
                while (i < j && arr[j] > pivot) {
                    j--;
                }
                if (i < j) {
                    arr[i++] = arr[j];
                }
                //从左向右遍历，查找大于基准数的位置
                while (i < j && arr[i] < pivot) {
                    i++;
                }
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }
            arr[i] = pivot;
            sort(arr, left, i - 1);
            sort(arr, i + 1, right);
        }
    }
}

快速排序的优化

进一步优化可将数组中的基准元素选取更为准确的位置，如选择三数取中法，取三个数中的中间值作为基准元素，从而尽可能避免最坏情况的出现（即子序列分割的非常不平衡），使得算法在一般情况下有更高的效率。

public static void sort(int[] arr, int left, int right) {
    if (left < right) {
        int i = left, j = right, pivot = medianOfThree(arr, left, right);
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot;
        sort(arr, left, i - 1);
        sort(arr, i + 1, right);
    }
}
/**
 * 选取子序列中前中后三个数中的中间值作为基准元素
 * @param arr 待排序数组
 * @param left 子序列左端点
 * @param right 子序列右端点
 * @return 基准元素
 */
public static int medianOfThree(int[] arr, int left, int right) {
    int mid = (left + right) / 2;
    if (arr[left] > arr[mid]) {
        swap(arr, left, mid);
    }
    if (arr[left] > arr[right]) {
        swap(arr, left, right);
    }
    if (arr[mid] > arr[right]) {
        swap(arr, mid, right);
    }
    swap(arr, mid, right - 1);
    return arr[right - 1];
}
/**
 * 交换数组中指定位置的元素
 * @param arr 数组
 * @param i 索引1
 * @param j 索引2
 */
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

示例说明

示例1：对整型数组进行排序

int[] arr = {3, 2, 1, 5, 4};
QuickSort.quickSort(arr);
System.out.println(Arrays.toString(arr));

运行结果：[1, 2, 3, 4, 5]

示例2：对字符串数组进行排序

String[] arr = {"abc", "ab", "a", "abcd", "abcde"};
 Arrays.sort(arr);
 System.out.println(Arrays.toString(arr));

运行结果：[a, ab, abc, abcd, abcde]

总结

通过上述示例，我们可以看到Java实现快速排序的过程，其基本思路是将待排序序列分成两个子序列，其中一个子序列中的所有元素都比另一个子序列中的元素小，然后对这两个子序列递归排序。为了提高效率并避免最坏情况出现，还可以采用选取基准元素的优化方案，如三数取中等方法。