快速排序
快速排序是一种高效的排序算法，它基于将数据列划分为更小的数组。比如将一个数组分割成两个更小的数据。然后重复对两个以上元素的数组进行排序，直到元素不可分割为止。
动画演示
image
逻辑描述
以数组最后一个元素作为分割基准（
pivot）。声明两个变量(
lo,hi)，指向最左、右元素，但是不包括基准位置。移动
lo位置找到大于，pivot的元素。移动
hi位置找到小于，pivot的元素。交换
lo和hi元素位置，并重复操作。当
lo>=hi,退出本次操作，从新寻找基准值。
代码实现
GO
package mainimport ( "fmt")func main() { //声明数组
numbers := []int{35, 33, 42, 10, 14, 19, 27, 44, 26, 31} //numbers := utils.GetRandSlices(10)
fmt.Printf("%v \n", numbers) //开始排序： 第一遍 左、右
QuickSort(0, len(numbers)-1, &numbers)
fmt.Printf("%v \n", numbers)
}func QuickSort(left, right int, numbers *[]int) { if right-left <= 0 { //数据已经不能再被分割。
return
} else {
pivot := (*numbers)[right] //找到基准元素
partIndex := Partition(left, right, pivot, numbers) //执行定位迁移操作。获取到基准原始交叉点。
//-----------------------------------------------------
//此时的数据已经由交叉点分割成左右两份。分别对左右的元素执行如此操作。
QuickSort(left, partIndex-1, numbers) //小于基准（左边）的元素，执行快速排序
QuickSort(partIndex+1, right, numbers) //大于基准（右边）的元素，执行快速排序
}
}func Partition(left, right, pivot int, numbers *[]int) int {
lo := left
hi := right - 1 //不包含基准元素位置
for { // 移动 `lo` 位置找到大于，`pivot` 的元素。
for (*numbers)[lo] < pivot {
lo++
} // 移动 `hi` 位置找到小于，`pivot` 的元素。
for hi > 0 && (*numbers)[hi] > pivot {
hi--
} //当移动的点交叉，本次迁移完成。退出
if lo >= hi { break
} else { //交换两个元素位置。
fmt.Printf(" 交换 :%d,%d\n", (*numbers)[lo], (*numbers)[hi])
(*numbers)[lo], (*numbers)[hi] = (*numbers)[hi], (*numbers)[lo]
}
} //当 `hi` 和 `lo` 交叉以后，数据已经通过 `pivot` 分割成左右两段。那么 `pivot` 就需要移动到交叉点的位置。
if lo != right {
fmt.Printf(" 交换 :%d,%d\n", (*numbers)[lo], (*numbers)[right])
(*numbers)[lo], (*numbers)[right] = (*numbers)[right], (*numbers)[lo]
} //返回交叉点。
return lo
}Python
# -*- coding: UTF-8 -*-numbers = [35, 33, 42, 10, 14, 19, 27, 44, 26, 31]
length = len(numbers)def quick_sort(left, right, nums):
if left >= right: return
else:
pivot = nums[right]
pivot_index = partition(left, right, pivot, nums)
quick_sort(left, pivot_index - 1, nums)
quick_sort(pivot_index + 1, right, nums)def partition(left, right, pivot, nums):
lo = left
hi = right - 1 # 不包含基准元素位置
while True: # 移动 `lo` 位置找到大于，`pivot` 的元素。
for i in range(lo, hi + 1):
lo = i if nums[i] > pivot: break
# 移动 `hi` 位置找到小于，`pivot` 的元素。
for j in range(hi, lo - 1, -1):
hi = j if nums[j] < pivot: break
# 当移动的点交叉，本次迁移完成。退出
if lo >= hi: break
else: # 交换两个元素位置。
print("交换:", nums[lo], nums[hi], "\n")
nums[lo], nums[hi] = nums[hi], nums[lo] # 当 `hi` 和 `lo` 交叉以后，数据已经通过 `pivot` 分割成左右两段。那么 `pivot` 就需要移动到交叉点的位置。
if lo != right:
print("交换:", nums[lo], nums[right], "\n")
nums[lo], nums[right] = nums[right], nums[lo] return lo
print("排序前:")
print(numbers)
quick_sort(0, length - 1, numbers)
print("排序后:", numbers)
作者：小码侠
链接：https://www.jianshu.com/p/7b7fe9eb671e