算法（快速排序）算法：快速排序

快速排序

快速排序是一种高效的排序算法，它基于将数据列划分为更小的数组。比如将一个数组分割成两个更小的数据。然后重复对两个以上元素的数组进行排序，直到元素不可分割为止。

动画演示

文章图片
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 loprint("排序前:") print(numbers) quick_sort(0, length - 1, numbers) print("排序后:", numbers)

【算法（快速排序）】微信搜索：小码侠