Выбор алгоритма сортировки для строк

Question

У меня возникла проблема с выбором выбранного алгоритма сортировки для сортировки строк в массиве в алфавитном порядке. Мой код как есть, полный беспорядок.

public class sorting { 
public void getArray(String [] a) { 
    int min = 0; 
    int minIndex = 0; 
    for (int j = 0; j < a.length; j++) { 
     for (int i = j; i < a.length; i++) { 
      if (i == j) { 
       a[min] = a[j]; 
      } 
      if (a[min].compareTo(a[i]) < 0) { // if current element is < lowest, assign new lowest. 
       a[min] = a[i]; 
       minIndex = i; 
      } // end of if 
     } // end of INSIDE for 

     a[minIndex] = a[j]; // place first element at the location of the smallest element. 
     a[j] = a[min]; // place the smallest element value in the first spot. 
    } // end of OUTSIDE for  
} 

Может ли кто-нибудь объяснить мне, как их мыслительный процесс происходит по этому поводу? Например, что делает внутренний цикл for вне внешнего? Спасибо заранее!

Answer 1

Очень просто говоря, выбор рода делает следующее:

1. Найти наименьший элемент
2. Своп его с первым элементом
3. найти второй наименьший элемент
4. поменять его со вторым элементом
5. ... (и так далее)

После шагов 1 и 2 вы знаете, что самый маленький элемент находится в первом месте массива. На шаге 3 вы ищете второй наименьший элемент, который является наименьшим, если вы начнете поиск со второй позиции.

Это то, что делает внешний цикл: найти j-й наименьший элемент и поменять его на элемент в пятне j.

Теперь, как вы находите наименьший элемент в массиве? Для этого вам нужен внутренний цикл. Вы отслеживаете самый маленький элемент до сих пор (и индекс, где вы его нашли), и всякий раз, когда вы находите меньший элемент, вы обновляете текущий наименьший элемент (и индекс, где вы его нашли).

---

Есть две ошибки в коде, хотя:

1. Когда вы отслеживаете минимальный элемент массива, вы перезапись элементы вашего входа. Вместо того, чтобы использовать a[min], вы всегда должны использовать min (для этого вам необходимо, например, изменить тип на String).
2. Вы должны проверить, меньше ли a[i], чем min, а не наоборот.

if (i == j) { 
    min = a[j]; 
} 
if (a[i].compareTo(min) < 0) { 
    min = a[i]; 
    minIndex = i; 
} 

и в конце концов:

a[minIndex] = a[j]; 
a[j] = min; 

Answer 2

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

Этот метод перебирает струны и, для каждой записи, называет swapMinFromIndex

public void sortStrings(String[] strings) { 
    for (int i = 0; i < strings.length; i++) 
     swapMinFromIndex(strings, i); 
} 

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

private void swapMinFromIndex(String[] strings, int start) { 
    int indexOfMin = start; 
    for (int i = start + 1; i < strings.length; i++) { 
     if (strings[i].compareTo(strings[indexOfMin]) { 
      indexOfMin = i; 
     } 
    } 
    if (indexOfMin != start) { 
     String tmp = strings[start]; 
     strings[start] = strings[indexOfMin]; 
     strings[indexOfMin] = tmp; 
    } 
} 

Таким образом, эти два метода постоянно ищут наименьший элемент и заменяют его на место.