Golang 排序

215. 数组中的第K个最大元素

1、使用sort源码

func findKthLargest(nums []int, k int) int {
 sort.Ints(nums)
 //fmt.Println()
 return nums[len(nums)-k]
}

2、冒泡排序

func bubble_sort(nums []int) []int {
 for i:=len(nums)-1; i >=0; 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 findKthLargest(nums []int, k int) int {
 sortnums:= bubble_sort(nums)
 return sortnums[k-1]
}

3、选择排序

对比n后面所有数,将最大的和n交换来确定n位置的值

func findKthLargest(nums []int, k int) int {
 for j := 0; j <= len(nums)-1; j++ {
 max := nums[j]
 tag := 0
 for i:=j+1; i<len(nums); i++{
 if max < nums[i] {
 max = nums[i]
 tag = i
 }
 }
 if tag != 0 {
 nums[j], nums[tag] = nums[tag], nums[j]
 // 排到k时直接返回
 if j+1 == k {
 return nums[k-1]
 }
 }
 }
 return nums[k-1]
}

方法四:插入排序

func insertSort(nums []int, k int) int {
 for i:= 1; i < len(nums); i++ {
 insertNum := nums[i]
 j:=i-1
 for j>=0 && nums[j] < insertNum{
 nums[j+1] = nums[j]
 j--
 }
 if j + 1 != i{
 nums[j+1] = insertNum
 }
 }
 return nums[k-1]
}

方法五:快速排序

func QuickSort(left, right int, nums []int) []int {
 l := left
 r := right
 pivot := nums[(l+r)/2]
 for l < r {
 for nums[l] > pivot{
 l++
 }
 for nums[r] < pivot {
 r--
 }
 if l >= r {
 break
 }
 nums[l], nums[r] = nums[r], nums[l]
 //fmt.Println(nums)
 if nums[l] == pivot {
 r--
 }
 if nums[r] == pivot {
 l++
 }
 }
 if l == r {
 l++
 r--
 }
 if left < r{
 QuickSort(left, r, nums)
 }
 if right > l {
 QuickSort(l, right, nums)
 }
 return nums
}
func findKthLargest(nums []int, k int)int {
 // 方法五:快速排序
 return QuickSort(0 , len(nums)-1, nums)[k-1]
}

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传