go实现随机快速排序

最新推荐文章于 2024-04-26 20:34:52 发布

ceshell

最新推荐文章于 2024-04-26 20:34:52 发布

阅读量222

点赞数

分类专栏： go 文章标签： go 随机快速排序

本文链接：https://blog.csdn.net/ceshell/article/details/100833219

版权

go 专栏收录该内容

8 篇文章

订阅专栏

本文详细介绍了如何使用Go语言实现随机化快速排序算法，包括排序原理、代码实现及性能分析，帮助读者理解并掌握这一高效排序技巧。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func swap(arr []int, i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}

func partition(arr []int, left, right, key int) []int { // 划分
	less := left - 1  // 小于区
	more := right + 1 // 大于区
	index := left     // 下标
	for index < more {
		if arr[index] < key { // 小于划分值，就放到小于区
			swap(arr, less+1, index)
			less++  // 扩大小于区
			index++ // 比较下一个值
		} else if arr[index] > key { // 大于划分值，就放到大于区
			swap(arr, more-1, index)
			more-- // 扩大大于区；索引位置不变（因为当前值已经改变，需要再次比较）
		} else {
			index++ // 相同时，比较下一个数
		}
	}
	// 返回等于区的位置
	return []int{less + 1, more - 1}
}

func randInt(left, right int) int { //生成随机数
	rand.Seed(time.Now().UnixNano())
	// 生成[left, right]闭区间内的随机数
	return rand.Intn(right-left+1) + left 
}

func RandomQuickSort(arr []int, left, right int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	if left < right {
		//选取随机数
		key := randInt(left, right) //随机选择一个数组下标
		fmt.Println("随机数key = ", key)
		key = arr[key] //取出随机划分值
		fmt.Println("数组值key = ", key)
		part := partition(arr, left, right, key) //随机选择一个数组中的数作为划分值
		RandomQuickSort(arr, left, part[0]-1)
		RandomQuickSort(arr, part[1]+1, right)
	}
}

func main() {
	arr := []int{3, 1, 2, 23, 8}	
	fmt.Println("排序前：", arr)
	RandomQuickSort(arr, 0, len(arr)-1)	
	fmt.Println("排序后：", arr)
}