我的快速排序算法所需的透视切换次数与我的分配中的透视切换次数不同的原因是什么？

Question

因此，显然在某些情况下，我的算法需要较少的透视更改来完成列表的排序。实际上，我的算法确实对列表进行了正确的排序，但数据透视表的数量小于或等于我所给出的示例。我的赋值中给出的一个例子是这个数组：

3 45 12 -3 4 -3 21 0 6 20

输出应该是这样的：

枢轴数： 7
第一个元素： -3
最后一个元素： 45

这是我得到的：

枢轴数： 5
第一个元素： -3
最后一个元素： 45

在另一个例子中，它适用于正确数量的枢轴：

9 2 4 7 3 7 10 11 12 13 13 10 13 13

我应该得到什么，也得到什么：

枢轴数量： 10
第一个元素： 2
最后一个元素： 13

我特别困惑的是，它在某些情况下有效，而在其他情况下则不起作用。

代码如下：

public static void quickSort(int[] arr, int start, int end, CountObject count){

    int partition = partition(arr, start, end, count);

    //partition will return the position the pivot. The pivot will be at the right place, hence if either side

    //of the pivot consists of only one element, it should not be sorted

    //check whether the part left from the pivot should still be sorted

   if(partition-1>start) {

        quickSort(arr, start, partition - 1, count);

    }

    //check whether the part right from the pivot should still be sorted

    if(partition+1<end) {

        quickSort(arr, partition + 1, end, count);

    }

}

public static int partition(int[] arr, int start, int end, CountObject count){

    int pivot = arr[start];

    count.increaseCount();

    //checks if left pointer < pivot

    for(int i=end; i>start; i--){

        if(arr[i]>pivot){

            int temp= arr[end];

            arr[end]=arr[i];

            arr[i]=temp;

            end--;

        }

    }

    int temp = arr[start];//=pivot

    arr[start] = arr[end];

    arr[end] = temp;

    return end;

}

}

我正在使用 CountObject 类进行计数。它包含一个方法增加计数和一个实例变量计数。

Answer 1

所以我终于想通了。我不得不使用另一种技术来遍历列表。在我的OP中，我使用第一个元素作为枢轴，并将其与列表末尾开始的所有元素进行比较。现在我从列表的第二个元素/当前子列表开始。这是解决我问题的代码，我希望这将使某人节省2天的工作，尽管我自己做这件事很有教育意义。import java.util.Scanner;public class Quickie {&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; Scanner sc = new Scanner(System.in);&nbsp; &nbsp; &nbsp; &nbsp; int temp;&nbsp; &nbsp; &nbsp; &nbsp; int size = sc.nextInt();&nbsp; &nbsp; &nbsp; &nbsp; int[] list = new int[size];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < size; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; temp = sc.nextInt();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; list[i] = temp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; int end = size - 1;&nbsp; &nbsp; &nbsp; &nbsp; CounterClass count = new CounterClass(0);&nbsp; &nbsp; &nbsp; &nbsp; quickSort(list, 0, end, count);&nbsp; &nbsp; &nbsp; &nbsp; int firstElement = list[0];&nbsp; &nbsp; &nbsp; &nbsp; int lastElement = list[size - 1];&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Number of pivots: " + count.getCount());&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("First Element: " + firstElement);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Last Element: " + lastElement);&nbsp; &nbsp; }&nbsp; &nbsp; private static void quickSort (int []arr, int start, int end, CounterClass count){&nbsp; &nbsp; &nbsp; &nbsp; int partition = partition(arr, start, end, count);&nbsp; &nbsp; &nbsp; &nbsp; if (partition-1>start){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; quickSort(arr, start, partition-1,count);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if (partition+1<end){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; quickSort(arr, partition+1,end,count);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; private static int partition (int[]arr, int start, int end, CounterClass count){&nbsp; &nbsp; &nbsp; &nbsp; int pivot = arr[start];&nbsp; &nbsp; &nbsp; &nbsp; count.count++;&nbsp; &nbsp; &nbsp; &nbsp; int pointer = start+1;&nbsp; &nbsp; &nbsp; &nbsp; int i =pointer;&nbsp; &nbsp; &nbsp; &nbsp; for (int j=pointer; j<=end;j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (arr[j]<pivot){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int temp = arr[j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[j]=arr[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[i]=temp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; i-=1;&nbsp; &nbsp; &nbsp; &nbsp; int temp=arr[start];&nbsp; &nbsp; &nbsp; &nbsp; arr[start]=arr[i];&nbsp; &nbsp; &nbsp; &nbsp; arr[i]=temp;&nbsp; &nbsp; &nbsp; &nbsp; return (i);&nbsp; &nbsp; }}class CounterClass{&nbsp; &nbsp; int count;&nbsp; &nbsp; public CounterClass(int count){&nbsp; &nbsp; &nbsp; &nbsp; this.count = count;&nbsp; &nbsp; }&nbsp; &nbsp; public int getCount() {&nbsp; &nbsp; &nbsp; &nbsp; return count;&nbsp; &nbsp; }}