Go实现快速选择算法

àì夳堔傛蜴生んèń 2023-10-04 15:39 28阅读 0赞

快速选择算法用于查找元素，当列表进行排序时，该元素将位于 Kth 位置，而无需实际排序整个列表。快速选择与快速排序非常相似，可以代替对整个列表进行排序，我们只是忽略快速排序每一步列表的一半，只关注我们感兴趣的列表区域。

package main
    
    import (
    	"fmt"
    )
    
    func QuickSelect(arr []int, key int) int {
    
    	size := len(arr)
    
    	QuickSelectUtil(arr, 0, size-1, key)
    
    	return arr[key-1]
    
    }
    
    func QuickSelectUtil(arr []int, lower int, upper int, key int) {
    
    	if upper <= lower {
    
    		return
    
    	}
    
    	pivot := arr[lower]
    
    	start := lower
    
    	stop := upper
    
    	for lower < upper {
    
    		for arr[lower] <= pivot && lower < upper {
    
    			lower++
    
    		}
    
    		for arr[upper] > pivot && lower <= upper {
    
    			upper--
    
    		}
    
    		if lower < upper {
    
    			swap(arr, upper, lower)
    
    		}
    
    	}
    
    	swap(arr, upper, start) // upper is the pivot position
    
    	QuickSelectUtil(arr, start, upper-1, key) // pivot -1 is the upper for left sub array.
    
    	QuickSelectUtil(arr, upper+1, stop, key) // pivot + 1 is the lower for right sub array.
    
    }
    
    func swap(arr []int, first int, second int) {
    
    	arr[first], arr[second] = arr[second], arr[first]
    
    }
    
    func main() {
    
    	data := []int{9, 1, 8, 2, 7, 3, 6, 4, 5}
    
    	fmt.Println(QuickSelect(data, 5))
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，28人围观）

还没有评论，来说两句吧...

相关阅读

相关快速排序/快速选择算法

目录一.快速排序 1.基本介绍 2.基本思路 1.关于中轴值的选择 2.小数组情形 3.时间复杂度 3.代码实现 1.随机值分割 2.三数中值分割法 2.

你的名字/ 2024年03月25日 09:30/ 0 赞/ 135 阅读

相关【算法】快速选择算法

目录 1.概述 2.代码实现 2.1.基于简单交换排序 2.2.基于堆排序 2.3.基于快速排序 3.应用 >

ゞ浴缸里的玫瑰/ 2024年02月17日 10:44/ 0 赞/ 28 阅读

相关 Go实现快速选择算法

快速选择算法用于查找元素，当列表进行排序时，该元素将位于 Kth 位置，而无需实际排序整个列表。快速选择与快速排序非常相似，可以代替对整个列表进行排序，我们只是忽略快速排序每一

àì夳堔傛蜴生んèń/ 2023年10月04日 15:39/ 0 赞/ 29 阅读

相关 Go实现快速排序算法

package main import ( "fmt" ) func QuickSort(arr []int) {

喜欢ヅ旅行/ 2023年10月04日 15:39/ 0 赞/ 93 阅读

相关 Go-实现选择排序算法

算法描述：从未排序数据中选择最大或者最小的值和当前值交换 O(n^2) 。算法步骤： 1. 选择一个数当最小值或者最大值，进行比较然后交换。 2.

「爱情、让人受尽委屈。」/ 2022年09月03日 00:14/ 0 赞/ 272 阅读

相关 Go-实现快速排序算法

算法描述如下：快速排序算法是对插入算法的一种优化，它主要是利用对问题的二分化，通过实现递归，完成快速排序。在所有算法中二分化是最常用的方式，我们可以将问题尽

红太狼/ 2022年09月02日 15:49/ 0 赞/ 278 阅读

相关快速选择算法

快速选择算法是基于快速排序算法的，目的是寻找一个无序表内的第k大（小）的元素。快速排序：快速排序的原理是把每次一个无序表以一个目标节点为中心，向左放比它

╰+攻爆jí腚メ/ 2022年07月11日 12:11/ 0 赞/ 267 阅读

相关 Go语言编程：Go语言实现快速排序算法

前言今天用Go语言实现下经典排序算法——快速排序算法。主要是学习了Go语言，得用它来干点事情嘛，就用快速排序来练手。在Go语言语法方面，主要用到切片数组，for循环（

男娘i/ 2022年05月27日 00:57/ 0 赞/ 427 阅读

相关 go实现选择排序算法

前面我们讲解了[选择排序算法][Link 1]，现在我们用go语言实现代码如下 package main import "fmt"

迈不过友情╰/ 2022年05月14日 01:09/ 0 赞/ 269 阅读

相关 go 实现选择排序

一点睛选择式排序属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，经过和其他元素重整，再依原则交换位置后达到排序的目的。二选择排序思想选择排

超、凢脫俗/ 2021年07月24日 20:07/ 0 赞/ 600 阅读