选择排序法
object SelectionSort {
fun <E : Comparable<E>> sort(array: Array<E>) {
for (index in array.indices) {
//arr[i..n)未排序 arr[0..i)已排序
//arr[i..n)中的最小值要放到arr[i]的位置
var minIndex = index
for (j in minIndex until array.size) {
if (array[j] < array[minIndex]) {
minIndex = j
}
}
array.swap(index, minIndex)
}
}
private fun <E> Array<E>.swap(i: Int, j: Int) {
val temp = this[i]
this[i] = this[j]
this[j] = temp
}
}
时间复杂度O(n^2)
object InsertionSort {
//正序交换排序
fun <E : Comparable<E>> sort(array: Array<E>) {
// 保持[0,i)有限有序,[i,array.length)无序
for (i in array.indices) {
// 保证[0,i)每个元素都比前一个元素大
for (j in i downTo 1) {
if (array[j] < array[j - 1]) {
array.swap(j, j - 1)
} else {
break
}
}
}
}
//正序原地排序
fun <E : Comparable<E>> sort2(array: Array<E>) {
for (i in array.indices) {
val e = array[i]
var j: Int = i
while (j > 0) {
if (e < array[j - 1]) {
array[j] = array[j - 1]
} else {
break
}
j--
}
array[j] = e
}
}
//逆序排序
fun <E : Comparable<E>> sort3(array: Array<E>) {
for (i in array.size - 1 downTo 0) {
val e = array[i]
var j = i
while (j < array.size - 1) {
if (e > array[j + 1]) {
array[j] = array[j + 1]
} else {
break
}
j++
}
array[j] = e
}
}
private fun <E> Array<E>.swap(i: Int, j: Int) {
val temp = this[i]
this[i] = this[j]
this[j] = temp
}
}
时间复杂度O(n^2)
选择排序和插入排序的区别在于无论数组是否有序,选择排序的时间复杂度都是O(n^2),插入排序在数组有序的情况下,时间复杂度会变成为O(n)
Q.E.D.