在快速排序中计算比较和交换次数

Question

我正在从文件中读取的2000个整数上运行快速排序，但我得到的比较和交换次数似乎很高。我的计数器是放在正确的位置吗？还是排序出现了问题？

public int partition(int array[], int low, int high) 
    { 
        int pivot = array[high];  
        int i = (low-1); 
        for (int j = low; j < high; j++) 
        {
            compCounter++;
            if (array[j] <= pivot) 
            { 
                i++; 
                int temp = array[i]; 
                array[i] = array[j]; 
                array[j] = temp; 
                SwapCounter++;
            } 
        } 

        int temp = array[i+1]; 
        array[i+1] = array[high]; 
        array[high] = temp; 
        SwapCounter++;

        return i+1; 
    } 

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

- GeoffM

---

不。我认为这是真的。 - Amin

如果你的算法是O(n)，这并不意味着你会看到恰好n个比较、交换或其他任何操作。它意味着，如果你的集合大小增加了两倍，那么交换/比较的数量也将增加两倍。 - Ivan

你的计数器有多高？我预计会有0到4000000个整数，但大多数在约10000到20000个之间，用于compCounter。 - leonardkraemer

Answer 1

你的计数器是正确的。

只是一个快速的建议 - 将交换代码移动到单独的函数 swap(array, fromIndex, toIndex) 中。

- Deian