# 每日一题 【每日一题】实现快速排序-Python-20210829

Jack · 2021年08月29日 · 最后由 lework 回复于 2021年12月15日 · 48 次阅读

``````tmp_list = [8, 5, 1, 3, 2, 10, 11, 4, 12, 20]
def partition(arr,low,high):
i = ( low-1 )
pivot = arr[high]
for j in range(low , high):
if   arr[j] <= pivot:
i = i+1
arr[i],arr[j] = arr[j],arr[i]

arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )

def quicksort(arr,low,high):
if low < high:
pi = partition(arr,low,high)
quicksort(arr, low, pi-1)
quicksort(arr, pi+1, high)

quicksort(tmp_list, 0, len(tmp_list)-1)
print(tmp_list)
``````
``````package main

import "fmt"

func quickSort(arr []int, low, height int){

if low >= height {
return // 当 low = height  时跳出
}

left, right := low, height
pivot := arr[(low+height)/2] // 取中间数做对比

for left <= right {
// 从左边开始迭代

// 左边的数如果比 pivot 小，那么就应该将他放在左边，继续向右滑动，遇到一个比他大的为止
for arr[left] < pivot {
left++
}

// 右边的数如果比 pivot 大，那么就应该将他放在右边，继续向左滑动，遇到一个比他小的为止
for arr[right] > pivot {
right--
}

// 这里进行一次交换，将上面碰到的大数和小数交换一次
// left 继续右走，right 继续左走 注意这里还不一定相遇，去继续执行上面的逻辑
if left <= right {
arr[left], arr[right] = arr[right], arr[left]
left++
right--
}
}
quickSort(arr, low, right)
quickSort(arr, left, height)
}

func main() {
/*
实现快速排序
快速排序：分治法+递归实现
随意取一个值A，将比A大的放在A的右边，比A小的放在A的左边；然后在左边的值AA中再取一个值B，将AA中比B小的值放在B的左边，将比B大的值放在B的右边。以此类推
*/

testArr := []int{2, 5, 3, 7, 4, 5, 8, 1, 4, 0}
quickSort(testArr, 0, len(testArr)-1)
fmt.Println(testArr)
}
``````