go 非递归版本快速排序

letterbeezps · · 826 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

# 非递归版本快速排序,go实现 ## 使用栈来接收中间参数 ## CODE ```go package main import "fmt" func main() { arrs := []int{3,5,2,5,7,1,3,5,25,2,15} // arrs := []int{3,5,2,5,7} fmt.Printf("before arr: %v\n", arrs) quick_sort(arrs, 0, len(arrs)-1) fmt.Printf("after arr: %v\n", arrs) } func partition(arr []int, l int, r int) int { var i, j int = l-1, r+1 var mid int = (l + r) / 2 x := arr[mid] for i < j { i ++ for arr[i] < x { i ++ } j -- for arr[j] > x { j -- } if i < j { arr[i], arr[j] = arr[j], arr[i] } } return j } func quick_sort(arr []int, l int, r int) { if r<=0 || l >= r { return } stack := []int{} i := 0 j := 0 stack = append(stack, r) stack = append(stack, l) for len(stack) > 0 { i = stack[len(stack)-1] stack = stack[: len(stack) - 1] j = stack[len(stack)-1] stack = stack[: len(stack) - 1] if i < j { k := partition(arr, i, j) if k > i { stack = append(stack, k) stack = append(stack, i) } if k < j { stack = append(stack, j) stack = append(stack, k+1) } } } } ``` ## 效果 before arr: [3 5 2 5 7 1 3 5 25 2 15] after arr: [1 2 2 3 3 5 5 5 7 15 25]

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

826 次点击  ∙  1 赞  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传