创建名为 prac10.py 的文件，在其中编写一个顺序表的类，该类必须至少含有两个 成员变量(关键字和其他信息)及相关的基本操作，具体如下。
初始化一个顺序表 SSequenceList。
通 过 CreateSequenceListByInput()方法从键盘上将待排序记录输入顺序表 SSequenceList。
调用排序算法
调用 InsertSort()方法对序列 SSequenceList 进行排序。
调用 ShellSort()方法对序列进行排序。
调用 BubbleSort()方法对序列进行排序。
调用 AdjustPartition(self,low,high)方法对指定部分的序列进行分区；
调用 QuickSort(self,low,high)方法对序列进行排序。
调用 SelectSort()方法对序列进行排序。
调用 AdjustHeap(self,i,SeqListLen)对指定部分序列进行调整，使之满足堆的定义;
调用 HeapSort()方法对序列进行堆排序。
调用 Merge()方法对两个相邻子序列进行归并；
调用 MergeSort()方法对序列进行归并排序。
通过 TraverseElementSet()方法将每次排序后的序列 SSequenceList 输出到屏幕上。
class Node(object):def __init__(self, index, key): # 构建书序表节点索引-值对self.index = indexself.key = keyclass SSequenceList(object):def __init__(self):self.sequence_list = []def CreateSequenceListByInput(self):index = -1 # 用于计数（从而填入索引）while True:info = input("请输入数字，依次输入一个，或输入“终止”以结束：")if info != "终止":try:info = int(info)index += 1 # 缩印的自加只能在这里面进行，要避开ValueErrorexcept ValueError:print("请输入数字")continue # 跳过后面的运行步骤self.sequence_list.append(Node(index, info)) # 写入数据print("%d写入成功" % info)else:breakdef InsertSort(self): # 直接插入排序length = len(self.sequence_list)for i in range(1, len(self.sequence_list)): # 循环每一个值for j in range(i, 0, -1): # 对每一个值向前进行依次比对if self.sequence_list[j].key < self.sequence_list[j - 1].key:self.sequence_list[j].key, self.sequence_list[j - 1].key = self.sequence_list[j - 1].key, self.sequence_list[j].key # 如果出现反序列值，则交换顺序使其正序else:break # 完成对某一个值的比对后关闭内层循环def ShellSort(self): # 希尔排序gap = len(self.sequence_list) // 2 # 需用整除取整数部分，将整个顺序表成对部分优先分组进行排序while gap > 0:for i in range(gap, len(self.sequence_list)):index = iwhile index > 0:if self.sequence_list[index - gap].key > self.sequence_list[index].key: # 在这个两个为一组的条件下，将大的那个放在后面，小的那个放在前面self.sequence_list[index - gap].key, self.sequence_list[index].key = self.sequence_list[index].key, self.sequence_list[index - gap].keyindex -= gap # 等价于将大的那个换成了小的else:breakgap = gap // 2 # 扩大小组范围，进行进一步排序def BubbleSort(self): # 冒泡排序for i in range(len(self.sequence_list) - 1): # 双重循环，第一重是保障完成排序的最多次数的循环for j in range(len(self.sequence_list) - 1 - i): # 第二层循环是在某一趟冒泡排序中对全部临近的一对数据进行鉴别操作if self.sequence_list[j].key > self.sequence_list[j + 1].key: # 如果存在可以交换的（存在逆序）self.sequence_list[j].key, self.sequence_list[j + 1].key = self.sequence_list[j + 1].key, self.sequence_list[j].key # 交换其位置else:continuedef AdjustPartition(self, low, high): # 在快速排序中指定区间进行序列分区while low < high: # 如果分区还没结束（分区结束的时候low和high交错）while self.sequence_list[low].key < self.sequence_list[0].key: # 如果存在左分区某个值小于枢轴low += 1 # 跳过该点while self.sequence_list[high].key > self.sequence_list[0].key: # 如果存在右分区某个值大于枢轴high -= 1 # 跳过该点if low < high: # 防止数组越界self.sequence_list[low].key, self.sequence_list[high].key = self.sequence_list[high].key, self.sequence_list[low].key # 将之前判定的需要大小交换（也就是无法跳过该点）的进行交换low += 1high -= 1return lowdef QuickSort(self, low, high):if low < high: # 判定条件index = self.AdjustPartition(low, high) # 获取分区结果self.QuickSort(low, index - 1) # 嵌套不断对左右分区及其子分区进行排序self.QuickSort(index + 1 , high)def SelectSort(self):for i in range(len(self.sequence_list) - 1): # 选取无序部分第一个值index = ifor j in range(i + 1, len(self.sequence_list)): # 选取无序部分的一个值if self.sequence_list[index].key > self.sequence_list[j].key: # 比对是否是更小的那个，之所以这里不直接用i就是因为i是不变的，而index是更新了最小值位置的，从而便于查找下一个最小值index = j # 如果发现更小的就直接替换（在循环的过程中，出现的更小的那一个会将原有的那个比较小的替换掉）self.sequence_list[i].key, self.sequence_list[index].key = self.sequence_list[index].key, self.sequence_list[i].key # 调换，这种方式可以最大限度减小调换的次数def AdjustHeap(self, i, length): # 建堆j = 2 * i + 1while j <= length:if j + 1 <= length and self.sequence_list[j].key < self.sequence_list[j + 1].key:j += 1 # 判断是否有右子节点，且右比左大，则更新j至右子节点if self.sequence_list[i].key < self.sequence_list[j].key: # 判断大小并将较大者的值和较小者交换self.sequence_list[i].key, self.sequence_list[j].key = self.sequence_list[j].key, self.sequence_list[i].keyi = j # 交换后，存在孙节点，把i设置为子节点，继续比对j = 2 * i + 1else:breakdef HeapSort(self):length = len(self.sequence_list)for i in range((length - 2) // 2, -1, -1):self.AdjustHeap(i, length - 1) # 建堆for i in range(length - 1, -1, -1): # 指向堆的最后一个元素self.sequence_list[0].key, self.sequence_list[i].key = self.sequence_list[i].key, self.sequence_list[0].key # 序列调换self.AdjustHeap(0, i - 1) # 指向新的length，保障节点每向上移动一次，均确保依然是一个堆def Merge(self, left, right):i = 0j = 0meg = [] # 存放左右两组的合并内容while i < len(left) and j < len(right):if left[i] <= right[j]:meg.append(left[i])i += 1else:meg.append(right[j])j += 1meg = meg + left[i:] + right[j:] # 处理未处理完的列表（因为只要存在等于则上述循环结束，而必然会存在一个一个列表处理不完全）return megdef MergeSort(self, seq):length = len(seq) # 读取输入的长度if length == 1: # 如果长度为1直接返回表（已经到了最后一层，分无可分）return seqelse:mid = length // 2 # 取中间，进行分而治之left = self.MergeSort(seq[:mid]) # 拆分为左右两部分进行迭代right = self.MergeSort(seq[mid:])list_left = []list_right = [] # 预备的将sequence list转化为list便于进一步处理for i in range(len(left)):list_left.append(left[i].key) # 实在是受不了每次都要考虑加不加key的问题了，因此直接先把key调出来转列表，然后处理for i in range(len(right)):list_right.append(right[i].key) # 同上理merge = self.Merge(list_left, list_right) # 进行排序移动if length != len(self.sequence_list): # 如果发现返回值的长度与原self.sequence_list不同，表明未到最外层迭代，需返回该层的seq进行下一步迭代for i in range(len(merge)):seq[i].key = merge[i] # 再转成SSequenceList对象return seqelse:for i in range(len(merge)):self.sequence_list[i].key = merge[i] # 如果迭代到了最外层，直接更新原顺序表为排序后结果returndef TraverseElementSet(self): # 遍历顺序表for i in range(0, len(self.sequence_list)):print(self.sequence_list[i].key, end=" ")print() # 保证换行if __name__ == "__main__":seq = SSequenceList()seq.CreateSequenceListByInput()print("原始序列为", end="：")seq.TraverseElementSet()for i in range(0, 9):if i == 0:seq_1 = seqseq_1.InsertSort()print("直接插入排序后为", end="：")seq_1.TraverseElementSet()elif i == 1:seq_2 = seqseq_2.ShellSort()print("希尔排序后为", end="：")seq_2.TraverseElementSet()elif i == 2:seq_3 = seqseq_3.BubbleSort()print("冒泡排序后为", end="：")seq_3.TraverseElementSet()elif i == 3:seq_4 = seqseq_4.QuickSort(0, len(seq.sequence_list) - 1)print("快速排序后为", end="：")seq_4.TraverseElementSet()elif i == 4:seq_5 = seqseq_5.SelectSort()print("简单选择排序后为", end="：")seq_5.TraverseElementSet()elif i == 5:seq_6 = seqseq_6.HeapSort()print("堆排序后为", end="：")seq_6.TraverseElementSet()elif i == 6:seq_7 = seqseq_7.MergeSort(seq_7.sequence_list)print("归并排序后为", end="：")seq_7.TraverseElementSet()
基于Python的数据结构实验——内排序（直接插入排序 希尔排序 冒泡排序 快速排序 选择排序 堆排序 归并排序）（附详细代码和注释）
