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

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-- {
    adjustHeap(nums, i, n)
  }
  // 排序
  for i := n - 1; i > 0; i-- {
    nums[0], nums[i] = nums[i], nums[0]
    adjustHeap(nums, 0, i)
  }
}
// 调整堆
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)
}

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)
}