[Go] Golang练习项目-快速排序的GO语言实现
2023-02-18 15:36:28 时间
快速排序首先选一个基准(你也可以认为是要放到排序后数组正确位置的元素)pivot,然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有很多种,所以快速排序具有很多版本。
总是选择第一个元素作为基准 pivot;
总是选择最后一个元素作为基准;(本文后续的实现就是依次为例)
随机的选择一个元素作为基准;
选择最中间的元素作为基准;
快速排序的关键是划分 partion() 。每一趟划分,我们就可以将作为 pivot 的值 x 放到排序数组的正确位置,并且将所有比 x 小的放到 x 的左边,所有比 x 大的元素放到 x 的右边。
package tools //划分 func partition(arr *[]int,left int,right int)int{ privot:=(*arr)[right] i:=left-1 for j:=left;j<right;j++{ if (*arr)[j]<privot{ i++ temp:=(*arr)[i] (*arr)[i]=(*arr)[j] (*arr)[j]=temp } } temp:=(*arr)[i+1] (*arr)[i+1]=(*arr)[right] (*arr)[right]=temp return i+1 } //递归 func QuickSort(arr *[]int,left int,right int){ if left>= right{ return } privot:=partition(arr,left,right) QuickSort(arr,left,privot-1) QuickSort(arr,privot+1,right) }
测试用例:
package tools import ( "testing" ) func TestQuickSort(t *testing.T) { arr:=[]int{1,8,3,9,4,5,4,7} t.Log(arr) QuickSort(&arr,0,len(arr)-1) t.Log(arr) }
go test -v sorts_test.go sorts.go
文章转载自公众号(景寓)
相关文章
- C/C++ 反汇编:函数与结构体
- C/C++ 反汇编:分析类的实现原理
- C/C++ 常用开发代码片段
- C/C++ Qt 编译打包项目
- C/C++ 常用排序算法整理
- C/C++ 操作数组与指针笔记
- C/C++ 结构体与指针笔记
- C/C++ 文件与指针操作笔记
- C/C++ 字符串拷贝处理
- C/C++ 命名空间引用知识
- C/C++ 类与构造析构等知识
- C/C++ 关于运算符重载笔记
- C/C++ 提权与强制卸载DLL
- C/C++ 实现LyDebug动态PE调试器
- C/C++ Npcap包实现数据嗅探
- C/C++ 常用加解密算法收集
- C/C++ 内存遍历与KMP特征搜索
- C/C++ 内存转储与获取DLL加载
- Git分支理解
- git ssh