java快速排序及时间

快速排序是一种常用的高效排序算法，它采用了分治法的思想。基本步骤如下：

1. **选择基准**：通常选择第一个元素作为基准值。
2. **分割区间**：将数组分为两部分，一部分的所有元素都小于基准，另一部分所有元素大于等于基准。
3. **递归排序**：对两部分分别进行快速排序，直到每个部分只剩一个元素，排序完成。

**核心代码片段** (伪代码)：

void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int partition(int[] arr, int low, int high) {
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        arr[low++] = arr[high];

        while (low < high && arr[low] <= pivot) low++;
        arr[high--] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

**时间复杂度**：
- 最佳情况（每次都能平均分割）：O(n log n)
- 平均情况：O(n log n)
- 最坏情况（数组已经有序或逆序）：O(n^2)，但通过随机化选取基准可以降低概率

**相关问题--:**
1. 除了递归，还有哪些方法可以实现快速排序？
2. 快速排序的空间复杂度是多少？
3. 当数据量非常大时，快速排序还适用吗？为什么？