使用Golang实现排序算法

冒泡排序

func bubblesort(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		for j := 0; j < i; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
	return nums
}

插入排序

func insertsort(nums []int) []int {
	for i := 1; i < len(nums); i++ {
		if nums[i] <= nums[i-1] {
			j := i
			for nums[j] < nums[j-1] {
				nums[j], nums[j-1] = nums[j-1], nums[j]
				j--
				if j == 0 {
					break
				}
				fmt.Println(nums)
			}
		}
	}
	return nums
}

选择排序

func selectsort(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		temp := i
		for j := i; j < len(nums); j++ {
			if nums[j] < nums[temp] {
				temp = j
			}
		}
		nums[temp], nums[i] = nums[i], nums[temp]
	}
	return nums
}

归并排序

func mergeort(nums []int) []int {
	if len(nums) > 1 {
		mid := len(nums) / 2
		left := mergeort(nums[:mid])
		right := mergeort(nums[mid:])
		temp := []int{}
		for i, j := 0, 0; i < len(left) && j < len(right); {
			if left[i] < right[j] {
				temp = append(temp, left[i])
				i++
				if i == len(left) {
					temp = append(temp, right[j:]...)
					break
				}
			} else {
				temp = append(temp, right[j])
				j++
				if j == len(right) {
					temp = append(temp, left[i:]...)
					break
				}
			}
		}
		return temp
	}
	return nums
}

显然,这个归并排序每次递归都会创建新的切片,空间占用直接爆炸

为了解决这个问题,下面的快速排序是在原有的切片上操作,使得空间占用大大降低

快速排序

func quicksort(nums []int, left, right int) []int {
	if left >= right {
		return nums
	}
	i, j := left, right
	privot := nums[i]
	for i < j {
		for i < j && nums[j] >= privot {
			j--
		}
		nums[i] = nums[j]
		for i < j && nums[i] <= privot {
			i++
		}
		nums[j] = nums[i]
	}
	nums[i] = privot
	quicksort(nums, left, i-1)
	quicksort(nums, i+1, right)
	return nums
}
当前文章: 《使用Golang实现排序算法》
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇