前言

​ 年后放假回来得了假期综合征，懒劲上来了，之前一直想更新的博客一拖再拖，再拖下去自己都不好意思了。

前几天看了看各个大厂的安卓面试题，发现大厂的安卓面试都会在最后考一道快速排序算法，算法对于我现在来说不太熟练，就跟着网上的敲了一下，就在这里做下总结。

快速排序算法

​ 网络上有总结快速排序算法的复杂度为nlogn。这里的nlogn表示为算法的时空复杂度。标准写法为O(n*logn)。时间复杂度为O(n),代表的是数据量增大多少倍，耗时就增大多少倍。而O(Logn

)代表的是当数据增大n倍时，耗时增大logn倍(这里是

)而O(nlogn)就是当数据增大n倍时，耗时增大nlogn倍，当数据增大256倍时，耗时增大256*8倍。

原理思想就是每一次排序都找到一个基准元素，将小于基准元素的元素放在基准元素的左边，将大于基准元素的元素放在基准元素的右边。通过这个描述大概就知道了，快速排序的关键是找到这个基准元素。

算法实现

private fun quickSort(array: IntArray, left: Int, right: Int) {

if (left >= right) {

return

}

//进行第一轮排序获取分割点

val index = partition(array, left, right)

//排序前半部分

quickSort(array, left, index - 1)

//排序后半部分

quickSort(array, index + 1, right)

tv_result.text = array.toString()

}

private fun quick(array: String) {

val arr = IntArray(array.length)

for (i in 0 until array.length) {

arr[i] = Integer.parseInt(array.substring(i, i + 1))

}

if (array.isNotEmpty()) {

quickSort(arr, 0, arr.size - 1)

}

}

复制代码

以上是快速排序的的实现部分，其中一个方法非常关键，就是partition()。这个方法用来确定基准元素。

private fun partition(array: IntArray, left: Int, right: Int): Int {

//第一个为基准元素

val baseElement = array[left]

var nextElement = left + 1

var lastElement = right

while (true) {

while (nextElement <= right && array[nextElement] < baseElement) nextElement++

while (lastElement > left && array[lastElement] > baseElement) lastElement--

//循环终止条件

if (nextElement > lastElement) break

// 交换 array[nextElement]与array[lastElement]

val tag = array[nextElement]

array[nextElement] = array[lastElement]

array[lastElement] = tag

nextElement++

lastElement--

}

//将基准元素与array[nextElement]交换

val tag = array[left]

array[left] = array[lastElement]

array[lastElement] = tag

//返回基准元素所在位置

return lastElement

}

复制代码

经过比照发现，数值比较少的时候插入排序算法比快速排序算法更快，效率更高。足见“快排”只是平均性能最好。

最后总结

​ 最近由快排延伸去研究了一下别的排序算法，算是对于算法第一次细致研究。算法这东西，还是挺有搞头的，锻炼数学技能。之后有机会再去研究其他的常用算法，毕竟要多多少少了解一下。