java - 我的快速排序算法需要的主元开关数量与我的作业中的不同的原因可能是什么？

Question

所以，显然在某些情况下，我的算法需要较少的主元变化来完成列表的排序。我的算法实际上确实对列表进行了正确排序，但枢轴数小于或等于我给出的示例。我的作业中给出的一个例子是这个数组:

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

输出应该是这样的:

Number of pivots: 7
First Element: -3
Last Element: 45

这是我得到的:

Number of pivots: 5
First Element: -3
Last Element: 45

在另一个例子中，它使用适量的枢轴:

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

我应该得到的和我得到的:

Number of pivots: 10
First Element: 2
Last Element: 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 类进行计数。它包含一个方法 increaseCount 和一个实例变量 count。

Answer 1

所以我终于想通了。我不得不使用另一种技术来遍历列表。在我的 OP 中，我使用第一个元素作为基准并将其与列表末尾开始的所有元素进行比较。现在我从列表的第二个元素/当前子列表开始。

这是解决我的问题的代码，我希望这会节省某人 2 天的工作时间，尽管这对我自己来说很有教育意义。

import java.util.Scanner;

public class Quickie {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int temp;

        int size = sc.nextInt();

        int[] list = new int[size];
        for (int i = 0; i < size; i++) {
            temp = sc.nextInt();
            list[i] = temp;
        }
        int end = size - 1;
        CounterClass count = new CounterClass(0);

        quickSort(list, 0, end, count);

        int firstElement = list[0];
        int lastElement = list[size - 1];
        System.out.println("Number of pivots: " + count.getCount());
        System.out.println("First Element: " + firstElement);
        System.out.println("Last Element: " + lastElement);
    }
    private static void quickSort (int []arr, int start, int end, CounterClass count){
        int partition = partition(arr, start, end, count);

        if (partition-1>start){
            quickSort(arr, start, partition-1,count);
        }
        if (partition+1<end){
            quickSort(arr, partition+1,end,count);
        }
    }
    private static int partition (int[]arr, int start, int end, CounterClass count){
        int pivot = arr[start];

        count.count++;
        int pointer = start+1;
        int i =pointer;
        for (int j=pointer; j<=end;j++){
            if (arr[j]<pivot){
                int temp = arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
                i++;
            }
        }
        i-=1;

        int temp=arr[start];
        arr[start]=arr[i];
        arr[i]=temp;
        return (i);
    }



}


class CounterClass{
    int count;
    public CounterClass(int count){
        this.count = count;
    }

    public int getCount() {
        return count;
    }
}