Quicksort 数组没有正确打印出来？ (java)

Question

我目前正在完成一项涉及实施排序算法的大学作业。我相信我已经正确地实现了快速排序算法，但是在测试 class 中，该方法只是打印出正在读取的数组而不对其进行排序。下面是测试 class 的代码，以及实际快速排序的代码（在一个名为 'sort' 的单独 class 中）。有没有人知道我做错了什么？

import java.io.*;
import java.text.*;
import java.util.*;

public class Sort {

/** Array of integers to sort **/
private int[] A;

/** Size of the array **/
private int size;

/** Number of elements actually used in array **/
private int usedSize;

/** Global variables for counting sort comparisons **/
public int compIS;
/** Global comparison count for Insertion Sort **/
public int compQS;
/** Global comparison count for Quicksort **/
public int compNewS;

/** Global comparison count for new sort **/

/*****************/
/** Constructor **/
/*****************/
Sort(int max) {
    /** Initialiase global sort count variables **/
    compIS = 0;
    compQS = 0;
    compNewS = 0;

    /** Initialise size variables **/
    usedSize = 0;
    size = max;

    /** Create Array of Integers **/
    A = new int[size];
}

public int getRightElement() {
    return usedSize - 1;
}

public int getLeftElement() {
    return A[0];
}

/*********************************************/
/*** Read a file of integers into an array ***/
/*********************************************/
public void readIn(String file) {
    try {
        /** Initialise loop variable **/
        usedSize = 0;

        /** Set up file for reading **/
        FileReader reader = new FileReader(file);
        Scanner in = new Scanner(reader);

        /** Loop round reading in data while array not full **/
        while (in.hasNextInt() && (usedSize < size)) {
            A[usedSize] = in.nextInt();
            usedSize++;
        }

    } catch (IOException e) {
        System.out.println("Error processing file " + file);
    }
}

/**********************/
/*** Display array ***/
/**********************/
public void display(int line, String header) {
    /*** Integer Formatter - three digits ***/
    NumberFormat FI = NumberFormat.getInstance();
    FI.setMinimumIntegerDigits(3);

    /** Print header string **/
    System.out.print("\n" + header);

    /** Display array data **/
    for (int i = 0; i < usedSize; i++) {
        /** Check if new line is needed **/
        if (i % line == 0) {
            System.out.println();
        }

        /**
         * Display an ar ray element
         **/
        System.out.print(FI.format(A[i]) + " ");
    }
}
public void quick(int L, int R) {
    /* ensure there is more than one element in array */
    if (R > L) {
        /* split array in two */
        int pLoc = partition(L, R);
        /* sort left half */
        quick(L, pLoc - 1);
        /* sort right half */
        quick(pLoc + 1, R);
    }

    System.out.println("\n\nAfter  QuickSort: ");
    for (int i = 0; i < usedSize; i++) {
        System.out.println(A[i] + " ");
    }
}

/* partitions array for quicksort */
public int partition(int L, int R) {
    /* Select pivot */
    int pivot = A[R];
    /* initialise scanning pointers */

    int pR = R;
    int pL = L;
    /* repeat until pointers cross */
    while (pL < pR) {
        compQS++;
        /* move left pointer */
        while (A[pL] < pivot) {
            pL++;
        }
        /* move right pointer */
        while ((A[pR] >= pivot) && (pR > L)) {
            pR--;
            //compQS++;
        }
        /* swap elements */
        //compQS++;
        if (pL < pR) {
            swap(pL, pR);
             L++;
             R--;
        }
    }


    /* put pivot in correct position */
    swap(pL, R);
    /* return pivot position */
    return pL;

}

/* swaps elements in quicksort */
public void swap(int i, int j) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}


    public class TestSort
{
    public static void main(String[] args) 
    {
        Sort sortTest = new Sort(100);



    /** Read in test data into array **/
    sortTest.readIn("test1.txt");

    /** Display array **/
    sortTest.display(10,"Input Array 1");
    /*apply insertion sort to array*/
    //sortTest.insertion(); 

    //sortTest.readIn("test1.txt");
    sortTest.quick(sortTest.getLeftElement(), sortTest.getRightElement());
    sortTest.newSort();

    /** Display comparison counters **/
    System.out.println("Quicksort comparison counter: " + sortTest.compQS);
    System.out.println("\n\nInsertion sort comparison counter: " + sortTest.compIS);


}

Answer 1

您的问题之一是 getLeftElement() 返回数组中位置 0 处的值，而不是仅返回 0。在数组中第一个元素的值大于数组大小的情况下，不会进行排序。

此外，我认为您对 quick 方法的实现是不正确的。在你递归调用的方法中 quick(L, pLoc - 1) 和 quick(pLoc + 1, R)。通过以这种方式调用，您不会遍历数组中数组的所有索引。（例如，如果 L 是 0，R 是 10，而 pLoc 是 5，那么您不涉及索引 5排序你的数组。）

Quicksort 数组没有正确打印出来？ (java)

Quicksort array is not printing out correctly? (java)

java

arrays

quicksort