实现快速排序的java函数

快速排序是一种常见的排序算法，其时间复杂度为O(nlogn)，实现起来比较简单，下面是一个java函数的实现。

public void quickSort(int[] arr, int left, int right){

    if (left >= right) { //边界条件

        return;

    }

    int i = left; //左指针

    int j = right; //右指针

    int tmp = arr[i]; //基准值

    while (i < j) {

        while (i < j && arr[j] >= tmp) { //从右往左找到第一个小于基准值的位置

            j--;

        }

        if (i < j) {

            arr[i] = arr[j]; //把该位置的元素赋值给左指针所在的位置

            i++;

        }

        while (i < j && arr[i] <= tmp) { //从左往右找到第一个大于基准值的位置

            i++;

        }

        if (i < j) {

            arr[j] = arr[i]; //把该位置的元素赋值给右指针所在的位置

            j--;

        }

    }

    arr[i] = tmp; //将基准值赋值到左右指针相遇的位置

    quickSort(arr, left, i - 1); //递归排序左边

    quickSort(arr, i + 1, right); //递归排序右边

}

该函数的参数包括要排序的数组以及要排序的区间，其中left和right分别是区间的左右边界。函数一开始会判断左右边界是否重合或者右边界小于左边界，如果是则直接返回。接着，函数会通过左右指针的移动，将数组分为两部分，左边的元素均小于等于基准值，右边的元素均大于等于基准值。最后，将基准值赋值到左右指针相遇的位置。

函数中采用递归方式分别对左、右两部分进行排序。递归结束的条件也很简单，即左右指针相遇或者左指针大于右指针。

在实际使用中，我们可以通过调用该函数来实现对数组的快速排序。比如，下面的示例代码会生成一个长度为10的随机数组，然后进行快速排序，并输出排序后的结果。

int[] arr = new int[10];

Random random = new Random();

for (int i = 0; i < 10; i++) {

    arr[i] = random.nextInt(100);

}

quickSort(arr, 0, arr.length-1);

for (int i = 0; i < arr.length; i++) {

    System.out.print(arr[i] + " ");

}

因为快速排序的时间复杂度为O(nlogn)，因此在大规模数据的排序时，快速排序是一个比较有效的算法。