测开面试 | Python常问算法

1、排序

从小到大排序：sorted(list)
从大到小排序：sorted(list, reverse=True)
sort() 方法，改变原有数组的顺序
sort(reverse=True)

#!/bin/Python

alist = [1, 4, 2, 3, 7, 6]

print(sorted(alist))

print(sorted(alist, reverse=True))

alist.sort()

print(alist)

alist.sort(reverse=True)

print(alist)

2、冒泡

1.比较相邻的元素，如果第一个比第二个大，就交换
2.一轮遍历，每两个相邻的元素，重复第 1 步，最大的放队尾
3.不包括已经排队尾的，重复第 2 步

#!/bin/Python

# -*- coding: UTF-8 -*-

#冒泡排序

def bubble_sort(lists):

    #获取数组长度

    count = len(lists) - 1

    #N个元素遍历N次

    for index in range(count, 0, -1):

        #第i个和i+1个依次对比

        for sub_index in range(index):

            #大的元素冒上去

            if lists[sub_index] > lists[sub_index + 1]:

                lists[sub_index], lists[sub_index + 1] = lists[sub_index + 1], lists[sub_index]

    return lists

alist = [1, 4, 2, 3, 7, 6]

print(bubble_sort(alist))

3、快排

1.从列表中挑出一个元素，作为基准值 key
2.所有小于 key 的元素放左边，所有大于 key 的元素放右边
3.分别递归左侧列表，右侧列表

#!/bin/Python

# -*- coding: UTF-8 -*-

#快速排序

def quick_sort(lists, left, right):

    #递归过程中，发现left和right一致时，停止递归，直接返回列表

    if left >= right:

        return lists

    #定义游标

    low = left

    high = right

    #取参考标志，最左边的元素

    key = lists[low]

    while low < high:

        #从最右侧向左，依次和标志元素对比，如果右侧的元素大于等于标志元素

        while low < high and lists[high] >= key:

            #右侧减1

            high -= 1

        #如果右侧的元素小于标志元素，则low赋high值

        lists[low] = lists[high]

        #从最左侧向右，依次和标志元素对比，如果左侧的元素小于等于标志元素

        while low < high and lists[low] <= key:

            #左侧加1

            low += 1

        #如果左侧的元素大于标志元素，则high赋low值

        lists[high] = lists[low]

    #最后给high位置赋值

    lists[high] = key

    #处理左侧元素

    quick_sort(lists, left, low - 1)

    #处理右侧元素

    quick_sort(lists, low + 1, right)

    return lists

alist = [0, 10, 88, 19, 9, 1, 7]

print(quick_sort(alist, 0, 6))

4、堆排序

堆排序指利用堆的数据结构设计的一种排序算法
堆近似于一个完全二叉树结构
子节点的键值小于（或者大于）它的父节点

#!/bin/Python

# -*- coding: UTF-8 -*-

#堆排序

def heap_sort(lst):

    def sift_down(start, end):

        """最大堆调整"""

        root = start

        print "root %d start %d end %d" % (root, start, end)

        while True:

            child = 2 * root + 1

            #print "child index: %d" % child

            #终止条件，孩子的索引值超过数组最大长度

            if child > end:

                break

            #print "lst child value: %d" % lst[child]

            #确定最大的孩子节点的索引值

            if child + 1 <= end and lst[child] < lst[child + 1]:

                child += 1

                #print "child+1 index: %d" % child

            #孩子节点最大值和根节点交换

            if lst[root] < lst[child]:

                lst[root], lst[child] = lst[child], lst[root]

                #print "lstroot %d" %d lst[root], "lstchild %d" % lst[child]

                root = child

                #print "root %d" % root

            else:

                break

    print("---------------创建最大堆---------------")

    #创建最大堆

    print(xrange((len(lst) - 2) // 2, -1, -1))

    for start in xrange((len(lst) - 2) // 2, -1, -1):

        print "---->Loop start %d" % start

        sift_down(start, len(lst) - 1)

        print(lst)

    print("---------------排序过程---------------")

    #堆排序

    for end in xrange(len(lst) - 1, 0, -1):

        #首尾交换

        lst[0], lst[end] = lst[end], lst[0]

        #剩余重新堆排序

        sift_down(0, end - 1)

        print(lst)

    return lst

alist = [70, 60, 12, 40, 30, 8, 10]

print(heap_sort(alist))

5、二分查找

二分查找又称折半查找
必须采用顺序存储结构
必须按关键字大小有序排列

#!/bin/Python

# -*- coding: UTF-8 -*-

#二分查找

#原始数组

alist = [0, 1, 10, 88, 19, 9, 1]

def binary_search(arr, start, end, hkey):

    if start > end:

        #返回-1,表示程序出现异常

        return -1

    #先找到数组索引的中间值

    mid = start + (end - start) / 2

    #如果中间值大于查找的值，则从中间值左边的数组中查找

    if arr[mid] > hkey:

        return binary_search(arr, start, mid - 1, hkey)

    #如果中间值小于查找的值，则从中间值右边的数组中查找

    if arr[mid] < hkey:

        return binary_search(arr, mid + 1, end, hkey)

    #返回查找的值所在的索引值

    return mid

#给数组排序

alist = sorted(alist)

#打印出排序后的数组

print(alist)

#执行程序

print binary_search(alist, 0, 6, 9)

6、素数

素数又称质数
0，1 不是素数
除了 1 和它本身外，不能被其他自然数整除的数

#!/bin/Python

# -*- coding: UTF-8 -*-

#素数

def is_prime(n):

    #0，1 不是素数

    if n <= 1:

        return False

    #除了 1 和它本身外，不能被其他自然数整除的数

    for i in range(2, n):

        if n % i == 0:

            return False

    return True

for i in range(0, 100):

    if is_prime(i):

        print i

欢迎关注微信公众号"测试开发Stack"

巴特西

测开面试 | Python常问算法

最新文章

热门文章