Kotlin 的快排之美？

在掘金某文中看到了这个链接：https://www.freecodecamp.org/news/my-favorite-examples-of-functional-programming-in-kotlin-e69217b39112/

里面有一个快排栗子：

fun <T : Comparable<T>> List<T>.quickSort(): List<T> =
    if (size < 2) this
    else {
      val pivot = first()
      val (smaller, greater) = drop(1).partition { it <= pivot }
      smaller.quickSort() + pivot + greater.quickSort()
    }

kotlin 高阶函数partition用于分组数据，drop 用于剔除第一个 pivot 元素。

看上去就很明朗了。我拿去跑了一下，表示确实可以正常运行，当然效率有所牺牲。运行了两次效率如下：

如果使用传统快排呢？

fun quickSort(a: IntArray, left: Int, right: Int){
    if(left>right) return

    val pivot=a[left]
    var i=left
    var j=right

    while(i<j)
    {
        while(pivot<=a[j]&&i<j)//从右往左找比基准值小的数
            j--
        while(pivot>=a[i]&&i<j)//从左往右找比基准值大的数
            i++

        if(i<j){
            //swap
            a[i]=a[j].also{
                a[i]=a[j]
            }
        }
    }
    a[left]=a[i]
    a[i]=pivot
    quickSort(a,left,i-1)
    quickSort(a,i+1,right)
}

拿去跑了一下，结果确实好一些。

不过原作者也说了这个问题：

用一些可读性换一些效率的丢失~ 不过，工作中一般没人自己写快排。

关于快排的思考题：

快速排序法为什么一定要从右边开始？