|
比如有如下几个数，在中间找到一个数字（偶数时中间那两个的随便一个都行）作为标准数，想法使左边的数都不大于标准数，右边的都不小于标准数，然后递归；
怎么是左边的数都不大于标准数，右边的不小于标准数呢？我用的的是挖坑托管法，
详情看下面：
如下面的数要排序：
找到一个中间的数字9；
现在做的就是使左边所有的数字不大于9，右边所有的数字都不小于9
1. 那么在左边找到第一个比9大的数字，把他取出来并放到托管所1里面（意味着取数的地方留下了一个坑，这样比较形象），然后在右边找到第一个比9小的数字，把他放到托管所2里面（意味着取数的地方留下了一个坑）；
2. 将托管所里面的两个数字交换，这样就达到了左边的那个坑的数字比9（标准）小，右边那个坑的数字比9大；（如果这里记录一下左边一定比9小的数的最长位置，右边一定比9大的数的最长位置，就会降低时间复杂度，但是这里不记录就是为了直观）
上图中可以看到左边（从左往右看）两个数比9不大，右边（从右往左看）两个数比9不小，（右边明明有三个数56 45 78比9大，但是78我们根本就不知道是否比9大，因为前面找的时候找到倒数第二个位置的时候就中止了）
现在就要做的就是接着在左边找到第一个比9大的数取出来形成一个坑并放到托管所1，然后在右边（从右往左）找到第一个比9小的数取出来放到托管所2,然后同上一样交换
![]()
接着重复上面，现在发现左边找到了32而右边却没有比9小的数字了，怎么办呢？
办法就是如果左边或右边没有找到合适的数字，那么就将9（标准数）作为没找到那一边的托管所里面，见下图：
交换后
就这样，左边所有的数字都比32小（现在是32作为中间数），右边所有的数都比32大
然后递归32的左边和右边，这个就不说了
| 
转播
