快速排序和三路快排之Partition
本文总结自：慕课网 （作者：liuyubobobo ）
1. 快速排序
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。快速排序算法的思路是每次选择一个元素作为标的点（pivot），将整个数组的所有元素分为小于这个元素和大于这个元素两部分，之后再递归地对左右两部分分别进行这个过程，直至整个数组有序。
显然，在这个过程中，“选择一个元素作为标的点（pivot），将整个数组的所有元素分为小于这个元素和大于这个元素两部分”这步操作是最重要的，也是快速排序的核心所在。这个步骤被称为 Partition。通常将数组第一个元素作为pivot。
Partition算法实现步骤：
首先记录首位置元素，然后在后续依次便利过程中，希望总有以下过程，即<v和>v两部分。
我们利用j来代表分界点，即[l+1,j]区间和[j+1,i-1]区间分别满足条件。i为我们当前访问的元素。
那如何决定当前i的元素呢？分两种情况，即e>v或<=v。可见，如果e>v，那我们直接合并e在紫色区间，也就是说i直接右移。如果e<v呢？略复杂一点：我们要将e放到橙色的部分。下面是解释：将e与j后面的元素做交换，那e就加入了橙色，i的位置就仍是大于v的数。下面j右移，i继续右移即可。
最终情况如下：
那么我们只需要将l和j位置交换，就满足了该元素左面都小于它，右面都大于他。
基于以上，可以写出partition算法以及递归快速排序。
1 def paitition(arr): # pritition 2 if not arr: return None 3 v = arr[0] 4 j = 0 # [l+1,j]>v [j+1,i)>v
5 for i in range(len(arr)): 6 if arr[i]<v: # 当前元素小于v则交换 7 arr[j+1],arr[i] = arr[i],arr[j+1] 8 j=j+1
9 arr[0],arr[j] = arr[j],arr[0] # 最后将该首位元素pivot交换到合理位置 10 return j,arr 11
12
13 def quicksort(arr): # 快速排序 14 if len(arr)<=1:return arr # 如果小于2个元素则直接返回 15
16 index,arr = paitition(arr) # 找到pivot元素和位置 17 arr[0:index] = quicksort(arr[0:index]) # 排序pivot左半部分 18 arr[index+1:len(arr)] = quicksort(arr[index+1:len(arr)]) # 排序pivot元素右部分 19
20 return arr 21
22
23 print(quicksort([0,1,2,0,3,2,4,2,402,0])) # 测试快排
如何写出这段简介的partition代码？
在写代码之前，要考虑清楚具体边界情况： [l+1,j]>v， [j+1,i)>v。然后根据一般情况写代码即可。每次定义一个变量，就要考虑清楚其具体作用，例如变量j就负责使得[l+1，j]满足元素都小于v。而i是当前情况，[j+1,i)是左闭又开区间。
快速排序的问题：
当数组元素有非常多的重复元素时，快速排序会沦为非常可怕的O(n^3)复杂度。前面没有提到=v的情况，都是<v的放左边，>v的放右边。可是当有大量重复元素时，快速排序就会变得非常不平衡，<=v的部分很多，或者>=v的部分很多。如下图：
改进：三路快排。将=v的部分单独拿出来，将<v和>v的部分分别置于数组两端。
