一、 实验目的

1．加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。

二、实验任务

1、排序算法
目前已知有几十种排序算法，请查找资料，并尽可能多地实现多种排序算法（至少实现8种）并分析算法的时间复杂度。比较各种算法的优劣。
2、三壶谜题：
有一个充满水的8品脱的水壶和两个空水壶（容积分别是5品脱和3品脱）。通过将水壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到4品脱的水。
3、交替放置的碟子
我们有数量为2n的一排碟子，n黑n白交替放置：黑，白，黑，白…
现在要把黑碟子都放在右边，白碟子都放在左边，但只允许通过互换相邻碟子的位置来实现。为该谜题写个算法，并确定该算法需要执行的换位次数。
4、带锁的门：
在走廊上有n个带锁的门，从1到n依次编号。最初所有的门都是关着的。我们从门前经过n次，每次都从1号门开始。在第i次经过时（i = 1,2，…, n)我们改变i的整数倍号锁的状态；如果门是关的，就打开它；如果门是打开的，就关上它。在最后一次经过后，哪些门是打开的，哪些门是关上的？有多少打开的门？

三、实验设备及编程开发工具

实验设备：Win10电脑
开发工具：Python 3.7，Pycharm

四、实验过程设计（算法思路及描述，代码设计）

1、排序算法

（1）冒泡排序

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个

2、对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上

3、针对所有的元素重复以上的步骤，除了最后一个

4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

代码：

def BubbleSort(sums):
    n = len(sums)
    for i in range(n):
        for j in range(1,n - i):
            if sums[j - 1] > sums[j]:
                sums[j - 1],sums[j] = sums[j],sums[j - 1]
    return sums

import random
import time

List = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()

BubbleSort(List)

b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

冒泡排序

最好时间复杂度为O(n^{2)，最坏时间复杂度为O(n}2)，平均时间复杂度为O(n^2)

（2）选择排序

1、在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2、再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾

3、以此类推，直到所有元素均排序完毕

代码：

def SelectSort(sums):
    n = len(sums)
    for i in range(0,n):
        min = i
        for j in range(i + 1,n):
            if sums[j] < sums[min]:
                min = j
            sums[min],sums[i] = sums[i],sums[min]
    return sums

import random
import time

List = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()

SelectSort(List)

b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

选择排序

最好时间复杂度为O(n^{2)，最坏时间复杂度为O(n}2)，平均时间复杂度为O(n^2)

（3）插入排序

1、从第一个元素开始，该元素可以认为已经被排序

2、取出下一个元素，在已经排序的元素序列中从后向前扫描

3、如果被扫描的元素（已排序）大于新元素，将该元素后移一位

4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5、将新元素插入到该位置后

6、重复步骤2~5

代码：

def InsertSort(sums):
    n = len(sums)
    for i in range(1,n):
        temp = sums[i]
        j = i - 1
        while j >= 0 and sums[j] > temp:
            sums[j + 1] = sums[j]
            j -= 1
        sums[j + 1] = temp
    return sums

import random
import time

List = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()

InsertSort(List)

b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

插入排序

最好时间复杂度为O(n)，最坏时间复杂度为O(n^{2)，平均时间复杂度为O(n}2)

（4）希尔排序

1、比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，算法先将要排序的一组数按某个增量d分成若干组

2、对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序

3、当增量减到1时，整个要排序的数被分成一组，排序完成

4、一般的初次取序列的一半为增量，以后每次减半，直到增量为1

代码：

def ShellSort(sums):
    n = len(sums)
    mid = n//2
    while mid >= 1:
        for i in range(mid,n):
            temp = sums[i]
            j = i
            while j - mid >= 0 and sums[j - mid] > temp:
                sums[j] = sums[j - mid]
                j -= mid
            sums[j] = temp
        mid //= 2
    return sums

import random
import time

List = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()

ShellSort(List)

b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

希尔排序

最好时间复杂度为O(nlog n)，最坏时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)

（5）归并排序

1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2、设定两个指针，最初位置分别为两个已经排序序列的起始位置

3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4、重复步骤 3 直到某一指针达到序列尾

5、 将另一序列剩下的所有元素直接复制到合并序列尾

代码：

def MergeSort(sums):
    if len(sums) <= 1:
        return sums
    n = len(sums)//2
    left = MergeSort(sums[:n])
    right = MergeSort(sums[n + 1:])
    return Merge(left,right)

def Merge(left,right):
    new_sums = []
    i,j = 0,0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            new_sums.append(left[i])
            i += 1
        else:
            new_sums.append(right[j])
            j += 1
    new_sums = new_sums + left[i:] + right[j:]
    return new_sums

import random
import time

List = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()

MergeSort(List)

b = time.time()
print(MergeSort(List))
print("算法消耗时间为：",(b - a)*100,"毫秒")

归并排序

最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)

（6）快速排序

1、从数列中挑出一个元素作为基准数

2、分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边

3、再对左右区间递归执行第二步，直至各区间只有一个数

代码：

def QuickSort(sums,left,right):
    if left >= right:
        return False
    low = left
    high = right
    temp = sums[low]
    while left < right:
        while left < right and sums[right] > temp:
            right -= 1
        sums[left] = sums[right]
        while left < right and sums[left] <= temp:
            left += 1
        sums[right] = sums[left]
    sums[right] = temp
    QuickSort(sums,low,left - 1)
    QuickSort(sums,left + 1,high)
    return sums

import random
import time

List = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()

QuickSort(List,0,len(List) - 1)

b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

快速排序

最好时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)，平均时间复杂度为O(nlogn)

（7）堆排序

1、最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点

2、创建最大堆：将堆中的所有数据重新排序

3、堆排序：移除位在第一个数据的根节点，并做最大堆调整的递归运算

代码：

def HeapSort(sums):
    n = len(sums)
    first = n//2 - 1
    for start in range(first,-1,-1):
        HeapSort_Max(sums,start,n - 1)
    for end in range(n - 1,0,-1):
        temp = sums[end]
        sums[end] = sums[0]
        sums[0] = temp
        HeapSort_Max(sums,0,end - 1)
    return sums

def HeapSort_Max(sums,start,end):
    root = start
    while True:
        child = 2 * root + 1
        if child > end:
            break
        if child + 1 <= end and sums[child] < sums[child + 1]:
            child = child + 1
        if sums[root] < sums[child]:
            temp = sums[root]
            sums[root] = sums[child]
            sums[child] = temp
            root = child
        else:
            break

import random
import time

List = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()

HeapSort(List)

b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

堆排序

最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)

（8）计数排序

1、找出待排序的数组中最大和最小的元素，新开辟一个长度为 最大值-最小值+1 的数组

2、统计原数组中每个元素出现的次数，存入到新开辟的数组中

3、根据每个元素出现的次数，按照新开辟数组中从小到大的秩序，依次填充到原来待排序的数组中，完成排序

代码：

def RadixSort(sums):
    Min = min(sums)
    Max = max(sums)
    List = [0 for i in range(Max - Min + 2)]
    for i in range(len(sums)):
        List[sums[i] - Min] += 1
    j,k = 0,0
    while j < (len(List)):
        if List[j] > 0:
            sums[k] = j + Min
            List[j] -= 1
            k += 1
        else:
            j += 1
    return sums

import random
import time

List = [random.randint(0, 100000) for i in range(5000)]
print(List)
a = time.time()

RadixSort(List)

b = time.time()
print(List)
print("算法消耗时间为：",(b - a)*100,"毫秒")

计数排序

最好时间复杂度为O(n)，最坏时间复杂度为O(n)，平均时间复杂度为O(n)

2、三壶谜题

将某个时刻水壶中水的数量看作一个状态，用一个长度为3的数组表示，初始状态便为[8,0,0],再拓展他的下一结点的可能结构，若下一结点的结构已经被拓展过了便放弃，若没有拓展过则加入拓展列表中。然后递归上述操作，直到拓展列表为空或者找到目标为止。

代码：

class node: 
   def __init__(self, data):
       self.data = data
       self.per = None 

def pour(n):
   r_list = n.data 
   max_list = [8, 5, 3]  
   for i, j in ((0, 1), (0, 2), (1, 2), (1, 0), (2, 0), (2, 1)):
       if r_list[i] != 0:
           n_list = r_list.copy()  
           if r_list[i] + r_list[j] > max_list[j]:
               n_list[i] = r_list[i] - (max_list[j] - r_list[j])
               n_list[j] = max_list[j]
           else:
               n_list[j] = r_list[i] + r_list[j]
               n_list[i] = 0
           flag = True 
           for one in closed_list:
               if one.data == n_list:  
                   flag = False
           if flag:
               print("扩展的新节点是：",n_list)
               new_node = node(n_list)  
               new_node.per = n
               open_list.append(new_node)

def BFS_node(root_1):  
   n = root_1
   print("当前节点：",n.data)
   if open_list is None:
       return "没有找到4品脱的水"
   nodelist = n.data
   if 4 in nodelist:
       print("找到了4品脱的水")
       print_node(n)
       return "找到了4品脱的水"
   closed_list.append(open_list.pop(0))
   pour(n)
   print("*******")
   BFS_node(open_list[0])

def print_node(n): 
   if n.per == None:
       return ""
   print(n.data)
   print_node(n.per)


# 初始化数据
root = node([8, 0, 0])
open_list = [root]  
closed_list = []
BFS_node(open_list[0])

三壶谜题：

时间复杂度为O(n^2)

3、交替放置的碟子

输入碟子的总数n，产生一个0，1交错的列表，其中1代表黑碟子，0代表白碟子，通过冒泡排序将碟子分开。
代码：

def Black_White(s):
    sums = [0 for i in range(s)]
    i = 0
    while i * 2 < s:
        sums[i * 2] = 1
        i += 1
    print(sums)
    k = 0
    n = len(sums)
    for i in range(n):
        for j in range(1, n - i):
            if sums[j - 1] > sums[j]:
                sums[j - 1], sums[j] = sums[j], sums[j - 1]
                k += 1
    print(sums)
    print("次数为：", k, "次")

# 黑碟子为1，白碟子为0
Black_White(40)

交替放置的碟子：

时间复杂度为O(n^2)

4、带锁的门

输入门的总数n，产生两个列表表示开门和关门的状态，同过循环遍历，将各位表示反复重置，最终得到门的状态并输出。其中1表示开门，0表示关门。
代码：

# 1表示开门，0表示关门
def LockDoor(n):
    List = [0 for i in range(n)]
    List_open = []
    List_close = []
    k,s = 0,0
    for i in range(1,n + 1):
        m = n // i
        for j in range(1,m + 1):
            
上一篇：DPDK系列之四十二DPDK应用网络编程UDP编程

下一篇：速通数据结构与算法第四站 双链表