快速排序作为经典的排序算法，使用场景很多。比如寻找数组中第K大的数。
虽然核心思想一致，但是不同的快速排序写法，细节还是不同，一不小心就会搞错。这里给的代码，是相对简洁好记的。
快速排序属于拿着元素找位置的算法。思路非常简单明了，首先给第一个元素找到它正确的位置并把它放置其中，此时该元素将原数组分为两半，左半边的元素都小于或等于它，右半边的元素都大于它，对这两个子数组重复刚才的操作，直到子数组中只有一个元素，此时排序完成。
首先，我们用一个forInsert变量存储数组第一个位置上的元素的值。可以通俗理解为我们将第一个位置上的元素“挖”了出来，以便为它找到合适的位置，第一个位置此时已经是“空”的，位置是空的这一概念很关键，后面会用到。
如何为该元素找到合适的位置呢？答案是先确定该元素所在位置的范围，不断缩小该范围，直到该范围是一个确定的位置，查找结束，把forInsert的值放到该位置上，再对该位置左右两个子数组进行迭代，直到子数组大小为1时结束，排序完成。
为表示该元素所在位置的范围，我们需要定义两个变量left,right，代表元素所在位置的范围的左端和右端，显然left的初始值应为0，right的初始值应为N-1。
下面开始缩小这一范围，将right位置上的元素与forInsert进行比较，如果大于forInsert,那么可以断定right这个位置肯定不是forInsert应当在的位置，因为如果将forInsert放置在right位置上，该位置上原来的元素将无处安放。
所以我们可以将right减1(right–)，这就缩小了位置的范围，然后我们继续将新的right位置上的元素与forInsert比较，如果还是大于forInsert,则可以继续将right减1后继续比较，直到right位置上的值小于forInsert的值时，就是magic发生的地方。
由于right位置上的元素比forInsert小，我们无法判断该位置是否是forInsert应当在的位置，BTW,我们可以判定left这个位置肯定不是forInsert应当在的位置，为什么？请参照上文叙述自行理解。
然后呢？我们可以将right位置上的值放置到left位置上，让left加1(left++),这进一步缩小了位置的范围。
此时right位置我们认为是“空的”了，看到没，刚才left是空的，现在right是空的了。
下步的思路肯定还是想办法继续缩小位置的范围。我们可以将left位置上的元素与forInsert比较，如果小于forInsert的值，我们可以断定，left这个位置肯定不是forInsert应当在的位置。
为啥？因为将forInsert放置到该位置上，该位置上的元素只能往左边挪，而左边每个位置上都是比forInsert小的元素导致“无处可挪”，矛盾出现，反证结束。然后我们又可以放心地将left加1了，位置范围又一次缩小。
我们继续将left位置上的元素与forInsert比较，直到发现left位置上的元素大于forInsert时，又要有magic发生了，我们将left位置上的元素放置到right位置上(还记得right位置此时是空的吗？)，现在，left位置变成空的了，由于此时right位置上的元素是大于forInsert的，right位置肯定不是forInsert应当在的位置，所以我们要将right减1，进一步缩小待确定位置的范围。
现在，left增加了一些值，并且left位置此时是空的，right减少了一些值，整体上[left , right]包含的范围比初始时小了好多。如果left=right,我们知道，要找的位置就是现在left所指示的空位置，直接将forInsert放置到left位置上即可。然后开始左右两个子数组的迭代，如果left还是小于right,那我们只能继续进行缩小位置范围的工作，直到确定位置为止。
def quicksort(nums, l, r):
if l < r:
i = l, j=r, x=nums[l]
while i < j:
#循环开始的时候， s[i]位置是空的，
#所以下一次，一定是把某个值放在 s[i]上
while i < j and nums[j] >= x:
j -= 1
if i < j:
nums[i] = nums[j]
i += 1
#经过一个while循环后，s[j]是空的，
#所以下一次，一定是把某个值放在s[j]上
while i < j and nums[i] < x:
i += 1
if i < j:
nums[j] = nums[i]
j -= 1
# 循环结束后，i == j，直接将x放在该位置即可
s[i] = x
quicksort(nums, l, i-1)
quicksort(nums, i+1, r)