基于Python的数据结构实验——内排序（直接插入排序，希尔排序，冒泡排序，快速排序，选择排序，堆排序，归并排序）（附详细代码和注释）_排序的操作实验-直接插入排序python

创建名为 prac10.py 的文件，在其中编写一个顺序表的类，该类必须至少含有两个 成员变量(关键字和其他信息)及相关的基本操作，具体如下。

1. 初始化一个顺序表 SSequenceList。

2. 通 过 CreateSequenceListByInput()方法从键盘上将待排序记录输入顺序表 SSequenceList。

3. 调用排序算法

• 调用 InsertSort()方法对序列 SSequenceList 进行排序。

• 调用 ShellSort()方法对序列进行排序。

• 调用 BubbleSort()方法对序列进行排序。

• 调用 AdjustPartition(self,low,high)方法对指定部分的序列进行分区；

调用 QuickSort(self,low,high)方法对序列进行排序。

• 调用 SelectSort()方法对序列进行排序。

• 调用 AdjustHeap(self,i,SeqListLen)对指定部分序列进行调整，使之满足堆的定义;

调用 HeapSort()方法对序列进行堆排序。

• 调用 Merge()方法对两个相邻子序列进行归并；

调用 MergeSort()方法对序列进行归并排序。

4. 通过 TraverseElementSet()方法将每次排序后的序列 SSequenceList 输出到屏幕上。

class Node(object):
    def __init__(self, index, key):  # 构建书序表节点索引-值对
        self.index = index
        self.key = key
 
class 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  # 缩印的自加只能在这里面进行，要避开ValueError
                except ValueError:
                    print("请输入数字")
                    continue  # 跳过后面的运行步骤
                self.sequence_list.append(Node(index, info))  # 写入数据
                print("%d写入成功" % info)
            else:
                break
    
    def 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 = i
                while 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].key
                        index -= gap  # 等价于将大的那个换成了小的
                    else:
                        break
            gap = 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:
                    continue
    
    def 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 += 1
                high -= 1
        return low
    
    def 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 = i
            for 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 + 1
        while 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].key
                i = j  # 交换后，存在孙节点，把i设置为子节点，继续比对
                j = 2 * i + 1
            else:
                break
                
    def 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 = 0
        j = 0
        meg = []  # 存放左右两组的合并内容
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                meg.append(left[i])
                i += 1
            else:
                meg.append(right[j])
                j += 1
        meg = meg + left[i:] + right[j:]  # 处理未处理完的列表（因为只要存在等于则上述循环结束，而必然会存在一个一个列表处理不完全）
        return meg
    
    def MergeSort(self, seq):
        length = len(seq)  # 读取输入的长度
        if length == 1:  # 如果长度为1直接返回表（已经到了最后一层，分无可分）
            return seq
        else:
            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 seq
            else:
                for i in range(len(merge)):
                    self.sequence_list[i].key = merge[i]  # 如果迭代到了最外层，直接更新原顺序表为排序后结果
                    return
    
    def 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 = seq
            seq_1.InsertSort()
            print("直接插入排序后为", end="：")
            seq_1.TraverseElementSet()
        elif i == 1:
            seq_2 = seq
            seq_2.ShellSort()
            print("希尔排序后为", end="：")
            seq_2.TraverseElementSet()
        elif i == 2:
            seq_3 = seq
            seq_3.BubbleSort()
            print("冒泡排序后为", end="：")
            seq_3.TraverseElementSet()
        elif i == 3:
            seq_4 = seq
            seq_4.QuickSort(0, len(seq.sequence_list) - 1)
            print("快速排序后为", end="：")
            seq_4.TraverseElementSet()
        elif i == 4:
            seq_5 = seq
            seq_5.SelectSort()
            print("简单选择排序后为", end="：")
            seq_5.TraverseElementSet()
        elif i == 5:
            seq_6 = seq
            seq_6.HeapSort()
            print("堆排序后为", end="：")
            seq_6.TraverseElementSet()
        elif i == 6:
            seq_7 = seq
            seq_7.MergeSort(seq_7.sequence_list)
            print("归并排序后为", end="：")
            seq_7.TraverseElementSet()