我在使用 Median 和 Mean 作为 Quicksort 中的 pivot 时遇到了问题

Question

对于一个 class 项目，我应该用不同的基准（低、高、中点、随机、中值和平均值）测试快速排序，但我无法让它与它们一起工作.到目前为止，我已经使用了两种不同的 Quicksort 方法，并且我已经能够对随机数组进行排序，所有内容都是随机的，但不是均值或中位数。 “分区”适用于低、中点和随机，而“分区 1”适用于高。

非常感谢任何帮助，如果还有任何需要补充的，请告诉我。

这是我目前使用的代码。 “Partition1”来自GFG，“Partition”来自我的教科书。

`

import java.util.Arrays;

import java.util.Random;

public class QSort {
public static int comparisonCount;
public static int swapCount;
public static void main(String[] args){

    Random r = new Random();
    int N= 10;

    int[] test = new int[N]; //random integer array
    for (int i =0; i < test.length; i++){
        test[i] = r.nextInt(N*2);
    }

    System.out.println(Arrays.toString(test));
    long startTime = System.nanoTime();
    Quicksort(test, 0, test.length-1);
    long endTime = System.nanoTime();
    long duration = (endTime - startTime);

    System.out.println(Arrays.toString(test));
    System.out.println("Number of Comparisons "+ comparisonCount);
    System.out.println("Number of swaps "+ swapCount);//1000000
    System.out.println("QuickSort Duration in millisecond is "+(duration/1000000));
    System.out.println("length is "+(test.length-1));


}


    public static double median(int[] arr){
    double median;
    if (arr.length % 2 == 0) {
        median = ((double) arr[arr.length / 2] + (double) arr[arr.length / 2 - 1]) / 2;
    }
    else {
        median = (double) arr[arr.length / 2];
    }
    return median;
}

static void swap(int[] arr, int i, int j)
{
    swapCount++;
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public static int Partition1(int[] arr, int low, int high)
{

    int pivot =arr[high];

    int i = (low - 1);

    for(int j = low; j <= high - 1; j++)
    {

        if(largerThan(arr[j],pivot))
        {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i+1, high);
    return (i+1);
}

public static int mean(int[] arr){
    double total = 0;
    for(int i=0; i<arr.length; i++){
        total = total + arr[i];
    }
    double average = total / arr.length;
    return (int)average;
}

public static int Partition(int[] numbers, int low, int high) {
    int midpoint = low + (high - low)/2; // Calculate Midpoint
    //Random rand= new Random(); // for random pivot
    //int pivot = numbers[rand.nextInt(high-low)+low];
    int pivot = numbers[high];

    boolean done = false;
    while (!done) {
        while (largerThan(numbers[low], pivot)) {
            low+=1;
        }

        while (largerThan(pivot, numbers[high])) {
            high-=1;
        }

        if (low >= high) {
            done = true;
        }
        else {
            swap(numbers, low, high);

            low+=1;
            high-=1;
        }
    }

    return high;
}

public static boolean largerThan( int i, int m){
    comparisonCount++;
    return i < m;
}



public static void Quicksort(int[] numbers, int low, int high) {
    if (high <= low || low >= high) {
        return;
    }

        var Index = Partition1(numbers, low, high);

        Quicksort(numbers, low, Index-1); //Index-1 for Partion1 and just Index for Partition
        Quicksort(numbers, Index + 1, high);
    }

} `

Answer 1

Lomuto 分区的示例 C 代码。它将中间元素交换到最后，但可以删除。递归较小，循环较大限制堆栈 space 复杂度为 O(log2(n))，但最坏情况时间复杂度仍然为 O(n^2)。您也不需要 uint64_t（只需使用 int 代替）。

void QuickSort(uint64_t a[], int lo, int hi)
{
    while (lo < hi){
        uint64_t t;
        uint64_t p = a[(lo+hi)/2];      /* use mid point for pivot */
        a[(lo+hi)/2]= a[hi];            /* swap with a[hi] */
        a[hi] = p;
        int i = lo;
        for (int j = lo; j < hi; ++j){  /* Lomuto partition */
            if (a[j] < p){
                t = a[i];
                a[i] = a[j];
                a[j] = t;
                ++i;
            }
        }
        t = a[i];
        a[i] = a[hi];
        a[hi] = t;
        if(i - lo <= hi - i){           /* recurse on smaller partiton, loop on larger */
            QuickSort(a, lo, i-1);
            lo = i+1;
        } else {
            QuickSort(a, i+1, hi);
            hi = i-1;
        }
    }
}

我在使用 Median 和 Mean 作为 Quicksort 中的 pivot 时遇到了问题

I am having trouble with using Median and Mean as pivot in Quicksort

java

quicksort