一、讨论题

略。

二、编程练习

1.进行随机实验，测试顺序搜索算法与二分搜索算法在处理整数列表时的差异。

二分搜索算法只能搜索有序列表，顺序搜索算法无序和有序都可以搜索，因此对比试验做两次。

import timeit
import random
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from chapter5.search import orderSequentialSearch, binarySearch

lenx = []
osy = []
bsy = []
color = ['c', 'b', 'g', 'r', 'm', 'y', 'k', 'w']

for i in range(1000000, 100000000, 1000000):
    t1 = timeit.Timer("orderSequentialSearch(x,random.randrange(%d))" % i, "from __main__ import random, x, orderSequentialSearch")
    t2 = timeit.Timer("binarySearch(x,random.randrange(%d))" % i, "from __main__ import random, x, binarySearch")
    x = list(range(i))
    # np.random.shuffle(x)
    findtime1 = t1.timeit(number=1)
    # x = list(range(i))
    findtime2 = t2.timeit(number=1)
    print("%d, %15.6f，%15.6f" % (i, findtime1, findtime2))
    lenx.append(i)
    osy.append(findtime1)
    bsy.append(findtime2)
    ax = plt.gca()
    # 去掉边框
    ax.spines['top'].set_color('none')
    ax.spines['right'].set_color('none')
    # 移位置 设为原点相交
    ax.xaxis.set_ticks_position('bottom')
    ax.spines['bottom'].set_position(('data', 0))
    ax.yaxis.set_ticks_position('left')
    ax.spines['left'].set_position(('data', 0))
    # plt.ylim(0, 0.0001)
    plt.scatter(lenx, osy, c=color[3], edgecolors='r', label='orderSequentialSearch')
    plt.scatter(lenx, bsy, c=color[1], edgecolors='b', marker='^', label='binarySearch')
    plt.xlabel('lenth(list)')
    plt.ylabel('time(/s)')
    plt.title('Search(Order)_analysis')
    plt.legend()
    plt.show()

结果如图：

结果分析：对于顺序搜索算法，当要搜索的列表无序时，其性能优于二分搜索。

结果分析：对于顺序搜索算法，当要搜索的列表由序时，其性能远远低于二分搜索算法。

2.随机生成一个有序的整数列表。通过基准测试分析文中给出的二分搜索函数（递归版本与循环版本）。请解释你得到的结果。

关于用python对函数进行基准测试，参考链接：https://blog.csdn.net/qq_21201267/article/details/126241080link，这里使用的书中第二章介绍的timeit包进行基准测试。

def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found

def binarySearch2(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist) // 2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearch2(alist[:midpoint], item)
            else:
                return binarySearch2(alist[midpoint+1:], item)

import timeit
import random
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from chapter5.search import binarySearch2, binarySearch

lenx = []
b1y = []
b2y = []
color = ['c', 'b', 'g', 'r', 'm', 'y', 'k', 'w']

for i in range(1000000, 100000000, 1000000):
    t1 = timeit.Timer("binarySearch(x,random.randrange(%d))" % i, "from __main__ import random, x, binarySearch")
    t2 = timeit.Timer("binarySearch2(x,random.randrange(%d))" % i, "from __main__ import random, x, binarySearch2")
    x = list(range(i))
    findtime1 = t1.timeit(number=1)
    findtime2 = t2.timeit(number=1)
    print("%d, %15.6f，%15.6f" % (i, findtime1, findtime2))
    lenx.append(i)
    b1y.append(findtime1)
    b2y.append(findtime2)
    ax = plt.gca()
    # 去掉边框
    ax.spines['top'].set_color('none')
    ax.spines['right'].set_color('none')
    # 移位置 设为原点相交
    ax.xaxis.set_ticks_position('bottom')
    ax.spines['bottom'].set_position(('data', 0))
    ax.yaxis.set_ticks_position('left')
    ax.spines['left'].set_position(('data', 0))
    plt.scatter(lenx, b1y, c=color[3], edgecolors='r', label='binarySearch1')
    plt.scatter(lenx, b2y, c=color[1], edgecolors='b', marker='^', label='binarySearch2')
    plt.xlabel('lenth(list)')
    plt.ylabel('time(/s)')
    plt.title('binarySearch_analysis')
    plt.legend()
    plt.show()
  

  结果分析 ：对于二分搜索，随着列表长度的增长，循环版本的性能要高于递归版本。
  这是因为：对于递归来说，进行函数调用时会调用“栈”，其中存储了所有的局部变量和其他内容（尾递归可以解决这个问题，但python3不支持尾递归），因此循环里的函数调用操作要快于递归操作。

3.不用切片运算符，实现递归版本的二分搜索算法。别忘了传入头元素和尾元素的下标。随机生成一个有序的整数列表，并进行基准测试。

import timeit
import random
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from chapter5.search import binarySearch2

def binarySearch3(alist, left, right, item):
    if len(alist) == 0:
        return False
    else:
        # midpoint = len(alist) // 2
        midpoint = (left + right) // 2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearch3(alist, left, midpoint - 1, item)
            else:
                return binarySearch3(alist, midpoint + 1, right, item)

lenx = []
b1y = []
b2y = []
color = ['c', 'b', 'g', 'r', 'm', 'y', 'k', 'w']

for i in range(1000000, 100000000, 1000000):
    t1 = timeit.Timer("binarySearch3(x, 0, len(x) - 1,random.randrange(%d))" % i, "from __main__ import random, x, binarySearch3")
    t2 = timeit.Timer("binarySearch2(x,random.randrange(%d))" % i, "from __main__ import random, x, binarySearch2")
    x = list(range(i))
    findtime1 = t1.timeit(number=1)
    findtime2 = t2.timeit(number=1)
    print("%d, %15.6f，%15.6f" % (i, findtime1, findtime2))
    lenx.append(i)
    b1y.append(findtime1)
    b2y.append(findtime2)
    ax = plt.gca()
    # 去掉边框
    ax.spines['top'].set_color('none')
    ax.spines['right'].set_color('none')
    # 移位置 设为原点相交
    ax.xaxis.set_ticks_position('bottom')
    ax.spines['bottom'].set_position(('data', 0))
    ax.yaxis.set_ticks_position('left')
    ax.spines['left'].set_position(('data', 0))
    plt.scatter(lenx, b1y, c=color[3], edgecolors='r', label='binarySearch3')
    plt.scatter(lenx, b2y, c=color[1], edgecolors='b', marker='^', label='binarySearch2')
    plt.xlabel('lenth(list)')
    plt.ylabel('time(/s)')
    plt.title('binarySearch_analysis')
    plt.legend()
    plt.show()

  如图，对于递归版本的二分搜索算法，切片操作的性能要远远低于传入头尾下标操作。

4.为散列表实现len方法__len__。

&

5.为散列表实现in方法__contains__。

    def __len__(self):
        return len(self.slots)

    def __contains__(self, item):
        return item in self.slots

6.采用链接法处理冲突时，如何从散列表中删除元素？如果是采用开放定址法，又如何做呢？有什么必须处理的特殊情况？请为HashTable类实现del方法。

  见书p141，即先找后删，注意冲突。

    def __delitem__(self, key):
        startslot = self.hashfunction(key, len(self.slots))
        stop = False
        found = False
        position = startslot
        while not found and not stop:
            if self.slots[position] == None:
                print('Error: None')
                break
            elif self.slots[position] == key:
                found = True
                self.slots[position] = None
                self.data[position] = None
                data = self.data[position]
            else:
                position = self.rehash(position, len(self.slots))
                if position == startslot:
                    stop = True

7.在本章中，散列表的大小为11。如果表满了，就需要增大。请重新实现put方法，使得散列表可以在载荷因子达到一个预设值时自动调整大小（可以根据载荷对性能的影响，自己决定预设值）。

    def overload(self):
        slotsB = self.slots
        dataB = self.data
        self.slots = [None] * self.size
        self.data = [None] * self.size
        for i in range(len(self.slots)):
            if slotsB[i] != None:
                hashvalue = self.hashfunction(slotsB[i], len(self.slots))
                if self.slots[hashvalue] == None:
                    self.slots[hashvalue] = slotsB[i]
                    self.data[hashvalue] = dataB[i]
                else:
                    nextslots = self.rehash(hashvalue, len(self.slots))
                    while self.slots[nextslots] != None and self.slots[nextslots] != slotsB[i]:
                        nextslots = self.rehash(nextslots, len(self.slots))
                    if self.slots[nextslots] == None:
                        self.slots[nextslots] = slotsB[i]
                        self.data[nextslots] = dataB[i]
                    else:
                        self.data[nextslots] = dataB[i]
                        
    def put(self, key, data):
        k = 0.9
        sum = 0
        for i in range(self.size):
            if self.slots[i] != None:
                sum += 1
        if sum / self.size >= k:
            self.size += 6
            for j in range(6):
                self.slots.append(None)
                self.data.append(None)
            self.overload()
        hashvalue = self.hashfunction(key, len(self.slots))
        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        else:
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = data
            else:
                nextslots = self.rehash(hashvalue, len(self.slots))
                while self.slots[nextslots] != None and self.slots[nextslots] != key:
                    nextslots = self.rehash(nextslots, len(self.slots))
                if self.slots[nextslots] == None:
                    self.slots[nextslots] = key
                    self.data[nextslots] = data
                else:
                    self.data[nextslots] = data

8.实现平方探测这一再散列技巧。

    def rehash_square(self, oldhash, size, m):
        return (oldhash + m**2) % size

注意，overload(), put(), get()里的rehash函数都改成rehash_square。

9.使用随机数生成器创建一个含500个整数的列表。通过基准测试分析本章中的排序算法。它们在执行速度上有什么差别？

sort.py：

def bubbleSort(alist):
    for passnum in range(len(alist) - 1, 0, -1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

def shortBubbleSort(alist):
    exchange = True
    passnum = len(alist) - 1
    while passnum > 0 and exchange:
        exchange = False
        for i in range(passnum):
            if alist[i] > alist[i + 1]:
                exchange = True
                temp = alist[i]
                alist[i] = alist[i + 1]
                alist[i + 1] = temp
        passnum -= 1

def selectionSort(alist):
    for fileslot in range(len(alist)-1, 0, -1):
        positionOfMax = 0
        for location in range(1, fileslot + 1):
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location
        temp = alist[fileslot]
        alist[fileslot] = alist[positionOfMax]
        alist[positionOfMax] = temp

def insetionSort(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

def shellSort(alist):
    sublistcount = len(alist) // 2
    while sublistcount > 0:
        for startposition in range(sublistcount):
             gapInsertSort(alist, startposition, sublistcount)
        # print('After increments of size ', sublistcount, 'The list is: ', alist)
        sublistcount //= 2

def gapInsertSort(alist, start, gap):
    for i in range(start+gap, len(alist), gap):
        currentvalue = alist[i]
        position = i
        while position >= gap and alist[position-gap] > currentvalue:
            alist[position] = alist[position-gap]
            position -= gap
        alist[position] = currentvalue

def mergeSort(alist):
    # print('Splitting ', alist)
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        mergeSort(lefthalf)
        mergeSort(righthalf)
        i, j, k = 0, 0, 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i += 1
            else:
                alist[k] = righthalf[j]
                j += 1
            k += 1
        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i += 1
            k += 1
        while j < len(righthalf):
            alist[k] = righthalf[j]
            j += 1
            k += 1
    # print('Merging', alist)

def quickSort(alist):
    quickSortHelper(alist, 0, len(alist) - 1)

def quickSortHelper(alist, first, last):
    if first < last:
        splitpoint = partition(alist, first, last)
        quickSortHelper(alist, first, splitpoint - 1)
        quickSortHelper(alist, splitpoint + 1, last)

def partition(alist, first, last):
    pivotvalue = alist[first]
    leftmark = first + 1
    rightmark = last
    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark += 1
        while leftmark <= rightmark and alist[rightmark] >= pivotvalue:
            rightmark -= 1
        if rightmark < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp

    return rightmark


if __name__ == '__main__':
    # alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    # shellSort(alist)
    b = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    quickSort(b)
    print(b)

import timeit
import random
from chapter5.sort import bubbleSort, shortBubbleSort, selectionSort, insetionSort, shellSort, mergeSort, quickSort

x = []
for i in range(500):
    x.append(random.randint(1, 1000))

t1 = timeit.Timer("bubbleSort(x)", "from __main__ import x, bubbleSort")
print('bubbleSort', t1.timeit(number=1000), 'milliseconds')

t2 = timeit.Timer("shortBubbleSort(x)", "from __main__ import x, shortBubbleSort")
print('shortBubbleSort', t2.timeit(number=1000), 'milliseconds')

t3 = timeit.Timer("selectionSort(x)", "from __main__ import x, selectionSort")
print('selectionSort', t3.timeit(number=1000), 'milliseconds')

t4 = timeit.Timer("insetionSort(x)", "from __main__ import x, insetionSort")
print('insetionSort', t4.timeit(number=1000), 'milliseconds')

t5 = timeit.Timer("shellSort(x)", "from __main__ import x, shellSort")
print('shellSort', t5.timeit(number=1000), 'milliseconds')

t6 = timeit.Timer("mergeSort(x)", "from __main__ import x, mergeSort")
print('mergeSort', t6.timeit(number=1000), 'milliseconds')

t7 = timeit.Timer("quickSort(x)", "from __main__ import x, quickSort")
print('quickSort', t7.timeit(number=1000), 'milliseconds')

结果如图，对于长度为500的列表，排序速度由慢至快排序为：冒泡 < 快速(递归) < 选择 < 归并 < 希尔排序 < 插入 < 短冒泡

10.利用同时赋值特性实现冒泡排序。

def bubbleSort(alist):
    for passnum in range(len(alist) - 1, 0, -1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

if __name__ == '__main__':
    b = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    bubbleSort(b)
    print(b)

11.可以将冒泡排序算法修改为向两个方向“冒泡”。第一轮沿着列表“向上”遍历，第二轮沿着列表“向下”遍历。继续这一模式，直到无须遍历为止。实现这种排序算法，并描述它的适用情形。

def bubbleSort(alist, size):
    left = 0
    right = size - 1
    flag = True
    while flag:
        flag = False
        for i in range(left, right, 1):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                flag = True
        right -= 1
        for j in range(right, left, -1):
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]
                flag = True
        left += 1


if __name__ == '__main__':
    b = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    bubbleSort(b, len(b))
    print(b)

  双向冒泡算法比单向冒泡更适用于序列基本有序，但是有小元素在尾部的情况。例如：对一个递增有序数列尾部添加一个较小的整数，对这个新数列进行排序适合用双向冒泡(相较于普通冒泡)。

12.利用同时赋值特性实现选择排序。

def selectionSort(alist):
    for fileslot in range(len(alist)-1, 0, -1):
        positionOfMax = 0
        for location in range(1, fileslot + 1):
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location
        alist[fileslot], alist[positionOfMax] = alist[positionOfMax], alist[fileslot]

if __name__ == '__main__':
    b = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    selectionSort(b)
    print(b)

13.针对同一个列表使用不同的增量集，为希尔排序进行基准测试。

import timeit
import random
import math

def shellSort(alist):
    sublistcount = len(alist) // 2
    while sublistcount > 0:
        for startposition in range(sublistcount):
             gapInsertSort(alist, startposition, sublistcount)
        # print('After increments of size ', sublistcount, 'The list is: ', alist)
        sublistcount //= 2

def shellSort2(alist):
    k = int(math.log(len(alist) + 1, 2))
    sublistcount = 2 ** k - 1
    while sublistcount > 0:
        k -= 1
        for startposition in range(sublistcount):
             gapInsertSort(alist, startposition, sublistcount)
        # print('After increments of size ', sublistcount, 'The list is: ', alist)
        sublistcount = 2 ** k - 1

def gapInsertSort(alist, start, gap):
    for i in range(start+gap, len(alist), gap):
        currentvalue = alist[i]
        position = i
        while position >= gap and alist[position-gap] > currentvalue:
            alist[position] = alist[position-gap]
            position -= gap
        alist[position] = currentvalue

if __name__ == '__main__':
    x = []
    for i in range(500):
        x.append(random.randint(1, 1000))

    t1 = timeit.Timer("shellSort(x)", "from __main__ import x, shellSort")
    print('n/2^k:', t1.timeit(number=1000), 'milliseconds')

    t2 = timeit.Timer("shellSort2(x)", "from __main__ import x, shellSort2")
    print('2^k - 1:', t2.timeit(number=1000), 'milliseconds')
    
>>>  ?  
n/2^k: 0.095182 milliseconds
2^k - 1: 0.09979709999999999 milliseconds

14.不用切片运算符，实现mergesort函数。

def mergeSort(alist, left, right):
    if right > left :
        mid = (left + right) // 2
        mergeSort(alist, left, mid)
        mergeSort(alist, mid + 1, right)
        merge(alist, left, mid, right)
    else:
        return

def merge(alist, left, mid, right):
    temp = []
    i, j = left, mid + 1
    while i <= mid and j <= right:
        if alist[i] <= alist[j]:
            temp.append(alist[i])
            i += 1
        else:
            temp.append(alist[j])
            j += 1
    while i <= mid:
        temp.append(alist[i])
        i += 1
    while j <= right:
        temp.append(alist[j])
        j += 1
    alist[left:right+1] = temp

if __name__ == '__main__':
    a = [2, 6, 3]
    length = len(a)
    mid = (0 + len(a) - 1) // 2
    merge(a, 0, mid, len(a) - 1)
    print(a)

    b = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    mergeSort(b, 0, len(b) - 1)
    print(b)

15.有一种改进快速排序的办法，那就是在列表长度小于某个值时采用插入排序(这个值被称为“分区限制”)。这是什么道理？重新实现快速排序算法，并给一个随机整数列表拍戏。采用不同的分区限制进行性能分析。

  快速排序对于小规模的数据集性能不是很好，但是快速排序算法使用了分治技术，最终来说大的数据集都要分为小的数据集来进行处理。由此可以得到的改进就是，当数据集较小时，不必继续递归调用快速排序算法，而改为调用其他的对于小规模数据集处理能力较强的排序算法来完成。

import timeit
import random

def quickSort2(alist, k):
    quickSortHelper2(alist, 0, len(alist) - 1, k)

def quickSortHelper2(alist, first, last, k):
    if first < last:
        if last - first <= k:
            temp = insetionSort(alist[first:last+1])
            alist[first:last+1] = temp
        else:
            splitpoint = partition(alist, first, last)
            quickSortHelper2(alist, first, splitpoint - 1, k)
            quickSortHelper2(alist, splitpoint + 1, last, k)

def insetionSort(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
    return alist

def partition(alist, first, last):
    pivotvalue = alist[first]
    leftmark = first + 1
    rightmark = last
    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark += 1
        while leftmark <= rightmark and alist[rightmark] >= pivotvalue:
            rightmark -= 1
        if rightmark < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp

    return rightmark

if __name__ == '__main__':
    x = []
    for i in range(500):
        x.append(random.randint(1, 1000))

    t1 = timeit.Timer("quickSort2(x, 5)", "from __main__ import x, quickSort2")
    print('k = 5:', t1.timeit(number=1000), 'milliseconds')

    t2 = timeit.Timer("quickSort2(x, 50)", "from __main__ import x, quickSort2")
    print('k = 50:', t2.timeit(number=1000), 'milliseconds')

    t3 = timeit.Timer("quickSort2(x, 100)", "from __main__ import x, quickSort2")
    print('k = 100:', t3.timeit(number=1000), 'milliseconds')

    t4 = timeit.Timer("quickSort2(x, 200)", "from __main__ import x, quickSort2")
    print('k = 200:', t4.timeit(number=1000), 'milliseconds')

  结果如图：对于长度为500的数列，随着k值增大，排序速度越快。

16.修改quickSort函数，在选取基准值时采用三数取中法。通过实验对比两种技巧的性能差异。

import timeit
import random
from chapter5.sort import quickSort

def quickSort2(alist):
    quickSortHelper2(alist, 0, len(alist) - 1)

def quickSortHelper2(alist, first, last):
    if first < last:
        splitpoint = partition2(alist, first, last)
        quickSortHelper2(alist, first, splitpoint - 1)
        quickSortHelper2(alist, splitpoint + 1, last)

def partition2(alist, first, last):
    mid = (first + last) // 2
    firstvalue = alist[first]
    midvalue = alist[mid]
    lastvalue = alist[last]
    if midvalue > firstvalue and midvalue < lastvalue:
        alist[first], alist[mid] = alist[mid], alist[first]
    elif lastvalue > firstvalue and lastvalue < midvalue:
        alist[first], alist[last] = alist[last], alist[first]
    pivotvalue = alist[first]
    leftmark = first + 1
    rightmark = last
    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark += 1
        while leftmark <= rightmark and alist[rightmark] >= pivotvalue:
            rightmark -= 1
        if rightmark < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp
    return rightmark


if __name__ == '__main__':
    x = []
    for i in range(1000):
        x.append(random.randint(1, 1000))

    t1 = timeit.Timer("quickSort(x)", "from __main__ import x, quickSort")
    print('quickSort:', t1.timeit(number=1000), 'milliseconds')

    t2 = timeit.Timer("quickSort2(x)", "from __main__ import x, quickSort2")
    print('quickSort2:', t2.timeit(number=1000), 'milliseconds')

  如图所示，三数取中法要比未改进的的快速排序速度快的多得多。

三、总结

主要学习了二分搜索、散列表、各种主流排序算法及其改进等。