python查找第k小元素代码分享

代码如下:

# -*- coding: utf-8 -*-

from random import randint
from math import ceil, floor

def _partition(A, l, r, i):
    """以A[i]为主元划分数组A[l..r],使得:
    A[l..m-1] <= A[m] < A[m+1..r]
    """
    A[i], A[r] = A[r], A[i] # i交换到末位r,作为主元
    pivot = A[r] # 主元
    m = l # 索引标记
    for n in xrange(l, r): # l..r-1
        if A[n] <= pivot:
            A[m], A[n] = A[n], A[m] # 交换
            m += 1 # 后移
    A[m], A[r] = A[r], A[m] # 主元到m位
    return m

def _rand(A, l, r):
    """随机划分主元"""
    return randint(l, r) # A[l..r]随机取一个

def _select(A, l, r, k, pivot_selector = _rand):
    """利用快排,得A[l..r]中第k小的数,k in [l+1,r+1]:

其尾递归方式,伪码如下:
    SELECT(A, l, r, k)
    1  while true:
    2    i ← ? // 划分主元位置
    3    m ← PARTITION(A, l, r, i) // 数组划分
    4    n ← m - l + 1 // A[l..m]元素个数
    5    if k = n // 检查A[m]是否是第k小的元素
    6      then return A[m]
    7    elseif k < n // 左划分区
    8      r = m - 1
    9    else // 右划分区
    10     k = k - n
    11     l = m + 1

Args:
        pivot_selector(Function): 主元选取方法,默认随机方式
    """
    if not A:
        return None
    if l == r:
        return A[l]
    while True:
        i = pivot_selector(A, l, r)
        m = _partition(A, l, r, i)
        n = m - l + 1
        if k == n:
            return A[m]
        elif k < n:
            r = m - 1
        else:
            k = k - n
            l = m + 1

def rand_select(A, k):
    """默认随机划分主元方式,k in [1, len(A)]
    E[T(n)] = O(n)
    """
    return _select(A, 0, len(A) - 1, k);

def _median(A, l, r):
    """对A[l..r]插入排序(原地)后选取其中位数位置"""
    for j in xrange(l, r + 1):
        k = A[j]
        i = j
        while i > l and A[i-1] > k:
            A[i] = A[i-1]
            i -= 1
        A[i] = k
    return l + int((r - l) * 0.5) # 下中位数

def _medianOfMedians(A, l, r):
    """中位数的中位数方式:
    1. 划分为floor(n/5)个5元组,剩下(n%5)组成最后一组。
    2. 找出ceil(n/5)个组各自的中位数。先对每组插入排序,再从中选出中位数。
    3. 对第2步中找出的ceil(n/5)个中位数重复上述操作,直到仅有一个中位数。
    """
    if l == r:
        return l
    n = r - l + 1 # 元素个数
    m = int(ceil(n / 5.0)) # 划分组数,每组5个元素
    for i in xrange(m):
        # 每组起始位和结束位
        sub_l = l + i * 5
        sub_r = sub_l + 4
        if sub_r > r:
            sub_r = r
        # 对每组元素插入排序后,选取中位数
        sub_m = _median(A, sub_l, sub_r) # 中位数索引
        # 交换中位数到前几位
        j = l + i
        A[j], A[sub_m] = A[sub_m], A[j]
    return _medianOfMedians(A, l, l + m - 1) # 中位数的中位数

def bfprt_select(A, k):
    """中位数的中位数方式(BFPRT算法)
    T(n) = O(n)
    """
    return _select(A, 0, len(A) - 1, k, _medianOfMedians);

def _median3(A, l, r):
    """三数中位数方式,取l,r,(l+r)/2三数中位数"""
    c = (l + r) / 2
    keys = [l, c, r]
    i = _median(keys, 0, 2)
    return keys[i]

def median_select(A, k):
    """三数中位数方式,以消除最坏情况"""
    return _select(A, 0, len(A) - 1, k, _median3);

if __name__ == '__main__':
    import random, time
    from copy import copy

print('preparing data...')
    n = 1000000
    nums = range(n)
    random.shuffle(nums)
    print('ready go!')

def timeit(fnc, *args, **kargs):
        print('%s starts processing' % fnc.__name__)
        begtime = time.clock()
        retval = fnc(*args, **kargs)
        endtime = time.clock()
        print('%s takes time : %f' % (fnc.__name__, endtime - begtime))
        return retval

test_methods = [rand_select, bfprt_select, median_select]
    k = random.randrange(n) + 1
    dashes = '---' * 10
    for test in test_methods:
        print(dashes)
        nums_new = copy(nums)
        result = timeit(test, nums_new, k)
        print('the %dth smallest element: %d' % (k, result))

(0)

相关推荐

  • python 查找文件夹下所有文件 实现代码

    复制代码 代码如下: def find_file_by_pattern(pattern='.*', base=".", circle=True): '''''查找给定文件夹下面所有 ''' re_file = re.compile(pattern) if base == ".": base = os.getcwd() final_file_list = [] print base cur_list = os.listdir(base) for item in cur

  • python快速查找算法应用实例

    本文实例讲述了Python快速查找算法的应用,分享给大家供大家参考. 具体实现方法如下: import random def partition(list_object,start,end): random_choice = start #random.choice(range(start,end+1)) #把这里的start改成random()效率会更高些 x = list_object[random_choice] i = start j = end while True: while li

  • Python查找相似单词的方法

    本文实例讲述了Python查找相似单词的方法.分享给大家供大家参考.具体分析如下: 问题: 给你一个单词a,如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的兄弟单词.现在给你一个字典,用户输入一个单词,让你根据字典找出这个单词有多少个兄弟单词. Python代码如下: from itertools import tee,izip from collections import defaultdict def pairwise(iterable): a, b = tee(iter

  • Python 字符串操作实现代码(截取/替换/查找/分割)

    Python 截取字符串使用 变量[头下标:尾下标],就可以截取相应的字符串,其中下标是从0开始算起,可以是正数或负数,下标可以为空表示取到头或尾. 复制代码 代码如下: # 例1:字符串截取str = '12345678'print str[0:1]>> 1   # 输出str位置0开始到位置1以前的字符print str[1:6]  >> 23456   # 输出str位置1开始到位置6以前的字符num = 18str = '0000' + str(num) # 合并字符串pr

  • Python中的二叉树查找算法模块使用指南

    python中的二叉树模块内容: BinaryTree:非平衡二叉树  AVLTree:平衡的AVL树  RBTree:平衡的红黑树 以上是用python写的,相面的模块是用c写的,并且可以做为Cython的包. FastBinaryTree  FastAVLTree  FastRBTree 特别需要说明的是:树往往要比python内置的dict类慢一些,但是它中的所有数据都是按照某个关键词进行排序的,故在某些情况下是必须使用的. 安装和使用 安装方法 安装环境: ubuntu12.04, py

  • python实现在目录中查找指定文件的方法

    本文实例讲述了python实现在目录中查找指定文件的方法.分享给大家供大家参考.具体实现方法如下: 1. 模糊查找 复制代码 代码如下: import os from glob import glob #用到了这个模块 def search_file(pattern, search_path=os.environ['PATH'], pathsep=os.pathsep):     for path in search_path.split(os.pathsep):         for mat

  • python中查找excel某一列的重复数据 剔除之后打印

    1.在python中excel的简单读写操作,推荐使用xlrd(特别是读操作) 2.到http://pypi.python.org/pypi/xlrd 去下载 xlrd库: 3.工程代码如下: 复制代码 代码如下: import xlrd def open_excel(fileName="simple.xls"):          try:              fileHandler = xlrd.open_workbook(fileName)              ret

  • python脚本实现查找webshell的方法

    本文讲述了一个python查找 webshell脚本的代码,除了查找webshell功能之外还具有白名单功能,以及发现恶意代码发送邮件报警等功能,感兴趣的朋友可以自己测试一下看看效果. 具体的功能代码如下: #!/usr/bin/env python #-*- coding: utf-8 -*- import os import sys import re import smtplib #设定邮件 fromaddr = "smtp.qq.com" toaddrs = ["vo

  • python查找第k小元素代码分享

    复制代码 代码如下: # -*- coding: utf-8 -*- from random import randintfrom math import ceil, floor def _partition(A, l, r, i):    """以A[i]为主元划分数组A[l..r],使得:    A[l..m-1] <= A[m] < A[m+1..r]    """    A[i], A[r] = A[r], A[i] # i交

  • 在Python web中实现验证码图片代码分享

    系统版本: CentOS 7.4 Python版本: Python 3.6.1 在现在的WEB中,为了防止爬虫类程序提交表单,图片验证码是最常见也是最简单的应对方法之一. 1.验证码图片的生成   在python中,图片验证码一般用PIL或者Pillow库实现,下面就是利用Pillow生成图片验证码的代码: #!/usr/bin/env python3 #- * -coding: utf - 8 - * -#@Author: Yang#@ Time: 2017 / 11 / 06 1: 04 i

  • python将数据插入数据库的代码分享

    python将数据插入数据库的方法: 首先读入数据并建立数据库连接: 然后创建数据库: 接着执行插入数据语句,迭代读取每行数据: 最后关闭数据库连接即可. 比如现在我们要将如下Excel数据表格插入到MySQL数据库中,该如何实现呢? 实现代码: #导入需要使用到的数据模块 import pandas as pd import pymysql #读入数据 filepath = 'E:\_DataSet\catering_sale.xls' data = pd.read_excel(filepat

  • c++实现扫雷小游戏代码分享

    分成两个源文件和一个头文件 注意:这串代码并不完整,不能够实现当所查坐标周围雷的数量为0时,直接展开周围坐标: 头文件:game.h #include <stdio.h> #define count 10 //雷的数量 //定义 行-ROW,列-COL #define ROW 9 #define COL 9 #define ROWS ROW+2 //多加一些,方便代码 #define COLS COL+2 //初始化棋盘,声明的函数均在game.c中实现 void InitBoard(char

  • 利用Python实现绘制3D爱心的代码分享

    目录 环境介绍 第一步,绘制一个三维的爱心 亿点点细节 加入时间序列 加入心脏的跳动 一个好的展示 完整代码 环境介绍 python3.8 numpy matplotlib 第一步,绘制一个三维的爱心 关于这一步,我采用的是大佬博客中的最后一种绘制方法.当然,根据我的代码习惯,我还是稍做了一点点修改的. class Guess: def __init__(self, bbox=(-1.5, 1.5), resolution=50, lines=20) -> None: ""&qu

  • python绘制铅球的运行轨迹代码分享

    我们按照面向过程程序设计的思想,使用python编写了程序,追踪铅球在运行过程中的位置信息.下面,修改程序代码,导入turtle模块,将铅球的运行轨迹绘制出来. python3代码如下: from math import pi, sin, cos, radians from turtle import Turtle def main(): angle = eval(input('Enter the launch angle(in degrees):')) vel = eval(input('En

  • Python numpy生成矩阵、串联矩阵代码分享

    import numpy 生成numpy矩阵的几个相关函数: numpy.array() numpy.zeros() numpy.ones() numpy.eye() 串联生成numpy矩阵的几个相关函数: numpy.array() numpy.row_stack() numpy.column_stack() numpy.reshape() >>> import numpy >>> numpy.eye(3) array([[ 1., 0., 0.], [ 0., 1.

  • Python中pygal绘制雷达图代码分享

    pygal的安装和简介,大家可以参阅<pip和pygal的安装实例教程>,下面看看通过pygal实现绘制雷达图代码示例. 雷达图(Radar): import pygal radar_chart = pygal.Radar() radar_chart.title = 'V8 benchmark results' radar_chart.x_labels = ['Richards', 'DeltaBlue', 'Crypto', 'RayTrace', 'EarleyBoyer', 'RegEx

  • Python学习pygal绘制线图代码分享

    pygal的安装大家可以参阅:pip和pygal的安装实例教程 线图: import pygal line_chart = pygal.Line() line_chart.title = 'Browser usage evolution (in %)' line_chart.x_labels = map(str, range(2002, 2013)) line_chart.add('Firefox', [None, None, 0, 16.6, 25, 31, 36.4, 45.5, 46.3,

  • python英语单词测试小程序代码实例

    这篇文章主要介绍了python英语单词测试小程序代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 爬取了扇贝英语网,并制作了一个英语单词测试的小程序,还能生成错词本,一起来看下代码吧- import requests #扇贝网爬虫,获取英语单词 category_res=requests.get('https://www.shanbay.com/api/v1/vocabtest/category/?_=1566889802182') ca

随机推荐