Рекурсивно сортировка массива строк без вспомогательного параметра

Question

Одно из заданий моего профессора для меня оказывается особенно сложным. Я должен написать метод со следующим заголовком:

public static void sort(String[] a) 

Метод должны сортировать массив в порядке возрастания (не уверен, если это означает, что «порядок возрастание длины строки», но это то, что я предполагаю) ,

Уловка: Мне не разрешено каким-либо образом изменять заголовок метода, мне не разрешено использовать сортировку или сортировку слиянием, и мне не разрешено использовать какие-либо посторонние пакеты/библиотеки.

Слияние сортировки и быстрая сортировка не разрешены для меня, поскольку я тоже не очень люблю, но мне трудно понять, как это сделать, не передавая вспомогательный параметр (для хранения позиция индекса для массива), которая будет использоваться в рекурсивных вызовах.

Это то, что я придумал после нескольких часов разочарования и в основном спиннинг мои колеса:

public static void sort(String[] a) 
{ 

    String temp; 

    // Note that we use a.length - 1 in the loop condition 
    // to account for the fact that we will be checking the value of the 
    // element at the current index against the value of the element at the NEXT index. 
    // Since array indices are zero-based, iterating from 0 to a.length would result 
    // in an ArrayIndexOutOfBoundsException when we index = 7, since the 
    // base case would check a[7] against a[8], the latter of which does not exist 

    for (int index = 0; index < a.length - 1; index++) 
    { 
     if (a[index].length() < a[index + 1].length()) 
     { 
      continue; 
     } 
     else 
     { 
      temp = a[index + 1]; 
      a[index + 1] = a[index]; 
      a[index] = temp; 

      // Recursive call to the sort method 
      sort(a); 
     } 
    } 
} 

Основная идея состояла в том, чтобы проверить каждый элемент «несколько раз» с для петель таким образом, чтобы стимулировать каждый элемент попадает в свое «надлежащее место» (в смысле «возрастающего порядка»). Я сомневаюсь, что это правильно, хотя я не тестировал его (профессор еще не загрузил драйвер для этого задания).

Если нет, может кто-нибудь может указать мне в правильном направлении? Кажется, что не существует методов в классе Array или String, который был бы здесь полезен. Я даже не вижу возможности для рекурсии здесь; не было бы бесполезно, если бы я просто передавал метод один и тот же массив снова и снова?

Answer 1

Это решение немного неэффективно, поскольку оно предполагает создание новых массивов и копирование, но оно соответствует требованиям, которые рекурсия должна использоваться с предоставленной сигнатурой метода. Он также удовлетворяет требованию, чтобы слияние сортировки и быстрого сортировки не использовалось.

import java.util.Arrays; 

public class RecursiveInsertionSort { 
    public static void sort(String[] a) 
    { 
     if (a.length==1) { 
      return; 
     } 
     // Copy array from 1..length-1 into new array rest 
     String rest [] = Arrays.copyOfRange(a, 1, a.length); 
     // sort rest 
     sort(rest); 
     // insert a[0] into rest and store the result in a 
     insert(a,rest); 
    } 

    // insert a[0] into sort and store result in a 
    private static void insert(String [] a, String [] sorted) { 
     int i; 
     String saveFirst = a[0]; 

     // Find index 'i' where such that sorted[i] > a[0] 
     for (i=0; i < sorted.length; i++) { 
      if (saveFirst.compareTo(sorted[i])<0) { 
       break; 
      } 
     } 
     // Copy elements less than a[0] from sorted to a 
     for (int j=0; j < i; j++) { 
      a[j] = sorted[j]; 
     } 
     // insert a[0] 
     a[i] = saveFirst; 
     // copy elements greater than a[0] from sorted to a 

     for (int j=i+1; j < a.length; j++) { 
      a[j] = sorted[j-1]; 
     } 

    } 
    public static void main(String args[]) { 
     String [] testData = {"Apples", "Oranges", "Cranberries", "Guava" }; 
     sort(testData); 
     for (String s: testData) { 
      System.out.println(s); 
     } 
    } 
} 

Answer 2

использовать (на месте) selection sort:

• для каждого элемента массива, первого до последнего
  • итерацию по элементам от текущего элемента до последнего, находя наименьший (который может быть токовым элементом)
  • своп наименьший с текущим

Или (на месте) insertion sort:

• для каждого элемента массива, первый до последнего
  • сдвига предыдущих элементов вправо, пока текущий элемент не меньше, чем элемент просто сдвинут и поместить текущий элемент в промежутке только что создал

Сложность времени для обоих составляет O (n), но сложность пространства O (1).

Проблема не говорит, что она должна быть рекурсивной.