Python面试算法编程题（一）——查找&排序

参考：https://blog.csdn.net/u012505432/article/details/52071537

一、查找

1、二分法查找

# 实现一个二分查找
# 输入:一个顺序list（必须为有序数列），要查找的值
# 输出: 待查找的元素的位置
def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1

    while first <= last:
        mid = (first + last)//2
        print(mid)
        if alist[mid] > item:
            last = mid - 1
        elif alist[mid] < item:
            first = mid + 1
        else:
            #从第一个开始
            return mid+1
    return -1

test = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarySearch(test, 3))

递归：

def bin_search_rec(data_set, value, low, high):
    if low < high:
        mid = (low + high) // 2
        if data_set[mid] == value:
            return mid+1
        elif data_set[mid] > value:
            return bin_search_rec(data_set, value, low, mid - 1)
        else:
            return bin_search_rec(data_set, value, mid + 1, high)
    else:
        return None

二、排序

1、冒泡排序法

原理就是，列表相邻的两个数，如果前边的比后边的小，那么交换顺序，经过一次排序后，最大的数就到了列表最前面

class Solution:
    def bubbleSort(nums):
        # 这个循环负责设置冒泡排序进行的次数
        for i in range(len(nums)-1):  
            # ｊ为列表下标  
            for j in range(len(nums)-i-1):  
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
        return nums

时间复杂度是O(n2)

见：https://www.cnblogs.com/Apy-0816/p/11100265.html

存在一个最好情况就是列表本来就是排好序的，所以可以加一个优化，加一个标志位，如果没有出现交换顺序的情况，那就直接return 

高级冒泡排序（鸡尾酒排序/搅拌排序）

def bubble_sort(origin_items, comp=lambda x, y: x > y):
    """高质量冒泡排序(搅拌排序)"""
    items = origin_items[:]
    for i in range(len(items) - 1):
        swapped = False
        for j in range(i, len(items) - 1 - i):
            if comp(items[j], items[j + 1]):
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if swapped:
            swapped = False
            for j in range(len(items) - 2 - i, i, -1):
                if comp(items[j - 1], items[j]):
                    items[j], items[j - 1] = items[j - 1], items[j]
                    swapped = True
        if not swapped:
            break
    return items

2、插入排序

原理：把列表分为有序区和无序区两个部分。最初有序区只有一个元素。然后每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。

def insertionSort(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index

        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position-1]
            position -= 1
        alist[position] = currentvalue

时间复杂度是O(n2)

见：https://blog.csdn.net/qq_42857603/article/details/81605124

3、快速排序法

（1）

def quick_sort(b):
    """快速排序"""
    if len(b) < 2:
        return b
    # 选取基准，随便选哪个都可以，选中间的便于理解
    mid = b[len(b) // 2]
    # 定义基准值左右两个数列
    left, right = [], []
    # 从原始数组中移除基准值
    b.remove(mid)
    for item in b:
        # 大于基准值放右边
        if item >= mid:
            right.append(item)
        else:
            # 小于基准值放左边
            left.append(item)
    # 使用迭代进行比较
    return quick_sort(left) + [mid] + quick_sort(right)

（2）推荐

example = [1,3,4,5,2,6,9,7,8,0]
 
a = 0
b = len(example)-1
 
def quickSort(number,head,tail):
    if (head<tail):
        base = division(number,head,tail)
        #print(number[base],"\n")
        quickSort(number,head,base-1)
        quickSort(number,base+1,tail)
    else:
        print(number)
 
def division(number,head,tail):
    base = number[head]
    while(head<tail):
        while(head<tail and number[tail]>=base):
            tail-=1
        number[head] = number[tail]
        while (head<tail and  number[head]<=base):
            head+=1
        number[tail] = number[head]
    number[head] = base
    return head
 
 
 
if __name__ == '__main__':
    quickSort(example,a,b)

见：https://blog.csdn.net/qq_40941722/article/details/94396010

正常的情况，快排的复杂度是O(nlogn)

快排存在一个最坏情况，就是每次归位，都不能把列表分成两部分，此时复杂度就是O(n2)了，如果要避免设计成这种最坏情况，可以在取第一个数的时候不要取第一个了，而是取一个列表中的随机数

4、选择排序

原理：遍历列表一遍，拿到最小的值放到列表第一个位置，再找到剩余列表中最小的值，放到第二个位置

def selectionSort(alist):
    for i in range(len(alist)-1):
        min = i
        for j in range(i+1, len(alist)):
            if alist[j] < alist[min]:
                min = j
        alist[i], alist[min] = alist[min], alist[i]
    return alist

时间复杂度是O(n2)

5、归并排序

原理：列表分成两段有序，然后分解成每个元素后，再合并成一个有序列表，这种操作就叫做一次归并。应用到排序就是，把列表分成一个元素一个元素的，一个元素当然是有序的，将有序列表一个一个合并，最终合并成一个有序的列表

def MergerSort(lists):
    # 细分到一个列表中只有一个元素的情况，对每一次都调用merge函数变成有序的列表
    if len(lists)<=1:
        return lists
    num=int(len(lists)/2)
    left=MergerSort(lists[:num])
    right=MergerSort(lists[num:])
    return Merge(left,right)

def Merge(left,right):
    #left right为两个list
    r,l=0,0
    result=[]
    while l<len(left) and r<len(right):
        if left[l]<=right[r]:
            result.append(left[l])
            l+=1
        else:
            result.append(right[r])
            r+=1
    # 如果两个列表并不是平均分的，就会存在有元素没有加入到临时列表的情况，所以再判断一下
    result+=list(left[l:])
    result+=list(right[r:])
    return result

print(MergerSort([22,3,2,8,65,8,9,1,4,3]))

时间复杂度是O(nlogn)

特殊的，归并排序还有一个O(n)的空间复杂度

6、希尔排序

希尔排序是一种分组插入排序的算法　　

思路：

　　首先取一个整数d1=n/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序；

　　取第二个整数d2=d1/2，重复上述分组排序过程，直到di=1，即所有元素在同一组内进行直接插入排序。

希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。

L = [1, 3, 2, 32, 5, 4]
def Shell_sort(L):
    step = len(L)/2
    while step > 0:
        for i in range(step,len(L)):            #在索引为step到len（L）上，比较L[i]和L[i-step]的大小
            while(i >= step and L[i] < L[i-step]):      #这里可以调整step从小到大或者从大到小排列
                L[i],L[i-step] = L[i-step],L[i]
                i -= step
        step /= 2
    print L
Shell_sort(L)

8.计数排序

需求：有一个列表，列表中的数都在0到100之间（整数），列表长度大约是100万，设计算法在O(n)时间复杂度内将列表进行排序

分析：列表长度很大，但是数据量很少，会有大量的重复数据。可以考虑对这100个数进行排序

代码：

1 2 3 4 5 6 7 8 9 10

def count_sort(li):     count = [0 for i in range(101)]  # 根据原题，0-100的整数     for i in li:         count[i] += 1       i = 0     for index,m in enumerate(count):  # enumerate函数将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。         for j in range(m):             li[i] = index             i += 1