快速排序.如何选择枢轴元素? [英] Quicksort. How to choose pivot element?

问题描述

我阅读了有关quicksort算法的信息，但我不了解如何选择数据透视元素.从教程中，我得到quciksort的示例代码:

I read about quicksort algorithm and I don't understand how to choose pivot element. From tutorials I get example code of quciksort:

public void quicksort(int[] A, int left, int right) {
    int pivot = A[left + (right - left) / 2];
    int i = left;
    int j = right;
    while (i <= j) {
        while (A[i] < pivot) {
            i++;
        }
        while (A[j] > pivot) {
            j--;
        }
        if (i <= j) {
            exchange(i, j);
            i++;
            j--;
        }
    }

    if(left < j)
        quicksort(A,left,j);
    if(i < right)
        quicksort(A,i,right);
}

但是为什么我们选择使用此A[left + (right - left) / 2];的支点呢?

But why we choose pivot using this A[left + (right - left) / 2];?

为什么不A[(right - left) / 2]

推荐答案

考虑left=6, right=10，然后(right-left)/2为2.您选择的元素不在子数组的范围内吗?

Consider left=6, right=10, then (right-left)/2 is 2. You are choosing an element which is not in the range of your sub-array?

您可以选择6到10之间的任意元素以进行快速排序.但是，如果选择第一个或最后一个元素并且对数组进行了排序，则算法的运行时间可能为O(n ^ 2).因此，最好选择中间元素.

You can choose any element between 6 and 10 as for quick sort.But if you choose first or last element and if the array is sorted, then your algorithm may go to O(n^2) running time. So it is always better to choose middle element.

这篇关于快速排序.如何选择枢轴元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！