介绍一种新的排序算法，快速排序。前面一片文章中介绍了归并排序，简单的说，归并排序是物理意义上的分治法，就是把前面几个位置（下标）上的元素看成一个子序列，后面几个位置（下标）上的元素看成一个子序列。然后再将每个子序列继续分而治之，直到每个子序列只有一个元素，这样作为有序序列向上归并。 那么这样做的时间复杂度为O(nlogn)，但是空间上需要多备份一份，作为新的序列，空间复杂度为O(n)，如果需要排序的数据集特别大，这时候就要仔细考虑一下了。 可以思考一种逻辑意义上的分治法，或者说是内容上的分治法。不是按照下标来分割序列，而是根据数值来分治，每次根据一个数将序列分割成两个子序列和这个数，一个子序列的元素全部比这个数小，另一个子序列，全部比这个数大，并将原始序列的元素位置按照分割的序列进行排列。然后再分别两个子序列继续分割，直到每个子序列只有一个元素。这样，每个子序列都是由“特殊的数”连接起来，这个”特殊的数”的左边都比它小，右边都比它大，所以整体上肯定是排好序的。这就是快速排序。其实简单的说就是找中间元素（或者说选取的元素）的位置。
那么这个特殊的数怎么选取呢？理想状态下肯定是选取的数就是整个序列的中间值，这样每次都是均分的。但是实际上这是不可能的，因为事先并不知道中间值到底是多少，而查找中间值也是有开销的。所以一般情况下是随机选取序列中的一个数，我们选取的是第一个元素。
接下来叙述一下快速排序的具体原理过程。
对于给定的一个待排序列，选取首元素作为分割序列的数值（也就是最终的序列中，首元素所在的位置的左面一定都是比首元素小的，右面一定都是比首元素大的）。然后分别从第二个元素起向后遍历和最后一个元素位置起向前遍历。向后遍历时，当遇到比首元素大的元素时，停止遍历。向前遍历时，当遇到比首元素小的元素时，停止遍历。注意在2和3步的过程中，一定要保证向后遍历的位置一定要在向前遍历的前面（或者说左面，即向后遍历的下标一定要小于向前遍历的下标，就像两个人过独木桥那样，一定要保证二者没有相遇）。没有相遇，说明二者还没有遍历完整个序列，也就是二者中间还有一定长度个数的元素，也就是还没有到达逻辑意义上的中点，也就是还没有到达首元素该有的位置。2和3都停止遍历时，判断是否符合4的规定，如果符合，就把两个停止遍历时的下标处的元素进行交换。因为符合的话，说明还没有遍历完，没有遍历完就说明此时向后遍历的元素一定全部都应该在左面，而左面不应该出现比首元素大的数，向前遍历同理。所以二者需要交换。如果不满足规定，说明二者已经交叉了，说明二者遍历经过的序列长度之和加起来已经超过了原始序列，所以必然是已经走过了中间元素的最终位置。那么此时到底哪个位置是呢？其实是向前遍历的下标。因为假设此时向前遍历到了一个元素a，向后遍历到了一个元素b，此时已经交叉且都停止遍历了，那么就是a比首元素小，b比首元素大。此时因为交叉，所以b在a的右面（下标）。那么如果首元素最终的位置是b，也就是和b交换，那么b就在首元素的起始位置（最开始），而最开始的位置又是在最左面，所以最终的结果就是首元素的左边出现了比首元素大的数，这显然是不符合规定的，也是排序不正确的。所以如何和a交换，原始a的右面一定都是比首元素大的，因为如果不大，就在a之前就停止遍历了。而a的左面一定是比首元素小的，因为因为如果不小，则在b的前面就停止遍历了。所以最终如果交叉的话，那么就是向前遍历的下标是最终首元素的位置。这样一轮遍历结束之后，实际上是找到了首元素的最终位置。那么接下来递归，分而治之即可。这是教程给的代码，还好吧。其实可以不用定义这么多函数的。
# 快速排序 def quick_sort(alist): quick_sort_helper(alist, 0, len(alist)-1) def quick_sort_helper(alist, first, last): if first < last: splitpoint = partition(alist, first, last) quick_sort_helper(alist, first, splitpoint-1) quick_sort_helper(alist, splitpoint + 1, last) def partition(alist, first, last): pivotvalue = alist[first] leftmark = first + 1 rightmark = last done = False while not done: while leftmark <= rightmark and alist[leftmark] <= pivotvalue: leftmark = leftmark + 1 while alist[rightmark] >= pivotvalue and rightmark >= leftmark: rightmark = rightmark - 1 if rightmark < leftmark: done = True else: temp = alist[leftmark] alist[leftmark] = alist[rightmark] alist[rightmark] = temp temp = alist[first] alist[first] = alist[rightmark] alist[rightmark] = temp return rightmark # alist = [54,26,93,17,77,31,44,55,20] # alist = [2, 1] # alist = [1] alist = [54,23,31,78] quick_sort(alist) print(alist)这是我写的代码，挺菜的。开始不太理解，对于长度为1和2的就特殊判别了一下。而且没有想到传递下标，把列表直接传进去了。
# 快速排序1 def quick_sort(alist): if len(alist) > 1: mid_value = alist[0] first = 1 last = len(alist) - 1 if first < last: while first < last: # 左边游标开始向右移动 if alist[first] <= mid_value: first += 1 else: # 左边找到了大于中间值的位置，即需要交换的位置。 # 右边下标开始向左移动 if alist[last] >= mid_value: last -= 1 else: # 右边找到了小于中间值的位置，即需要交换的位置。 # 交换 alist[first], alist[last] = alist[last], alist[first] alist[0], alist[first - 1] = alist[first - 1], alist[0] # print(alist[:first-1]) left = quick_sort(alist[:first-1]) right = quick_sort(alist[first:]) # 快排结束后，将左半部分，中间值，和右半部分三个合并为一个，注意extend语法 left.extend([alist[first-1]]) left.extend(right) return left else: if alist[0] <= alist[1]: return alist else: return alist[::-1] else: return alist lst = [1,26,93,17,77,31,44,55,20] # lst = [2,1] # lst = [3] print(quick_sort(lst))稍微改进了一下下，不用判别长度为2的了。
# 快速排序2 def quick_sort(alist): if len(alist) > 1: mid_value = alist[0] first = 1 last = len(alist) - 1 if first <= last: while first <= last: # 左边游标开始向右移动 if alist[first] <= mid_value: first += 1 else: # 左边找到了大于中间值的位置，即需要交换的位置。 # 右边下标开始向左移动 if alist[last] >= mid_value: last -= 1 else: # 右边找到了小于中间值的位置，即需要交换的位置。 # 交换 alist[first], alist[last] = alist[last], alist[first] alist[0], alist[first - 1] = alist[first - 1], alist[0] # print(alist[:first-1]) left = quick_sort(alist[:first-1]) right = quick_sort(alist[first:]) # 快排结束后，将左半部分，中间值，和右半部分三个合并为一个，注意extend语法 left.extend([alist[first-1]]) left.extend(right) return left else: return alist # lst = [1,26,93,17,77,31,44,55,20] lst = [1,2] # lst = [3] print(quick_sort(lst))大改了一下，传递下标，那这样参数就多了一点。
# 快速排序3 def quick_sort(alist, first, last): if first < last: # 中间值 mid_value = alist[first] # 左右游标 left = first + 1 right = last while left <= right: # print(left, right) # 左右游标分别移动 while left <= right and alist[left] <= mid_value: left += 1 while right >= left and alist[right] >= mid_value: # print(right) right -= 1 # 此时要么是左右游标相对左右位置发生改变（即左游标在右游标的右边），要么就是出现了要交换的元素 if left <= right: alist[left], alist[right] = alist[right], alist[left] else: break alist[first], alist[right] = alist[right], alist[first] # print(alist) quick_sort(alist, first, right-1) quick_sort(alist, right+1, last) # alist = [54,26,93,17,77,31,44,55,20] # alist = [2, 1] # alist = [1] alist = [54,23,31,78] quick_sort(alist, 0, len(alist)-1) print(alist)时间复杂度的话，这个就是O(nlogn)，和归并排序类似，分为分割和排序两部分，分割的话，划分到长度为1的时候就截止了，所以还是O(logn)（不过取决于初值中间值的选取，这个还不是很清楚），排序的话，就是前后同时遍历，遍历完就完事了，那就是O(n)了。感觉比归并排序容易理解一点哈哈哈。
