集中常见的排序方法Go语言版本实现

这篇具有很好参考价值的文章主要介绍了集中常见的排序方法Go语言版本实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

简单排序:插入排序、选择排序、
冒泡排序 分治排序:快速排序、归并排序
分配排序:桶排序、基数排序
树状排序:堆排序
其他:计数排序、希尔排序

稳定排序:如果 a 原本在 b 的前面,且 a == b,排序之后 a 仍然在 b 的前面,则为稳定排序。
非稳定排序:如果 a 原本在 b 的前面,且 a == b,排序之后 a 可能不在 b 的前面,则为非稳定排序。
原地排序:原地排序就是指在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
非原地排序:需要利用额外的数组来辅助排序。
时间复杂度:一个算法执行所消耗的时间。
空间复杂度:运行完一个算法所需的内存大小。

/**  insertSort   * 插入排序法     * @param arr     * @return     */
func insertSort(arr []int) {
	//	//判断数组是否为空或者长度是否大于2
	if len(arr) < 2 {
		return
	}
	//循环遍历数组
	for i := 1; i < len(arr); i++ {
		//定义变量保存要插入的值
		tem := arr[i]
		k := i - 1
		for k >= 0 && arr[k] > tem {
			arr[k+1] = arr[k]
			k--
		}
		//元素插入
		arr[k+1] = tem
	}
	return
}

// selectSort 选择排序 时间复杂度可能很高
func selectSort(arr []int) {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		m := i
		for j := i + 1; j < n; j++ {
			if arr[m] > arr[j] {
				m = j
			}
		}
		//交换
		temp := arr[i]
		arr[i] = arr[m]
		arr[m] = temp
	}
}

// bubbleSort 冒泡排序算法
func bubbleSort(arr []int) {
	if len(arr) < 2 {
		return
	}
	flag := true
	//加一个标志位,记录上一次是否发生了交换,如果是,我们则进行下一轮,如果没有,说明已经冒泡好了
	for i := 1; i < len(arr) && flag; i++ {
		//控制次数,第几趟排序,只需要n-1趟,有交换时进行,只有flag=false就说明上一次一个元素都没有进行交换
		flag = false
		//假定未交换
		for j := 0; j < len(arr)-i; j++ {
			if arr[j] > arr[j+1] {
				temp := arr[j]
				arr[j] = arr[j+1]
				arr[j+1] = temp
				flag = true
			}
		}
	}
}

// quickSort 快速排序算法
func quickSort(arr []int, left, right int) []int {
	if left < right {
		//获取基点元素所处的位置
		mid := partition(arr, left, right)
		//进行分割
		arr = quickSort(arr, left, mid-1)
		arr = quickSort(arr, mid+1, right)
	}
	return arr
}
func partition(arr []int, left, right int) int {
	//选取基点元素
	pivot := arr[left]
	i := left + 1
	j := right
	for {
		// 向右找到第一个小于等于 pivot 的元素位置
		for i <= j && arr[i] <= pivot {
			i++
		}
		// 向左找到第一个大于等于 pivot 的元素位置
		for i <= j && arr[j] >= pivot {
			j--
		}
		if i >= j {
			break
		}
		//交换两个元素的位置,使得左边的元素不大于pivot,右边的不小于pivot
		temp := arr[i]
		arr[i] = arr[j]
		arr[j] = temp
	}
	arr[left] = arr[j]
	// 使中轴元素处于有序的位置
	arr[j] = pivot
	return j
}

// 堆排序
func heapSort(arr []int) {
	//1.构建大顶堆
	for i := len(arr)/2 - 1; i >= 0; i-- {
		//从第一个非叶子结点从下至上,从右至左调整结构
		sift(arr, i, len(arr))
	}
	//2.调整堆结构+交换堆顶元素与末尾元素
	for i := len(arr) - 1; i > 0; i-- {
		//现在的数组第一个就是根结点,最小值所在,进行交换,把它放到最右边
		temp := arr[i]
		arr[i] = arr[0]
		arr[0] = temp
		//重新建立堆
		sift(arr, 0, i)
		//重新对堆进行调整
	}
}

/**
 建立堆的方法
 私有方法,只允许被堆排序调用
 @param arr     要排序数组
 @param parent  当前的双亲节点
 @param len     数组长度
 */
func sift(arr []int, parent, len int) {
	value := arr[parent]
	//先取出当前元素i
	for child := 2*parent + 1; child < len; child = child*2 + 1 {
		//从parent结点的左子结点开始,也就是2*parent+1处开始
		if child+1 < len && (arr[child] < arr[child+1]) {
			//如果左子结点小于右子结点,child指向右子结点
			child++
			//右孩子如果比左孩子大,我们就将现在的孩子换到右孩子
		}
		//判断是否符合大顶堆的特性, 如果右孩子大于双亲,自然左孩子也大于双亲,符合
		//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
		if value < arr[child] {
			arr[parent] = arr[child]
			parent = child
		} else {
			//如果不是,说明已经符合我们的要求了。
			break
		}
	}
	arr[parent] = value
	//将value值放到最终的位置
}

附个二分查找算法文章来源地址https://www.toymoban.com/news/detail-815238.html

func Search(n int, f func(int) bool) int {
	// Define f(-1) == false and f(n) == true.
	// Invariant: f(i-1) == false, f(j) == true.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if !f(h) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
	return i
}

到了这里,关于集中常见的排序方法Go语言版本实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Go 实现选择排序算法及优化

    选择排序是一种简单的比较排序算法,它的算法思路是首先从数组中寻找最小(大)的元素,然后放到数组中的第一位,接下来继续从未排序的元素中寻找最小(大)元素,然后放到已排序元素的末尾,依次类推,直到所有元素被排序。 执行结果: 升序排序。 使用 i 变量表

    2024年02月08日
    浏览(39)
  • 数据结构(C语言实现)——常见排序算法的基本思想及实现(快速排序的三种方法和优化及非递归实现快速排序)

    生活中几乎处处都会用到排序,比如:网购时的店铺顺序,学生成绩的排名等,今天我们就来学习数据结构中常见的几种排序算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列

    2023年04月24日
    浏览(60)
  • 掌握Go语言:探索Go语言递归函数的高级奥秘,优化性能、实现并发、解决算法难题(28)

    递归函数在Go语言中是一种强大的工具,能够解决许多复杂的问题。除了基本的递归用法外,Go语言还提供了一些高级用法,使得递归函数更加灵活和强大。本文将深入探讨Go语言递归函数的高级用法,包括尾递归优化、并发递归和记忆化递归等。 尾递归优化 尾递归是一种特

    2024年04月10日
    浏览(50)
  • 初识Go语言25-数据结构与算法【堆、Trie树、用go中的list与map实现LRU算法、用go语言中的map和堆实现超时缓存】

      堆是一棵二叉树。大根堆即任意节点的值都大于等于其子节点。反之为小根堆。   用数组来表示堆,下标为 i 的结点的父结点下标为(i-1)/2,其左右子结点分别为 (2i + 1)、(2i + 2)。 构建堆   每当有元素调整下来时,要对以它为父节点的三角形区域进行调整。 插入元素

    2024年02月12日
    浏览(57)
  • 1 Go语言开发环境搭建详细教程+go常见bug合集【Go语言教程】

    官网地址:golang.org,因为一些原因国内可能无法访问。可以使用下面第二个链接。 国内地址访问:https://golang.google.cn/dl或者https://www.golangtc.com/download 根据自己操作系统版本,下载安装即可,目录尽量选择全英文且没有空格和其他其他特殊字符。 2.1 Windows下 GOPATH:即默认的w

    2024年02月05日
    浏览(45)
  • 源码分享-go语言实现的祖冲之ZUC加密算法

    源码路径:free5gc/nas/security/zuc zuc.go zuc_test.go

    2024年02月16日
    浏览(33)
  • GO语言实现区块链POW共识算法- -区块定义与数据串行化

    持续创作,加速成长!这是我参与「掘金日新计划 · 6 月更文挑战」的第9天,点击查看活动详情 区块链分布式系统,共识算法系统是它的灵魂,pow也就是工作量证明,证明你做过一定量的工作。(按劳分配,拼算力) 在我们实现pow之前,需要对区块链的基本架子先搭起来(相当

    2024年02月08日
    浏览(38)
  • 源码分享-go语言实现的snow3g加密算法

    源码路径:free5gc/nas/security/snow3g snow3g.go snow3g_test.go

    2024年02月16日
    浏览(35)
  • go 语言常见问题(2)

    无,recover 必须在 defer 函数中运行。recover 捕获的是祖父级调用时的异常,直接调用时无效。 直接 defer 调用也是无效。 defer 调用时多层嵌套依然无效。 必须在 defer 函数中直接调用才有效。 在每轮迭代中生成一个局部变量 i 。如果没有 i := i 这行,将会打印同一个变量。 或

    2024年01月24日
    浏览(40)
  • Go 1.19 排序算法

    插入排序是一种简单直观的排序算法,它的基本思想是将待排序的元素插入到已经排好序的序列中,从而得到一个新的有序序列。插入排序的具体过程如下: 从第一个元素开始,认为它已经是有序的序列。 取出下一个元素,在已经排序的序列中从后向前扫描。 如果已经排序

    2024年02月07日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包