八十一、最快最优的快速排序和优化

@Author：Runsen

编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。 ---- Runsen

快速排序

不久前，我在牛客中看到这样一个笑话，面试官让他写一个快速排序，结果他写了一个冒泡排序，虽说不是计算机专业的，还一直说没有写错，都不知道面试官为什么这么PASS。其实，一共有十大排序算法，最快最稳定的就是快速排序，简称快排。

quicksort 可以说是应用最广泛的排序算法之一，它的基本思想是分治法。基础的快速排序算法思想很简单，核心就是一句话：找到基准值的位置。

具体的过程其实和把大象装进冰箱这个问题一样，都可以分成三步：

第一步，选择一个值作为基准值。

第二步，找到基准值的位置，并将小于基准值的元素放在基准值的前面，大于基准值的元素放在基准值的后面。

第三步，对基准值的左右两侧递归地进行这个过程。

以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ]为例，选择一个支点, index= (L+R)/2 = (0+7)/2=3, 支点的值 pivot = arr[index] = arr[3] 

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/111474949