@TOC
前言
年后放假回来得了假期综合征，懒劲上来了，之前一直想更新的博客一拖再拖，再拖下去自己都不好意思了。
前几天看了看各个大厂的安卓面试题，发现大厂的安卓面试都会在最后考一道快速排序算法，算法对于我现在来说不太熟练，就跟着网上的敲了一下，就在这里做下总结。
快速排序算法
网络上有总结快速排序算法的复杂度为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 + 1var lastElement = rightwhile (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] = tagnextElement++lastElement--}//将基准元素与array[nextElement]交换val tag = array[left]array[left] = array[lastElement]array[lastElement] = tag//返回基准元素所在位置return lastElement
}
复制代码经过比照发现，数值比较少的时候插入排序算法比快速排序算法更快，效率更高。足见“快排”只是平均性能最好。
最后总结
最近由快排延伸去研究了一下别的排序算法，算是对于算法第一次细致研究。算法这东西，还是挺有搞头的，锻炼数学技能。之后有机会再去研究其他的常用算法，毕竟要多多少少了解一下。