Сложность: O(n²) в худшем и среднем случае, O(n) в лучшем (уже отсортированный массив)
fun bubbleSort(arr: IntArray) {
for (i in 0 until arr.size - 1) {
for (j in 0 until arr.size - i - 1) {
if (arr[j] > arr[j + 1]) {
// Меняем элементы местами
val temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
}
Применение в Android: Практически не используется, только в учебных целях.
Сложность: Всегда O(n²)
fun selectionSort(arr: IntArray) {
for (i in arr.indices) {
var minIdx = i
for (j in i+1 until arr.size) {
if (arr[j] < arr[minIdx]) {
minIdx = j
}
}
val temp = arr[minIdx]
arr[minIdx] = arr[i]
arr[i] = temp
}
}
Особенности: Меньше перестановок чем у Bubble Sort, но все равно неэффективен для больших данных.
Сложность: O(n²) в худшем, O(n) в лучшем случае
fun insertionSort(arr: IntArray) {
for (i in 1 until arr.size) {
val key = arr[i]
var j = i - 1
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
}
Применение в Android: Полезен для почти отсортированных массивов или маленьких наборов данных (n < 50).
Сложность: Всегда O(n log n)
fun mergeSort(arr: IntArray): IntArray {
if (arr.size <= 1) return arr
val middle = arr.size / 2
val left = arr.sliceArray(0 until middle)
val right = arr.sliceArray(middle until arr.size)
return merge(mergeSort(left), mergeSort(right))
}
fun merge(left: IntArray, right: IntArray): IntArray {
var leftIndex = 0
var rightIndex = 0
val result = mutableListOf<Int>()
while (leftIndex < left.size && rightIndex < right.size) {
if (left[leftIndex] < right[rightIndex]) {
result.add(left[leftIndex++])
} else {
result.add(right[rightIndex++])
}
}
while (leftIndex < left.size) result.add(left[leftIndex++])
while (rightIndex < right.size) result.add(right[rightIndex++])
return result.toIntArray()
}
Преимущества: Стабильная сортировка, хороша для больших данных.
Сложность: O(n log n) в среднем, O(n²) в худшем случае
fun quickSort(arr: IntArray, low: Int = 0, high: Int = arr.size - 1) {
if (low < high) {
val pi = partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
}
}
fun partition(arr: IntArray, low: Int, high: Int): Int {
val pivot = arr[high]
var i = low - 1
for (j in low until high) {
if (arr[j] <= pivot) {
i++
arr[i] = arr[j].also { arr[j] = arr[i] }
}
}
arr[i + 1] = arr[high].also { arr[high] = arr[i + 1] }
return i + 1
}
Применение в Android: Используется в стандартных библиотеках Java/Kotlin (но с модификациями).
Сложность: O(n log n)
Гибридный алгоритм, сочетающий Merge Sort и Insertion Sort. Именно он используется в:
Сложность: O(n + k), где k - диапазон значений Ограничение: Только для целых чисел в небольшом диапазоне
Сложность: O(nk), где k - количество цифр Применение: Для сортировки строк или больших чисел
// Рекомендуемый подход в Android:
val list = mutableListOf(5, 2, 8, 1)
list.sort() // Использует оптимизированный Timsort