python实现排序算法四：BFPTR算法

所谓的BFPTR算法就是从n个数中寻找最小的K个数，主要思想可以参考注释，写得不是很好，特别是寻找中位数的中位数的时候，欢迎指正：

采用任意排序算法，将分组后的数据进行排序：

__author__ = 'liu'
#coding = utf-8

'''
BFPTR排序

采用任意排序算法，将分组后的数据进行排序
这里采用插入排序算法，比如10个数，则low = 0, high = 10
'''
def insertsort(a, low, high):
        for i in range(low + 1, high):
                j = i
                while j > 0 and a[j] < a[j - 1]:
                        a[j], a[j - 1] = a[j - 1], a[j]
                        j -= 1
'''
分治法，可参考快速排序，将快速排序里的key值由a[low]变为指定的索引值a[keyIdx]
为了得到将原始数据分为两部分的值对应的索引
'''
def Partion(a, low, high, keyIdx):
        a[low],a[keyIdx] = a[keyIdx],a[low]
        i = low
        j = high
        key = a[low]
        while i < j:
                while a[j] >= key and i < j:
                        j -= 1
                if i < j:
                        a[i] = a[j]
                        i += 1
                        while a[i] <= key and i < j:
                                i += 1
                        if i < j:
                                a[j] = a[i]
                                j -= 1
        a[i] = key
        return i

'''
根据给定的值，获取该指定值的索引
'''
def findIdx(a, low, high, num):
        for i in range(low,high):
                if a[i] == num:
                        return i
        return -1
'''
假设原数组有n个元素，则以5个元素为一组进行分组，最后得到n/5 + 1组
最后一组可能不满5个元素
这里是获取每个分组的中位数
然后对n/5 + 1个中位数再获取中位数
'''
def findMidNum(a, low, high):
        midNum = []
        temp = 0
        if low == high - 1:
                return a[low]
        for i in range(low, high - 5, 5):
                insertsort(a, i, i + 5)
                temp = i
                midNum.append(a[i + 2])
        num = high - temp
        if num > 0:
                insertsort(a, temp, temp + num)
                midNum.append(a[int(num / 2)])
        n = int(high / 5) + 1
        insertsort(midNum, 0, n)
        return midNum[int(n/2)]

def BFPTR(a, low, high, k):
        num = findMidNum(a, low, high)
        keyIdx = findIdx(a, low, high, num)
        i = Partion(a, low, high - 1, keyIdx)
        m = i - low + 1
        if m == k:
                return a[i]
        if m > k:
                return BFPTR(a, low, i - 1, k)
        return BFPTR(a, i + 1, high, k - m)