上一篇方法一，在一些特殊输入下时间复杂度会退化为n平方，比如：a = [5,5,5,5,5,5,5]全部一样的情况下

方法二采用从左右两个方向遍历列表：

1.从左向右找到大于参考值t的元素，

2.从右向左找到小于参考值t的元素，

3.然后交换两个元素

 

具体实现如下代码所示：

需要注意的是在一次排序过程中，m必须为最后一个小于等于t的索引，然后将参考值t换到m的位置，完成一次筛选。

一次成功的筛选要求保证列表分为三个区间，小于t，等于t，大于t。如果存在多个相同值t的情况，则小于等于t，等于t，大于等于t

1 a = range(0,10) 2 random.shuffle(a) 3 print a 4  5 def qsort2(a, l, u): 6     if l >= u: 7         return 8          9     #选取列表第一个值为参考，以m为分界点，左边小于等于t，右边大于t    10     m = l11     t = a[l]12     13     #和方法一不同，这里使用了两个for循环14     while(1):15         #从左向右，找到比t大的值16         for i in range(l+1, j+1):17             if a[i] > t:18                 break19         else:20             #没有找到，i为最后一个比t小的值的索引21             m = i22             break23         24         #从右向左，找到比t小的值25         for j in range(u, i-1, -1):26             if a[j] < t:27                 break28         else:29             #没有找到，j为第一个比t大的值30             m = i - 131             break32         33         #交换i和j的值    34         a[i],a[j] = a[j],a[i]35         36     #循环结束，将参考值换到中间位置，完成一次筛选37     a[l],a[m] = a[m],a[l]38     39     #分别递归，m-1和m+1两个区间40     qsort2(a, l, m-1)41     qsort2(a, m+1, u)42     43 qsort2(a, 0, len(a)-1)44 print a

 

方法二仍然在一些常见的情况下，复杂度会退化，比如一个本来就有序的列表。还可以进一步改进该算法：参考值t改为随机选择，然后和第0个元素交换位置；对于基本有序的列表采用插入排序的方法。