记录用kotlin实现冒泡、插入、希尔、归并、堆、快速排序 先定义2个工具函数
//测量时间 fun Long.nextTime(print: Boolean = true, which: String = "") { val cur = System.currentTimeMillis() if (print) { println("$which used time:${cur - this}") } this.plus(cur - this) } //交换位置 fun IntArray.swap(i: Int, j: Int) { val tmp = this[i] this[i] = this[j] this[j] = tmp } 冒泡排序 private fun bubbleSort(array: IntArray) { for (i in array.indices) { for (j in array.indices) { if (array[i] < array[j]) { array.swap(i, j) } } } } 插入排序 private fun insertSort(array: IntArray) { for (i in 1 until array.size) { var j = i - 1 val tmp = array[i] while (j >= 0 && tmp < array[j]) { array[j + 1] = array[j] j-- } array[j + 1] = tmp } } 希尔排序 private fun shellSort(array: IntArray) { var grap = array.size / 2 while (grap > 0) { for (i in grap until array.size) { var j = i - grap val tmp = array[i] while (j >= 0 && tmp < array[j]) { array[j + grap] = array[j] j -= grap } array[j + grap] = tmp } grap /= 2 } } 归并排序 private fun mergeSort(array: IntArray) { mergeSortGroup(array, 0, array.size - 1) } private fun mergeSortGroup(src: IntArray, l: Int, r:Int) { if (l < r) { val m = (l + r) / 2 mergeSortGroup(src, l, m) mergeSortGroup(src, m + 1, r) mergeSortMerge(src, l, m, r) } } private fun mergeSortMerge(src: IntArray, l: Int, m: Int, r:Int) { val dst = IntArray(r - l + 1) var li = l var ri = m + 1 for (i in dst.indices) { dst[i] = when { ri > r -> src[li++] li > m -> src[ri++] src[li] <= src[ri] -> src[li++] else -> src[ri++] } } for (i in dst.indices) { src[i + l] = dst[i] } } 堆排序 private fun heapSort(array: IntArray) { heapSortBuildMax(array.size, array) for (i in array.size - 1 downTo 1) { array.swap(0, i) heapSortMax(i, 0, array) } } private fun heapSortBuildMax(heapSize: Int, src: IntArray) { for (i in (src.size - 1) / 2 downTo 0) { heapSortMax(heapSize, i, src) } } private fun heapSortMax(heapSize: Int, index: Int, src: IntArray) { val li = index * 2 + 1 val ri = index * 2 + 2 var maxi = index if (li < heapSize && src[li] > src[maxi]) { maxi = li } if (ri < heapSize && src[ri] > src[maxi]) { maxi = ri } if (maxi != index) { src.swap(maxi, index) heapSortMax(heapSize, maxi, src) } } 快速排序 private fun quickSort(array: IntArray) { quickSort(array, 0, array.size - 1) } private fun quickSort(src: IntArray, l: Int, r: Int) { if (l < r) { val p = quickSortPartition(src, l, r) quickSort(src, l, p - 1) quickSort(src, p + 1, r) } } private fun quickSortPartition(src: IntArray, l: Int, r: Int) : Int { var li = l for (i in l until r) { if (src[i] <= src[r]) { src.swap(i, li) li++ } } src.swap(r, li) return li }测试运行时间
class Sort { private val source = generatorRandArray(1000000) private lateinit var standardSortArray : IntArray companion object { @JvmStatic fun main(args: Array<String>) { Sort().main() } } fun main() { //println("product array: " + source.contentToString()) standardSortArray = source.clone() standardSort() val time = measureTimeMillis { // val bubbleSortTest = GlobalScope.async { // runSort("bubble sort") { // bubbleSort(it) // } // } val insertSortTest = GlobalScope.async { runSort("insert sort") { insertSort(it) } } val shellSortTest = GlobalScope.async { runSort("shell sort") { shellSort(it) } } val mergeSortTest = GlobalScope.async { runSort("merge short") { mergeSort(it) } } val heapSortTest = GlobalScope.async { runSort("heap sort") { heapSort(it) } } val quickSortTest = GlobalScope.async { runSort("quick sort") { quickSort(it) } } runBlocking { //bubbleSortTest.await() insertSortTest.await() shellSortTest.await() mergeSortTest.await() heapSortTest.await() quickSortTest.await() } } println("run time = $time") } private fun standardSort() { println("sort by standard method!") val startTime = System.currentTimeMillis() Arrays.sort(standardSortArray) startTime.nextTime(which = "Arrays.sort") //println("sort by standard result: " + standardSortArray.contentToString()) } private fun runSort(sortName: String, sort: (IntArray) -> Unit) { val testArray = source.clone() println("sort by ${sortName}... ") val st = System.currentTimeMillis() sort(testArray) st.nextTime(which = sortName) println("$sortName test sort result: ${standardSortArray.contentEquals(testArray)}") } private fun generatorRandArray(size: Int): IntArray { val random = Random(System.currentTimeMillis()) return IntArray(size) { random.nextInt(size * 5) } } }控制台输出：
sort by standard method! Arrays.sort used time:200 sort by insert sort... sort by shell sort... sort by merge short... sort by heap sort... merge short used time:331 merge short test sort result: true sort by quick sort... shell sort used time:494 heap sort used time:454 shell sort test sort result: true heap sort test sort result: true quick sort used time:168 quick sort test sort result: true insert sort used time:110915 insert sort test sort result: true run time = 111073