快排应该算是比较有趣的一种排序算法了。
#Ps：反正我觉的蛮有趣的
话不多说，还是先上代码：
- # 升序
- def quitSort(arr,left,right):
- if left >= right:
- return arr
- init_left = left
- init_right = right
- key = arr[left]
- while left < right:
- while left < right and arr[right] >= key:
- right -= 1
- arr[left] = arr[right]
- while left < right and arr[left] <= key:
- left += 1
- arr[right] = arr[left]
- arr[left]=key
- quitSort(arr,init_left,left-1)
- quitSort(arr,left+1,init_right)
- return arr
-
- # 降序
- def quitSort(arr,left,right):
- if left >= right:
- return arr
-
- init_left = left
- init_right = right
- key = arr[right]
-
- while left < right:
- while left < right and arr[left]>=key:
- left+=1
- arr[right]=arr[left]
- while left < right and arr[right]<=key:
- right -= 1
- arr[left] = arr[right]
- arr[right] = key
- quitSort(arr,init_left,left-1)
- quitSort(arr,right+1,init_right)
- return arr
e，先放上菜鸟教程的快排gif：
快排的原理就在于 设定一个中间值 ，在我的代码中，key 就是中间值（下面都用 key 来代替中间值）
快排过程：
- 快排的本质就是 分而治之 ，也就是说以 key 为准，对两边的数据进行一个整理，比如：大于 key 的值往 key 的右边扔，小于 key 的往左边挪，至于等于 key 的值往左往右都行。（如上图）
- 接着我们确定一个 key ，一般是数组最左或最右边的值（这里我们设置为最左边的值，也就是 key = arr[ left ] ）
- 既然 key 是最左边的值，那么我们要先判断右边（以升序为例）：
- 右边的指针（right）一开始指向最右边（ len(arr-1) ），只要指针指向的值大于 key ，指针就向左挪一个位置（因为要让 key 左边的值都比 key 大），这样，我们就能找到第一个 小于 key 的值，并将值赋给 left 指向的位置，如下图与下下图。
#Ps：这是原始数组： left 指向 5 ，right 指向 4
#Ps：这是左边第一次循环结束后的数组： left 指向 4 ，right 指向 4
- 同时，由于我们在函数开始就存储了 arr[left] 的值，也就是 key ，所以我们并不用担心会出现数据丢失的情况。
- 因为左边第一次循环已经结束了，接下来就是右边的第一次循环，第一次判断：4 < 5（ arr[left]<key ），满足条件，left 指针向右挪一位 指向8，8> key ，将 8 赋值给 right 指向的位置
#Ps：left 指向 8（第二位） ，right 指向 8（最后一位）
- 第二轮大循环开始：
- 还是右边先判断：8 > key ，满足条件，right 指针往左走一格 指向 3 ，3<key ，将3 赋值给 left 指向的位置
#Ps：left 指向 3 （第二位），right 指向 3（倒数第二位）
- 左边开始判断：一直到 6 停下来，left 指向 6，将 6 赋值给 right 指向的位置
#Ps：left 指向 6 （第五位），right 指向 6（第六位）
- 第三轮大循环开始：
- arr[ right] >key ，right 指针向左走，此时 left ，right 指向同一个位置，大循环结束。将 key 赋值给 left 和 right 指向的位置
#Ps：left 指向 5 ，right 指向 5
- 接着，我们以 key 为节点 分为 key 的左边 和 key 的右边 再进行以上的步骤。
最后附上 每一轮大循环结束后的数组 arr ：
本文到此结束，手动分割线。