大佬教程收集整理的这篇文章主要介绍了golang 版快速排序,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
快速排序作为经典算法,基本面试中都会遇到,今天记录一下。
1.非递归版,这里也是使用一个栈的模型(自己实现)来实现。需要注意的是interface转int需要断言。
package main import ( "container/list" "fmt" ) // Stack is stack type Stack struct { stack *list.List } func newStack() *Stack { list := list.New() return &Stack{list} } func (Stack *Stack) push(value interface{}) { Stack.stack.PushBACk(value) } func (Stack *Stack) pop() interface{} { e := Stack.stack.BACk() if e != nil { Stack.stack.Remove(E) return e.Value } return nil } func (Stack *Stack) isEmpty() bool { return Stack.stack.Len() == 0 } func main() { var nums = []int{4,1,89,18,10} quickSort(nums,len(nums)-1) fmt.Println(nums) } func quickSort(nums []int,low,high int) { stack := newStack() if low < high { stack.push(high) stack.push(low) for low < high { left,ok := stack.pop().(int) if !ok { break } right,ok := stack.pop().(int) if !ok { break } pivot := partition(nums,left,right) if left < pivot-1 { stack.push(pivot - 1) stack.push(left) } if right > pivot+1 { stack.push(right) stack.push(pivot + 1) } } } } func partition(nums []int,high int) int { pivotKey := nums[high] for low < high { for low < high && nums[low] < pivotKey { low++ } nums[low],nums[high] = nums[high],nums[low] for low < high && nums[high] > pivotKey { high-- } nums[low],nums[low] } return high }2.递归版
package main import "fmt" func main() { var nums = []int{4,10} quickSort(nums) fmt.Println(nums) } func quickSort(nums []int) { qSort(nums,len(nums)-1) } func qSort(nums []int,high int) { if low < high { pivot := partition(nums,high) qSort(nums,pivot-1) qSort(nums,pivot+1,high) } } func partition(nums []int,high int) int { pivotKey := nums[low] for low < high { for low < high && nums[high] > pivotKey { high-- } nums[low],nums[low] for low < high && nums[low] < pivotKey { low++ } nums[low],nums[low] } return low }
以上是大佬教程为你收集整理的golang 版快速排序全部内容,希望文章能够帮你解决golang 版快速排序所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。