python实现快速排序

qingkuangs

　　快速排序可以把时间复杂度优化到nlog2n，省心多了。。。
　　来八卦一下快速排序
　　1. 快速排序就是选定一个标志位，我们把它叫做flag，期望把小于flag的放在它的左边，把大于flag的放在它的右边，这样就以flag的分界，把原来的list分为了两个子list ： list1 和 list2。
　　2. 按照上述方法，在list1 和 list2中再分别选flag，将list2 和 list2 分别拆成两个list，依次类推
　　3. 直到n = 1，即每个子list都只有一个元素  整个过程 : n/2x = 1  x = log2n

　　那么如何实现step1呢，既然有的元素比flag大，有的元素比flag小，那么我们定义两个游标，一个指向大于flag的元素，一个指向小于flag的元素，选定list中的最后一个元素作为flag
　　list = [5,1,3,8,9,4,7,6]
　　（整个过程，可以在纸上先写一写，分析一下就很清楚了）
　　在上面的列表中，选择list[-1] = 6作为flag位，定义游标 i 和游标 j ，i指向大于flag的元素，j指向小于flag的元素。
　　Step1 ：将 i 初始化到-1 位置，将 j 初始化到 0 位置
　　Q：为什么将 i 初始化到-1位置，即指向列表前面一个空的位置？
　　A：等下解释。。。
　　Step2：j ：0——>len（list）-1
　　比较list[j]和flag，在例子中，现在j=0，list[0] < flag，这时候 i= i+1， exchange list 和 list[j]的值
　　Q：现在 i 和 j 指向的都是0的位置，为什么自己要和自己交换呢？
　　A：可以在代码中看到，这样做其实是为了保持程序的一致性，当然你也可以自己判断，如果i 和 j 指向的都是同一个位置，那没必要交换
　　Step3：j++，到了j=（index）3的时候，这时候 i 还是指向（index）2的，发现，list[j=3] = 8 是大于flag的，那么，i 原地不动 ，即现在i 还是指向index=2的位置，i 不往前走了。
　　Step4：当 j 走到5的时候，list[5] = 4，它小于flag ，而它前面的8 和 9 都比flag大，那么，也肯定比list[5] = 4要大了，好，i+1，即 i 现在指向（index）3，即value=8，exchange list 和 list[j]，然后j 继续向前走。
　　总之，j 先走，只要碰到小于flag的数，i 就+1，只要碰到大于flag的数，i 就原地不动，j 继续向前走，目前就是把后面小的数给挪到前面来。
　　现在，来解释一下为什么将i 初始化到 -1 的位置呢？
　　很简单，当第一个位置的元素大于flag时，i 指向0，原地不动，而j 继续向前走，当遇到下面一个比flag小的元素时，i+1，那么，你就永远处理不到第一个元素了，嗯，就是这个原因，可以自己在纸上写一下，一下子就看出来了。
　　上面的过程可以用下面的代码实现;
　　



1 if __name__ == '__main__':
2     l = [5,1,3,8,9,4,7,6]
3
4     def first_sort(l):
5         flag = l[-1]
6         i = -1
7         for j in range(len(l)-1):
8             if l[j] > flag:
9                 pass
10             else:
11                 i += 1
12                 tmp = l
13                 l = l[j]
14                 l[j] = tmp
15         print(l)
16         print("\n" + "*"*20 + "\n")
17
18         tmp = l[-1]
19         l[-1] = l[i+1]
20         l[i+1] = tmp
21
22         print(l)
23         print("\n" + "*"*20 + "\n")
24
25     first_sort(l)
　　
　　运行后的结果为：



[5, 1, 3, 4, 9, 8, 7, 6]
********************
[5, 1, 3, 4, 6, 8, 7, 9]
********************
　　从第一个打印出的list来看，小于flag的和大于flag的已经分开了
　　将list[-1] 和 list[i+1] 交换，那么第一次快排就完成了，（运行结果的第二条）
　　清楚了这个过程以后，接下来就是递归的事儿了，呃，不想写了，好累。。。直接贴代码。



1     def path_sort(list,start_index,end_index):
2         flag = list[end_index]
3         i = start_index - 1
4         for j in range(start_index,end_index):
5             if list[j] > flag:
6                 pass
7             else:
8                 i += 1
9                 tmp = list
10                 list = list[j]
11                 list[j] = tmp
12         tmp = l[end_index]
13         l[end_index] = l[i+1]
14         l[i+1] = tmp
15
16         return i+1
17
18     def Quick_sort(list,start_index,end_index):
19         if start_index >= end_index:
20             return
21         middle = path_sort(list,start_index,end_index)
22         Quick_sort(list,start_index,middle-1)
23         Quick_sort(list,middle+1,end_index)
24         print(l)
25
26     Quick_sort(l,0,len(l)-1)
　　ps，其实不难的，只要你肯认真思考。O(&cap;_&cap;)O~