这个算法写了我好久，在这里记一下。
算法的原理是利用中位数来作为划分元素选择第M小的元素，中位数需要递归自身来求得。算法的最优，平均，最差时间复杂度都为O(N)。相对于随机算法改善了最差时间复杂度。
和快排用了同样的partition，但是这个算法所使用的pivot是确定的，即中位数。
代码版本为golang 1.8.0。
路径goWorkSpace/algorithms/worseLinearSelect.go
package algorithms
import (
"fmt"
)
func WorseLinearSelect(array []int, startIndex, stopIndex, rank int)(selectedValue int) {
if startIndex + 5 > stopIndex {
insertionSort(array)
return array[rank]
}
midValueArrays := getMidValueArray(array, startIndex, stopIndex)
midValue := WorseLinearSelect(midValueArrays, 0, len(midValueArrays), (len(midValueArrays) - 1)/2)
devideIndex := partitionWithPiovt(array, midValue)
if devideIndex == rank {
return array[devideIndex]
} else if devideIndex > rank {
return WorseLinearSelect(array, startIndex, devideIndex, rank)
} else {
return WorseLinearSelect(array, devideIndex + 1, stopIndex, rank)
}
}
//sort array by groups and return the mid value array
func getMidValueArray(array []int, startIndex, stopIndex int)(midValues []int) {
array = array[startIndex : stopIndex]
arrayGroups := len(array) / 5
if len(array) % 5 == 0 {
midValues = make([]int, arrayGroups)
} else {
midValues = make([]int, arrayGroups + 1)
}
//j := 0
for i, j := 0, 0; i < len(array); i += 5 {
if i + 5 <= len(array) {
b := array[i : i + 5]
insertionSort(b)
midValues[j] = array[i + 2]
} else {
insertionSort(array[i : len(array)])
midValues[j] = array[(i + len(array)) / 2]
}
//(i + 5 <= len(array)) ? (insertionSort(array[i : i + 5])) : (insertionSort(array[i : len(array)]))
j ++
}
return midValues
}
func partitionWithPiovt(array []int, pivotValue int)(firstIndex int) {
firstIndex = -1
for secondIndex := 0; secondIndex != len(array); secondIndex ++ {
if array[secondIndex] < pivotValue {
firstIndex ++
swap(&array[firstIndex], &array[secondIndex])
} else if array[secondIndex] == pivotValue {
firstIndex ++
swap(&array[firstIndex], &array[secondIndex])
swap(&array[0], &array[firstIndex])
}
}
swap(&array[0], &array[firstIndex])
return firstIndex
}
func insertionSort(array []int) {
defer func() {
if r := recover(); r != nil {
fmt.Println(r)
}
}()
for i := 1; i != len(array); i++ {
selectValue := array[i]
for j := i - 1; j >= 0; j -- {
if array[j] > selectValue {
swap(&array[j], &array[j + 1])
} else {
break
}
}
}
}
func swap(a *int, b *int) {
temp := *b
*b = *a
*a = temp
}
func Partition(array []int, pivotValue int) int {
return partitionWithPiovt(array, pivotValue)
}
main包路径goWorkSpace/golangTest/test.go，测试代码如下：
package main
import (
"fmt"
"algorithms"
"sort"
"time"
"math/rand"
)
func main() {
//to new a random slice
rand.Seed(time.Now().UnixNano())
arrayLen := rand.Intn(400) + 200
array := make([]int, arrayLen)
for index, _ := range array {
array[index] = rand.Intn(5 * arrayLen)
fmt.Print(",", array[index])
}
rank := rand.Intn(arrayLen)
fmt.Println("array befor select\n", array)
fmt.Println("rank", rank)
fmt.Println("array length", arrayLen)
//run the select function
selectedValue := algorithms.WorseLinearSelect(array[:], 0, len(array), rank)
sort.Ints(array[:])
fmt.Println("\nselectedValue by sort", array[rank])
fmt.Println("\nselectedValue", selectedValue)
}
后来发现代码还有小缺陷，partition方法会影响到切片中不需要重新划分的部分，但不影响算法的复杂度，只是多了一点无意义的操作。
代码对于所有测试用例都能通过。