之前排序内容概述
这是之前的****快速排序*****讲解，主要讲解了三种算法（霍尔版本，挖坑法，前后指针法），然后是递归版本和非递归版本，用非递归版本主要是为了解决栈溢出的问题，但是却不能解决某些情况时间复杂度坍缩成O(N²)，例如当待排数据已经有序的时候就会坍缩，就产生了三数取中的方法，尽可能的让每次排序左右均分。
新问题
但是还是有一定的问题，比如全是同样的数据时也会坍缩，因为三数取中无论怎么取都是一样的，不起效果。
那么就有另一种算法来完成子排序：
三路分化
三路分化原理
A.我们以arr[0]的数据作为K，即一次排序的中间值，左边比它小右边比它大。
B.这里创造三个指针，left指向开头，cur指向left下一个下标，right指向末尾下标。
C.我们的cur会扫遍整个数组，直到超过right指针。
D.cur的运动过程是：如果此时 arr[cur]<K 就让left的值和cur的值交换，并让left和cur向后移动一格；如果此时 arr[cur]==K 那么就只让cur向后移一位；如果此时 arr[cur]>K 就让cur的值和right的值交换，并让right向左移，而cur不移动。结果就是cur继续和right交换，然后重复操作，直到cur和right交换后cur的值不再大于K为止。那么就会进行前两个操作，cur就继续往后移动了。
我们看了D这个过程后，就可以总结出，left之前的是比K小的，left和cur之间的是等于K的，right之后的是大于K的。并且发现left的值始终等于K。
我们通过下面的GIF来看看整个过程
代码实现
优点
三路分化的优点就是将重复的K数据直接放在中间，之后的子排序不再参与。
那么重复度大的数据进行排序就会省很多事。
三路分化优化
我们将cur与right进行交换的时候，这个过程可能持续很多次，因为换过来的值可能还是比K要大，所以我们可以让right往左移一直找到小于等于K的数值，再进行交换。这样就减少了交换的次数。
这个我测过，没有这个之前在力扣里面是过不了的，写了就能过了。
自省排序
虽然上面的可以解决很多种情况，但是还是不能100%的排除栈溢出的风险，所以就有了自省排序。
我们每次递归就让一个传入值deep加一来记录递归的深度，如果deep>2*hight就可以换成堆排序,这个结论是前人通过大量实验的出来的。这里的hight表示的是这次递归的最大深度。
那么我们通过以上代码就可以实现了，通过下面的for循环来求hight=log(r-l+1)，让后我们核心排序可以用前后指针等都行，因为如果递归次数过深都会调用堆排
