QSort 随机分区

Question

以下 qsort 的实现来自 "Foundations of Algorithms" 一书，因此被认为是正确的。下面是我在 Java 中的实现。这没用。问题是当分区被随机选择时，生成的分区是不正确的。我希望有人能告诉我我做错了什么：

鲍勃

import java.util.*;
public class qsort {
    public static void main(String []args)
    {
        int []a1 = { 1, 2, 3, -4, -5, 6, 7 };
        sort( 0, a1.length-1, a1 );
        printarray (a1 );

    }
static void sort( int low, int high, int []a )
{
    if ( low < high ) {
        int p = part( low, high, a);
        System.out.println( " p = " + p );
        printarray( a, low, p );
        System.out.println();
        sort( low, p-1, a);
        printarray( a, p, high );
        System.out.println();
        sort( p+1, high, a);
    }
}
static int part(int low, int high, int [] S) {
        int i;
        int j;
        int randspot;
        int pivotitem;
        int pivotpoint;
        Random random = new Random(456);
        randspot = random.nextInt(high-low +1)+low;
        pivotitem = S[randspot];
        j = low;
        for (i = low + 1; i <= high; i++)
            if (S[i] < pivotitem){
                j++;
                int temp = S[j];
                S[j] = S[i]; //exchanges S[i] and S[j]
                S[i] = temp;
            }
        pivotpoint = j;
        int temp = S[low];
        S[low] = S[pivotpoint];
        S[pivotpoint] = temp;
        return pivotpoint;
    }

static void printarray (int [] Test){
    for (int i = 0; i<Test.length; i++){
        if (i !=0 && i%10==0)
            System.out.println();
        System.out.print(Test[i]+ "\t");

    }
}
static void printarray (int [] Test, int low, int high){
    for (int i = low; i<high; i++)
        System.out.print(Test[i]+ "\t");
    }
}

Answer 1

您需要先将基准元素与低索引元素交换，然后再进行其他操作。检查我在以下代码块中添加的代码。

static int part(int low, int high, int [] S) {
    int i;
    int j;
    int randspot;
    int pivotitem;
    int pivotpoint;
    Random random = new Random(456);
    randspot = random.nextInt(high-low +1)+low;
    System.out.println( " p = " + randspot );
    System.out.println( " value = " + S[randspot] );
    pivotitem = S[randspot];
    //---------------Start code block
    int temp1 = S[randspot];
    S[randspot] = S[low];
    S[low] = temp1;
    //---------------End code block
    j = low;
    for (i = low + 1; i <= high; i++)
        if (S[i] < pivotitem){
            j++;
            int temp = S[j];
            S[j] = S[i]; //exchanges S[i] and S[j]
            S[i] = temp;
        }
    pivotpoint = j;
    int temp = S[low];
    S[low] = S[pivotpoint];
    S[pivotpoint] = temp;
    return pivotpoint;
}

QSort 随机分区

QSort with Random Partition

java

algorithm

sorting

qsort