Java函数实现快速排序算法详解及应用实例

快速排序是一种常用的排序算法，最早是由C. A. R. Hoare（英国计算机科学家）于1960年提出的。

快速排序算法的思想是通过分治的思想将一个数组划分为两个子数组，使得一个数组中所有元素都小于另一个数组中的所有元素，然后递归地排序两个子数组。

具体实现方法如下：

1. 选择一个基准值（pivot），一般选择数组的 个元素。

2. 将数组分为两部分，左边的部分为小于等于基准值的元素，右边的部分为大于基准值的元素。

3. 递归地对左右两部分进行快速排序。

4. 合并左右两部分得到排好序的数组。

Java代码实现快速排序算法如下：

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        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[left];
        int i = left;
        int j = right;

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

        swap(arr, left, i);

        return i;
    }

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

调用快速排序算法：

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

应用实例

使用快速排序算法对一个包含10000个元素的数组进行排序，计算排序所需时间。Java代码如下：

import java.util.Arrays;

public class QuickSortTest {

    public static void main(String[] args) {
        int[] arr = new int[10000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 10000);
        }

        long startTime = System.currentTimeMillis();
        QuickSort.quickSort(arr, 0, arr.length - 1);
        long endTime = System.currentTimeMillis();

        System.out.println(Arrays.toString(arr));
        System.out.println("快速排序所需时间：" + (endTime - startTime) + "ms");
    }
}

运行结果：

快速排序所需时间：15ms

快速排序算法时间复杂度为O(nlogn)。因此，快速排序在处理大规模数据时表现良好。