python实现快速排序
快速排序可以把时间复杂度优化到nlog2n，省心多了。。。来八卦一下快速排序
1. 快速排序就是选定一个标志位，我们把它叫做flag，期望把小于flag的放在它的左边，把大于flag的放在它的右边，这样就以flag的分界，把原来的list分为了两个子list ： list1 和 list2。
2. 按照上述方法，在list1 和 list2中再分别选flag，将list2 和 list2 分别拆成两个list，依次类推
3. 直到n = 1，即每个子list都只有一个元素整个过程 : n/2x = 1x = log2n
那么如何实现step1呢，既然有的元素比flag大，有的元素比flag小，那么我们定义两个游标，一个指向大于flag的元素，一个指向小于flag的元素，选定list中的最后一个元素作为flag
list =
（整个过程，可以在纸上先写一写，分析一下就很清楚了）
在上面的列表中，选择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和flag，在例子中，现在j=0，list < flag，这时候 i= i+1， exchange list 和 list的值
Q：现在 i 和 j 指向的都是0的位置，为什么自己要和自己交换呢？
A：可以在代码中看到，这样做其实是为了保持程序的一致性，当然你也可以自己判断，如果i 和 j 指向的都是同一个位置，那没必要交换
Step3：j++，到了j=（index）3的时候，这时候 i 还是指向（index）2的，发现，list = 8 是大于flag的，那么，i 原地不动 ，即现在i 还是指向index=2的位置，i 不往前走了。
Step4：当 j 走到5的时候，list = 4，它小于flag ，而它前面的8 和 9 都比flag大，那么，也肯定比list = 4要大了，好，i+1，即 i 现在指向（index）3，即value=8，exchange list 和 list，然后j 继续向前走。
总之，j 先走，只要碰到小于flag的数，i 就+1，只要碰到大于flag的数，i 就原地不动，j 继续向前走，目前就是把后面小的数给挪到前面来。
现在，来解释一下为什么将i 初始化到 -1 的位置呢？
很简单，当第一个位置的元素大于flag时，i 指向0，原地不动，而j 继续向前走，当遇到下面一个比flag小的元素时，i+1，那么，你就永远处理不到第一个元素了，嗯，就是这个原因，可以自己在纸上写一下，一下子就看出来了。
上面的过程可以用下面的代码实现;
1 if __name__ == '__main__':
2 l =
3
4 def first_sort(l):
5 flag = l[-1]
6 i = -1
7 for j in range(len(l)-1):
8 if l > flag:
9 pass
10 else:
11 i += 1
12 tmp = l
13 l = l
14 l = tmp
15 print(l)
16 print("\n" + "*"*20 + "\n")
17
18 tmp = l[-1]
19 l[-1] = l
20 l = tmp
21
22 print(l)
23 print("\n" + "*"*20 + "\n")
24
25 first_sort(l)
运行后的结果为：
********************
********************
从第一个打印出的list来看，小于flag的和大于flag的已经分开了
将list[-1] 和 list 交换，那么第一次快排就完成了，（运行结果的第二条）
清楚了这个过程以后，接下来就是递归的事儿了，呃，不想写了，好累。。。直接贴代码。
1 def path_sort(list,start_index,end_index):
2 flag = list
3 i = start_index - 1
4 for j in range(start_index,end_index):
5 if list > flag:
6 pass
7 else:
8 i += 1
9 tmp = list
10 list = list
11 list = tmp
12 tmp = l
13 l = l
14 l = 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(∩_∩)O~
页:
[1]