Сортировка, выбор и поиск

Сортировка

Поскольку Spire предоставляет специализированный класс типов упорядочения, имеет смысл также предоставить свои собственные методы для выполнения операций на основе Order

. Эти методы определены в массивах и "возникают на месте", изменяя массив. Другие коллекции могут воспользоваться преимуществами сортировки путем преобразования в массив, последующей сортировки и обратного преобразования (что уже делает платформа коллекций Scala в большинстве случаев). Таким образом, Spire поддерживает как изменяемые массивы, так и неизменяемые коллекции.

Методы сортировки можно найти в объекте spire.math.Sorting

. Это:

• quickSort
  : самый быстрый, \(O(n*log(n))\), нестабильный с потенциалом \(O(n^{2})\) в худшем случае
• mergeSort
  : также быстрый, \(O(n*log(n))\), стабильный, но выделяет дополнительное временное пространство
• insertionSort
  : \(O(n^{2})\), но стабильный и быстрый для небольших массивов
• sort
  : псевдоним для quickSort

Оба mergeSort

и quickSort

делегируют insertionSort

при работе с массивами (или срезами) ниже определенной длины. Поэтому правильнее было бы назвать их гибридными сортировками.

Выборка

Методы выбора можно найти в аналогичном объекте spire.math.Selection

. Учитывая массив и индекс k

, эти методы помещают k-й наибольший элемент в позицию k

, гарантируя, что все предыдущие элементы меньше или равны, а все последующие элементы больше или равны k-му элементу.

Определено два метода:

• quickSelect
  : обычно быстрее, нестабильнее, потенциально плохой в худшем случае
• linearSelect
  : обычно медленнее, но с гарантированной линейной сложностью
• select
  : псевдоним для quickSelect

Поиск

Методы поиска расположены в объекте spire.math.Searching

. Учитывая отсортированный массив (или индексированную последовательность), эти методы найдут индекс нужного элемента (или вернут -1

, если он не найден).

• search(array, item)
  : находит индекс item
  в array
  .
• search(array, item, lower, upper)
  : поиск осуществляется только между lower
  и upper
  .

Поиск также поддерживает более эзотерический метод: minimalElements

. Этот метод возвращает минимальные элементы частично упорядоченного набора.

---

Ссылки:

• Spire home page