# Golang每日一练(leetDay0111) 摆动排序II\I Wiggle Sort

### 324. 摆动排序 II Wiggle Sort ii

• 1 <= nums.length <= 5 * 10^4
• 0 <= nums[i] <= 5000
• 题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

package main
import "fmt"
func wiggleSort(nums []int) {
n := len(nums)
if n <= 1 {
return
}
heapSort(nums)
mid := n / 2
if n%2 == 0 {
mid--
}
temp := make([]int, n)
copy(temp, nums)
// 将较小的元素从末尾开始插入，较大的元素从中间位置开始插入
for i, j := 0, mid; i < n; i, j = i+2, j-1 {
nums[i] = temp[j]
}
for i, j := 1, n-1; i < n; i, j = i+2, j-1 {
nums[i] = temp[j]
}
}
// 堆排序
func heapSort(nums []int) {
n := len(nums)
// 建堆
for i := n/2 - 1; i >= 0; i-- {
}
// 排序
for i := n - 1; i > 0; i-- {
nums[0], nums[i] = nums[i], nums[0]
}
}
// 调整堆
func adjustHeap(nums []int, root, n int) {
for {
child := 2*root + 1
if child >= n {
break
}
if child+1 < n && nums[child+1] > nums[child] {
child++
}
if nums[child] > nums[root] {
nums[child], nums[root] = nums[root], nums[child]
}
root = child
}
}
func main() {
nums1 := []int{1, 5, 1, 1, 6, 4}
wiggleSort(nums1)
fmt.Println(nums1)
nums2 := []int{1, 3, 2, 2, 3, 1}
wiggleSort(nums2)
fmt.Println(nums2)
}

[1 6 1 5 1 4]

[2 3 1 3 1 2]

### 280. 摆动排序 I Wiggle Sort i

package main
import "fmt"
func wiggleSort(nums []int) {
n := len(nums)
findKthSmallest(nums, 0, n-1, n/2)
mid := nums[n/2]
i, j, k := 0, 0, n-1
for j <= k {
if nums[j] < mid {
nums[i], nums[j] = nums[j], nums[i]
i++
j++
} else if nums[j] > mid {
nums[j], nums[k] = nums[k], nums[j]
k--
} else {
j++
}
}
for i, j := 1, n-1; i < j; i, j = i+2, j-2 {
nums[i], nums[j] = nums[j], nums[i]
}
}
func findKthSmallest(nums []int, left, right, k int) {
if left == right {
return
}
pivot := partition(nums, left, right)
if k == pivot {
return
} else if k < pivot {
findKthSmallest(nums, left, pivot-1, k)
} else {
findKthSmallest(nums, pivot+1, right, k)
}
}
func partition(nums []int, left, right int) int {
pivot := nums[left]
for left < right {
for left < right && nums[right] >= pivot {
right--
}
nums[left] = nums[right]
for left < right && nums[left] <= pivot {
left++
}
nums[right] = nums[left]
}
nums[left] = pivot
return left
}
func main() {
nums := []int{3, 5, 2, 1, 6, 4}
wiggleSort(nums)
fmt.Println(nums)
}

[3 1 5 2 6 4]

## 🌟 每日一练刷题专栏 🌟

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

 （2023.5.16~）更新中... （2023.3.11~）更新中... （2023.2.18~2023.5.18）暂停更 （2023.2.18~2023.5.18）暂停更 （2023.3.11~2023.5.18）暂停更

|
3月前
|

59 0
|
2月前
|
Go
【golang】golang 字符串切片排序
【golang】golang 字符串切片排序
26 1
|
3月前
|
Go 索引
7天玩转 Golang 标准库之 sort
7天玩转 Golang 标准库之 sort
24 1
|
3月前
|

29 3
|
3月前
|
Linux 监控 Ubuntu
Linux 终端操作命令（1）
Linux 终端操作命令（1）
78 1
|
3月前
|
Shell Linux 算法
Shell编程——弱数据类型的脚本语言快速入门指南
Shell编程——弱数据类型的脚本语言快速入门指南
71 0
|
3月前
|
Linux 监控 Shell
38 0
|
3月前
|
Go Linux Shell
Linux 终端命令之文件浏览(2) more
Linux 终端命令之文件浏览(2) more
46 0
|
3月前
|
Shell Linux 机器学习/深度学习
Linux 终端操作命令（3）内部命令用法
Linux 终端操作命令（3）内部命令用法
57 0
|
3月前
|
Shell 机器学习/深度学习 Linux
Linux 终端操作命令（2）内部命令
Linux 终端操作命令（2）内部命令
36 0