python的排序和查询

#encoding=utf-8
__author__ = ‘[email protected]‘

################# python自带的排序接口 #####################
# python内带非常强大的排序函数，sorted，或sort
# sorted是内建函数，sort是列表类的函数，它们都用法都是一样的，下面以sorted为例子
# 利用python的sorted函数进行排序，这个函数可以输入三个参数，key参数用于声明根据数据的哪一个部分进行排序，reversed参数
# 声明正序还是反序，cmp可以定义排序的规则
def sort_sorted_v1(sort_list):
    ‘‘‘
    利用data里面每一项的下划线分割后最后一项进行反序排序
    @data list 需要排序的数据
    这个函数如果输入 data=[‘ljxz_sa_100‘,‘ljxz_sa_78‘,‘ljxz_sa_910‘,‘ljxz_sa_90‘]
    会返回 [‘ljxz_sa_910‘, ‘ljxz_sa_100‘, ‘ljxz_sa_90‘, ‘ljxz_sa_78‘]
    ‘‘‘

    return sorted(sort_list, key=lambda x: int(x.split(‘_‘)[-1]), reverse=True)


def sort_sorted_v2(sort_list):
    ‘‘‘
    通过定义cmp参数，自定义排序的规则为按照数据的长度来排序
    @data list 需要排序的数据
    这个函数如果输入 data=[1, 8, ‘fefe‘, 678, 35, 4]
    会返回 [1, 8, 4, 35, 678, ‘fefe‘]
    ‘‘‘


    def my_cmp(x, y):
        f = lambda x: len(str(x))
        return cmp(f(x), f(y))

    return sorted(sort_list, cmp=lambda x, y: my_cmp(x, y))

################# 常规的排序方法 #####################
#1. 插入排序
def insertion_sorting(sort_list):
    sort_list_len = len(sort_list)
    if sort_list_len > 1:
        #从列表的第二个数开始遍历列表
        for i in range(1, sort_list_len):
            j = i - 1
            tmp_item = sort_list[i]
            #从i的位置开始，向左遍历列表，一旦有数比i对于的数大，就让这个大的数向后移动
            while j >= 0 and sort_list[j] > tmp_item:
                sort_list[j + 1] = sort_list[j]
                j -= 1
                #如果有数移动了，就在j+1的位置放入i对应的数
            if j != i - 1:
                sort_list[j + 1] = tmp_item
    return sort_list

#2. 冒泡排序
def bubble_sorting(sort_list):
    ‘‘‘
    通过比较相邻两个数的大小，大的移动到右边的方法，将左边i个数的最大的数移动到最右边，然后再将左边i-1个数的最大
    的数移动到最右边,依次类推。i开始为列表的长度
    ‘‘‘
    sort_list_len = len(sort_list)
    if sort_list_len > 1:
        for i in range(sort_list_len - 1):
            for j in range(sort_list_len - 1 - i):
                if sort_list[j] > sort_list[j + 1]:
                    sort_list[j], sort_list[j + 1] = sort_list[j + 1], sort_list[j]

    return sort_list

#2. 冒泡排序
def bubble_sorting1(sort_list):
    ‘‘‘
    通过比较相邻两个数的大小，大的移动到右边的方法，将左边i个数的最大的数移动到最右边，然后再将左边i-1个数的最大
    的数移动到最右边,依次类推。i开始为列表的长度
    ‘‘‘
    sort_list_len = len(sort_list)
    if sort_list_len > 1:
        i = sort_list_len
        while i > 1:
            for j in range(i - 1):
                if sort_list[j] > sort_list[j + 1]:
                    sort_list[j], sort_list[j + 1] = sort_list[j + 1], sort_list[j]
            i -= 1

    return sort_list

#3. 选择排序
def selection_sorting(sort_list):
    ‘‘‘

    ‘‘‘
    sort_list_len = len(sort_list)
    if sort_list_len > 1:
        for i in range(sort_list_len - 1):
            min_ = i
            #找到i后面（包括i）的所有数的最小值，跟i交换
            for j in range(i, sort_list_len):
                if sort_list[min_] > sort_list[j]:
                    min_ = j
            if min_ != i:
                sort_list[min_], sort_list[i] = sort_list[i], sort_list[min_]

    return sort_list

#快速排序
def quick_sorting(sort_list):
    ‘‘‘
    1.输入i和j，k等于下标为i的值，i为列表的开始下标，j为结束下标
    2.j依次减一，直到有sort_list[j]<k,就令sort_list[i] = sort_list[j]
    3.i依次加一，直到有sort_list[i]>k,就令sort_list[j] = sort_list[i]
    4.重复2,3,直到i和j相等，令sort_list[i]=k,这样k的位置就排好了，因为左边的都是比它小的，右边的都是比它大的
    5.把k左边的数和右边的数看成两个新的列表，对他们分别执行1,2,3,4，5步的操作，直到新的列表的长度都等于1

    ‘‘‘

    def _quick_sorting(i, j):
        if not j > i:
            return
        i_, j_ = i, j
        k = sort_list[i]
        while i != j:
            while i != j:
                if sort_list[j] < k:
                    sort_list[i] = sort_list[j]
                    break
                j -= 1
            while i != j:
                if sort_list[i] > k:
                    sort_list[j] = sort_list[i]
                    break
                i += 1
        sort_list[i] = k
        _quick_sorting(i_, i - 1)
        _quick_sorting(i + 1, j_)

    _quick_sorting(0, len(sort_list) - 1)
    return sort_list


if __name__ == ‘__main__‘:
    sort_list = [‘ljx_sa_100‘, ‘ljx_sa_78‘, ‘ljx_sa_910‘, ‘ljx_sa_90‘]
    print sort_sorted_v1(sort_list)

    sort_list = [1, 8, ‘fefe‘, 678, 35, 4]
    print sort_sorted_v2(sort_list)

    sort_list = [1, 8, 48, 678, 35, 4]
    print insertion_sorting(sort_list)

    sort_list = [1, 8, 48, 678, 35, 4]
    print bubble_sorting(sort_list)

    sort_list = [1, 8, 48, 678, 35, 4]
    print selection_sorting(sort_list)

    sort_list = [1, 8, 48, 678, 35, 4]
    print quick_sorting(sort_list)

#encoding=utf-8
__author__ = ‘Administrator‘

#############python内建查找函数##################
#1.index 这是python列表类自带的查找函数
def search_index(src, target):
    ‘‘‘
    @param src:list 查找的列表
    @param target: 查找的目标
    @return: 查找目标的下标
    ‘‘‘
    try:
        return src.index(target)
    except ValueError:
        return -1

#2.find 用于查找字符串的函数
def search_find(src, target):
    ‘‘‘

    @param src:str 查找的字符串
    @param target: 查找的目标
    @return: 查找目标的下标,如果查询不到，就返回-1
    ‘‘‘
    src.find(target)

#3.re python里面的正则模块，功能十分强大，实际开发中多用这种方法
def search_re(src, patt):
    ‘‘‘
    @param src:str 查找的字符串
    @param target: 正则表达式
    @return: 所有符合正则的结果的列表
    ‘‘‘
    import re

    return re.findall(patt, src)

################一般的查询算法####################
#1.顺序查询
def search_sequence(src, target):
    ‘‘‘
    @param src:list 查找的源列表
    @param target: 查找目标
    @return: 查找目标的下标,如果查询不到，就返回-1
    ‘‘‘
    for index, value in enumerate(src):
        if target == value:
            return index
    return -1

#2.二分法查询

def search_dichotomy(src, target):
    ‘‘‘
    @param src:list 查找的源列表，该列表需要排序好，而且是升序
    @param target: 查找目标
    @return: 查找目标的下标,如果查询不到，就返回-1
    ‘‘‘
    low = 0
    hight = len(src)
    while hight > low:
        mid = (low + hight) / 2
        if src[mid] == target:
            return target
        elif src[mid] < target:
            low = mid
        else:
            hight = mid
    return -1


if __name__ == ‘__main__‘:
    src = [1, 2, 3, 7, 9, 54, 666]
    print search_index(src, 554)

    src = ‘123486875‘
    print search_index(src, ‘48‘)

    src = ‘123486875‘
    print search_re(src, ‘48‘)

    src = [1, 2, 3, 7, 9, 54, 666]
    print search_sequence(src, 9)
    print search_dichotomy(src, 0)