冒泡排序

import java.util.Date

// Time Complexity O(n^2)
// Space Complexity O(1)
// neighbours change places until a pass makes no swaps:
// the largest element "bubbles up" to the end on every pass

fun sort(arr: Array<Int>): Array<Int> {
    val items = arr.copyOf()
    for (end in items.size downTo 2) {
        var swapped = false
        for (j in 1..<end) {
            if (items[j] < items[j - 1]) {
                val tmp = items[j]
                items[j] = items[j - 1]
                items[j - 1] = tmp
                swapped = true
            }
        }
        if (!swapped) {
            break
        }
    }
    return items
}

var items = arrayOf(4, 1, 5, 3, 2)

val sortItems = sort(items)
// sortItems is {1, 2, 3, 4, 5}
sortItems.forEach { print("$it ") }
println()

// *** simplified speed test ***
items = Array(200) { 0 }
    .mapIndexed { i, _ -> i }
    .reversed()
    .toTypedArray()
val count = 10000
val start = Date()

for (i in 0..<count) {
    sort(items)
}

val milliseconds = Date().time - start.time

println("$milliseconds milliseconds")
// about 259 milliseconds