使用Java实现的快速排序函数

快速排序是经典的递归算法，用来将一个无序序列按照一定的顺序进行排序。快速排序的基本思想是将整个序列分成两部分，分别进行排序，其中一部分的所有元素都小于另一部分的所有元素，因而可以选择一个元素作为枢轴(pivot)，通过一次排序，把两部分分别排好序。

实现代码

下面是使用Java实现的快速排序函数代码。

public class QuickSort {
    public void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0 || low >= high) {
            return;
        }

        int i = low, j = high;
        int pivot = arr[low + (high - low) / 2];

        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }

        if (low < j) {
            quickSort(arr, low, j);
        }
        if (high > i) {
            quickSort(arr, i, high);
        }
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] arr = { 3, 7, 6, 1, 8, 5, 9, 2, 4 };
        quickSort.quickSort(arr, 0, arr.length - 1);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

在这个代码中，quickSort()函数接收一个数组和数组的下标范围，其中low表示排序的起始位置，high表示排序的终止位置。如果传入的数组为null，或者数组没有元素，或者low大于等于high，则返回。

接下来，函数定义了两个变量，i和j，并以数组中间位置的元素为枢轴(pivot)。在while循环中，通过比较数组元素与枢轴大小来进行交换。当i小于等于j时，交换ai 和aj坐标上的元素，并将i和j分别加1和减1。

随后，递归调用quickSort()函数对数组的左半边进行排序。如果low小于j，则在区间[low, j]上调用quickSort()函数，将左半边进行排序。同样，如果i小于high，则在区间[i, high]上调用quickSort()函数，将右半边进行排序。

快速排序的时间复杂度为O(nlogn)，是同样时间复杂度的排序算法中 的，但它不是一个稳定的排序算法，即相同的元素排序后其顺序还是原来的顺序。这个算法可能会对大量重复元素的数组进行一定程度的过度分割，使得一部分数多次被交换，导致效率降低，并且快速排序最差情况的时间复杂度是O(n2)。