需要关于Arraylist快速排序和分区的帮助吗

Question

说明：

给定读取用户ID（直到-1）的main（），完成快速排序（）和分区（）方法，使用快速排序算法按升序对ID进行排序，并每行输出一个排序后的ID。

示例输入：

kaylasimms 
julia 
myron1994 
kaylajones 
-1

样本输出：

julia 
kaylajones
kaylasimms
myron1994 

我运行并构建了我的代码，它没有显示任何错误，所以我猜我的方式有问题。输出仅按我输入的顺序显示字符串，但没有-1。

我的代码：

import java.util.Scanner;
import java.util.ArrayList;

public class UserIDSorting {
   // TODO: Write the partitioning algorithm - pick the middle element as the 
   //       pivot, compare the values using two index variables l and h (low and high), 
   //       initialized to the left and right sides of the current elements being sorted,
   //       and determine if a swap is necessary
   

public static int partition(ArrayList<String> numbers, int lowIndex, int highIndex) {
   // Pick middle element as pivot
   int midpoint = (lowIndex + (highIndex - lowIndex) / 2);
   int pivot = midpoint;
   
   boolean done = false;
   while (!done) {
      // Increment lowIndex while numbers[lowIndex] < pivot
      while (lowIndex < pivot) {
         lowIndex += 1;
      }
      
      // Decrement highIndex while pivot < numbers[highIndex]
      while (pivot < highIndex) {
         highIndex -= 1;
      }
      
      // If zero or one elements remain, then all numbers are 
      // partitioned. Return highIndex.
      if (lowIndex >= highIndex) {
         done = true;
      }
      else {
         // Swap numbers[lowIndex] and numbers[highIndex]
         int temp = lowIndex;
         lowIndex = highIndex;
         highIndex = temp;
         
         // Update lowIndex and highIndex
         lowIndex += 1;
         highIndex -= 1;
      }
   }
   
   return highIndex;
}

public static void quicksort(ArrayList<String> numbers, int lowIndex, int highIndex) {
   // Base case: If the partition size is 1 or zero 
   // elements, then the partition is already sorted
   if (lowIndex >= highIndex) {
      return;
   }
   
   // Partition the data within the array. Value lowEndIndex 
   // returned from partitioning is the index of the low 
   // partition's last element.
   int lowEndIndex = partition(numbers, lowIndex, highIndex);
   
   // Recursively sort low partition (lowIndex to lowEndIndex) 
   // and high partition (lowEndIndex + 1 to highIndex)
   quicksort(numbers, lowIndex, lowEndIndex);
   quicksort(numbers, lowEndIndex + 1, highIndex);
}  

   public static void main(String[] args) {
      Scanner scnr = new Scanner(System.in);

      ArrayList<String> userIDList = new ArrayList<String>();

      String userID = "";

      
      while (!userID.equals("-1")) {
         userID = scnr.next();
         userIDList.add(userID);
      }
      
      // Initial call to quicksort 
      quicksort(userIDList, 0, userIDList.size() - 2);

      for (int i = 0; i < userIDList.size(); ++i) {
         System.out.println(userIDList.get(i));
      }
   }
}

Answer 1

在某个时刻，你需要交换这些值，对吗？你计算索引，但你从来没有做过像数字这样的事情。设置（索引、值）。。。结果与输入完全相同，这并不奇怪。