基于快排求无序数组的第K大元素

package other_pratice

/**
* 怎么最快的求无序数组的第K大元素。
*
* Author:sxy
*/

//  我们知道快排的排序是从大到小，还是从小到大取决于分区那个函数是如何写的，本题是在数组中寻找第几大元素
//  所以需要在数组的大小的顺序要是从大到小
//  快速排序每次排序完找的 基准点即是第几大元素。
//  如果 如果count==基准点+1；则基准点即是第几大元素； 如果count<基准点+1，在左边找；  如果count>基准点+1大于在右边找。
func FindNMaxIndex(arr []int, count int) int {
	return findNMaxIndex(arr, count, 0, len(arr)-1)
}

func findNMaxIndex(arr []int, count, start, end int) int {
	pivot := partition(arr, start, end)
	if pivot+1 == count {
		return arr[pivot]
	} else if pivot+1 > count {
		return findNMaxIndex(arr, count, start, pivot-1)
	} else {
		return findNMaxIndex(arr, count, pivot+1, end)
	}
}

// 如此排序的是数组的的数据是从大到小的。
func partition(arr []int, start, end int) int {
	// 选取最后一位当对比数字
	pivot := arr[end]

	var i = start
	for j := start; j < end; j++ {
		if arr[j] > pivot {
			if !(i == j) {
				// 交换位置
				arr[i], arr[j] = arr[j], arr[i]
			}
			i++
		}
	}
	arr[i], arr[end] = arr[end], arr[i]
	return i
}

测试

package other_pratice
import (
	"fmt"
	"testing"
)

func  TestFindNMaxIndex(t *testing.T){

	//arr:=[]int{1,3,2,0}
	arr1:=[]int{4, 2, 5, 12, 3 }
	res:=FindNMaxIndex(arr1,3)
	fmt.Println(res)
}

output: 第3k大元素

=== RUN   TestFindNMaxIndex
4
--- PASS: TestFindNMaxIndex (0.00s)
PASS

Process finished with exit code 0