1、1快速排序主元
題目?jī)?nèi)容：
著名的快速排序算法里有一個(gè)經(jīng)典的劃分過(guò)程：我們通常采用某種方法取一個(gè)元素作為主元（中值），通過(guò)交換，把比主元小的元素放到它的左邊，比主元大的元素放到它的右邊。 給定劃分后的N個(gè)互不相同的正整數(shù)的排列，請(qǐng)問(wèn)有多少個(gè)元素可能是劃分前選取的主元？
例如給定的排列是[1, 3, 2, 4, 5]。則：
1 的左邊沒(méi)有元素，右邊的元素都比它大，所以它可能是主元；
盡管 3 的左邊元素都比它小，但其右邊的 2 比它小，所以它不能是主元；
盡管 2 的右邊元素都比它大，但其左邊的 3 比它大，所以它不能是主元；
類似原因，4 和 5 都可能是主元。
因此，有 3 個(gè)元素可能是主元。
輸入格式:
一行數(shù)個(gè)整數(shù)的排列，由空格分隔
輸出格式：
在第 1 行中輸出有可能是主元的元素個(gè)數(shù)；在第 2 行中按遞增順序輸出這些元素，其間以 1 個(gè)空格分隔，行首尾不得有多余空格。
輸入樣例：
1 3 2 4 5
輸出樣例：
3
1 4 5
代碼：

def quickSort(alist):
    output = []
    if len(alist) == 1:
        print(1)
        print(alist[0])
    for i in range(1, len(alist)-1):
        if alist[i] > max(alist[:i]) and alist[i] < min(alist[i+1:]):
            output.append(alist[i])
    if alist[0] < min(alist[1:]):
        output.append(alist[0])
    if alist[-1] > max(alist[:-2]):
        output.append(alist[-1])
    output.sort()
    print(len(output))
    print(" ".join([str(i) for i in output]))

quickSort(list(map(int, input().split())))

2、第一個(gè)壞版本
題目?jī)?nèi)容：
現(xiàn)在有同一個(gè)產(chǎn)品的N個(gè)版本，編號(hào)為從1至N的整數(shù)；其中從某個(gè)版本之后所有版本均已損壞?，F(xiàn)給定一個(gè)函數(shù)isBadVersion，輸入數(shù)字N可判斷該版本是否損壞（若損壞將輸出True）；請(qǐng)找出第一個(gè)損壞的版本。
注：有時(shí)isBadVersion函數(shù)運(yùn)行速度很慢，請(qǐng)注意優(yōu)化查找方式
輸入格式:
兩行
第一行為整數(shù)，為產(chǎn)品號(hào)總數(shù)N
第二行為給定的判斷函數(shù)，使用有效的Python表達(dá)式給出，可使用eval讀取
輸出格式：
一行數(shù)字，表示第一個(gè)損壞的版本
輸入樣例：
50
lambda n:n>=30
輸出樣例：
30
示例代碼模板：
N = int(input())
isBadVersion = eval(input())

def firstBadVersion(n):

code here

pass

print(firstBadVersion(N))

代碼：

N = int(input())
isBadVersion = eval(input())

def firstBadVersion(n):
    left = 1
    right = n
    while left < right:
        mid = (right - left) // 2
        if isBadVersion(mid):
            right = mid
        else:
            left = mid + 1
    return left

print(firstBadVersion(N))

3、插入與歸并
題目?jī)?nèi)容：
給出如下定義：
插入排序是迭代算法，逐一獲得輸入數(shù)據(jù)，逐步產(chǎn)生有序的輸出序列。每步迭代中，算法從輸入序列中取出一元素，將之插入有序序列中正確的位置。如此迭代直到全部元素有序。
歸并排序進(jìn)行如下迭代操作：首先將原始序列看成 N 個(gè)只包含 1 個(gè)元素的有序子序列，然后每次迭代歸并兩個(gè)相鄰的有序子序列，直到最后只剩下 1 個(gè)有序的序列。
現(xiàn)給定原始序列和由某排序算法產(chǎn)生的中間序列，請(qǐng)你判斷該算法究竟是哪種排序算法？
輸入格式:
兩行由空格分隔的數(shù)字，其對(duì)應(yīng)長(zhǎng)度相等的列表
其中第一行代表未排序的列表，第二行是排序算法過(guò)程中某一步的中間列表
輸出格式：
首先在第 1 行中輸出Insertion Sort表示插入排序、或Merge Sort表示歸并排序；然后在第 2 行中輸出用該排序算法再迭代一輪的結(jié)果序列。題目保證每組測(cè)試的結(jié)果是唯一的。數(shù)字間以空格分隔，且行首尾不得有多余空格
輸入樣例：
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
輸出樣例：
Merge Sort
1 2 3 8 4 5 7 9 0 6
輸入樣例2：
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
輸出樣例2：
Insertion Sort
1 2 3 5 7 8 9 4 6 0
代碼：

def check(lst1, lst2):
    flag = 0
    for i in range(len(lst2)-1):
        if lst2[i] > lst2[i+1]:
            flag = i+1
            break
    if lst1[flag:] == lst2[flag:]: #插入排序
        result = sorted(lst1[:flag+1])+lst2[flag+1:]
        return True, result
    else:#歸并排序
        cnt = 2
        result = lst2
        while result == lst2:
            sub_lst = [sorted(lst2[i:i+cnt]) for i in range(0, len(lst2), cnt)]
            result = [num for sub in sub_lst for num in sub]
            cnt *= 2
            return False, result

lst1 = [int(i) for i in input().split()]
lst2 = [int(i) for i in input().split()]
num = len(lst1)
flag, next_list = check(lst1, lst2)
if flag:
    print("Insertion Sort")
else:
    print("Merge Sort")
print(" ".join([str(i) for i in next_list]))