使用字符串进行插入排序

Question

我将 2 个主要 classes 合并为一个，以显示插入数组字符串的未排序和排序值。给出的代码使用的是整数，我将其改为执行字符串。我的 insertionSort() 有问题。比较线导致它崩溃，我不知道为什么！

 public void insertionSort()
  {
  int in, out;

  for(out=1; out<nElems; out++)     // out is dividing line
     {
     String temp = a[out];            // remove marked item
     in = out;                      // start shifts at out
     System.out.println(a[in]);
   --->while(a[in].compareTo(a[in+1])>0 ) // until one is smaller,
        {
        a[in] = a[in-1];            // shift item to right
        --in;                       // go left one position
        }
     a[in] = temp;                  // insert marked item
     }  // end for
  }  // end insertionSort()

这是我的主要内容class:

   class SortApp
  {
  public static void main(String[] args)
    {
    int maxSize = 100;            // array size

  ArraySel arr;//reference to ray1--> selection sort
  ArrayIns arr2;// reference to array2--> insertion sort
  arr = new ArraySel(maxSize);  // create the array
  arr2 = new ArrayIns(maxSize);

  arr.insert("hello"); //insert words into the array
    arr.insert("this");
    arr.insert("is");
    arr.insert("a");
    arr.insert("random");
    arr.insert("weird ");
    arr.insert("sentence");
    arr.insert("that");
    arr.insert("does");
    arr.insert("not");
    arr.insert("make");
    arr.insert("any");
    arr.insert("sense");

    arr2.insert("hello");
    arr2.insert("this");
    arr2.insert("is");
    arr2.insert("a");
    arr2.insert("random");
    arr2.insert("weird ");
    arr2.insert("sentence");
    arr2.insert("that");
    arr2.insert("does");
    arr2.insert("not");
    arr2.insert("make");
    arr2.insert("any");
    arr2.insert("sense");

    arr.display();                // display items
  arr2.display();

  arr.selectionSort();//sort the 2 arrays
  arr2.insertionSort();

  arr.display();                // display them again
  arr2.display();
  }  // end main()
   }  // end class SelectSortApp

这里是更新后的 selectionSort class

public void selectionSort()
  {
  int out, in, min;

  for(out=0; out<nElems-1; out++)   // outer loop
     {
     min = out;                     // minimum
     for(in=out+1; in<nElems; in++) // inner loop

         if((a[in].compareTo(a[in-1])>0 ))        // if min greater,
            min = in;               // we have a new min
     swap(out, min);                // swap them

Answer 1

您需要比较 a[in] 和 a[in-1] 而不是 a[in+1]。您的交换已经使用了正确的元素。按原样使用代码，a[in+1] 可以超过数组的上限，

Answer 2

您真的很接近解决方案

您应该比较 temp 与 a[in-1] 而不是 a[in] 与 a[in+1]

您还需要检查 in 在 while loop 上始终为正，以避免 IndexOutOfBoundsException

while(in > 0 && temp.compareTo(a[in-1]) < 0) 
{

Answer 3

这是我现在可以使用的选择排序：

public void selectionSort() {
   int out, in, min;
    for(out=0; out<nElems-1; out++)   // outer loop
    {
       min = out;                     // minimum
       for(in=out+1; in<nElems; in++) // inner loop
           if((a[in].compareTo(a[min])<0 ))        // if min greater,
               min = in;               // we have a new min
       swap(out, min);                // swap them
     }  // end for(out)
  }  // end selectionSort()

使用字符串进行插入排序

Insertion Sort using a String

java

arrays

string

insertion-sort