Python数据结构实验 排序实验（一）_数据排序实验程序

一、实验目的

1．熟悉排序的基本概念，包括排序的稳定性、内排序和外排序之间的差异；

2．掌握插入排序算法，包括直接插入排序、折半插入排序和希尔排序的过程和算法实现；

3．掌握交换排序算法，包括冒泡排序和快速排序的过程和算法实现。

二、实验环境

1．Windows操作系统的计算机

2．Python3.7环境平台和PyCharm编辑器

三、实验说明 

1．实现插入排序算法和交换排序算法程序设计方法。  
2．实验中如无特别说明，均要求使用脚本（.py）方式编写代码。

3．自主编写程序，必要时参考相关资料。

4．实验学时：2学时

四、实验内容和步骤

1．实验内容

（1） 编写一个实验程序，采用直接插入排序完成一个整数序列的递增排序，并用相关数据进行测试。

参考思路：

方法一：
 
def InsertSort(R):     #对R[0..n-1]按递增有序进行直接插入排序
 
    ……
 
 
 
方法二：
 
def cmp(x,y):
 
    ……
 
    
 
def InsertSort(R):      #对R[0..n-1]按递增有序进行直接插入排序
 
    ……
 
 
 
 
 
#主程序
 
if __name__ == '__main__':
 
    R=[__________      _]
 
    print("初始序列",end=' ')
 
    print(R)
 
    print("排序")
 
    InsertSort(R)
 
    print("排序序列",end=' ')
 
    print(R)
 
 
 

（2）编写一个实验程序，采用希尔排序完成一个整数序列的递增排序，并用相关数据进行测试。

参考思路：

def ShellSort(R):     #对R[0..n-1]按递增有序进行希尔排序
 
    ……
 
 
 
 
 
#主程序
 
if __name__ == '__main__':
 
    R=[__________      _]
 
    print("初始序列",end=' ')
 
    print(R)
 
    print("排序")
 
    ShellSort(R)
 
    print("排序序列",end=' ')
 
    print(R)

（3）编写一个实验程序，采用冒泡排序完成一个整数序列的递增排序，并用相关数据进行测试。

参考思路：

def BubbleSort(R):       #对R[0..n-1]按递增有序进行冒泡排序
 
    ……
 
 
 
 
 
#主程序
 
if __name__ == '__main__':
 
    R=[__________      _]
 
    print("初始序列",end=' ')
 
    print(R)
 
    print("排序")
 
    BubbleSort(R)
 
    print("排序序列",end=' ')
 
    print(R)
 
 
 

2．实验步骤

（1）分析实验内容，写出程序大致框架或完整的程序代码。

（2）进入Python集成环境。

（3）编辑程序并进行保存。

（4）运行程序，若有错误，修改错误后再次运行，如此反复进行到不显示出错为止。

（5）检查程序输出结果。

五、实验代码与结果（程序运行代码及其结果）

1． （1）给出算法的基本设计思想。

  （2）根据设计思想，采用Python语言描述算法，关键之处给出注释。

def InsertSort(R): #对R[0..n-1]按递增有序进行直接插入排序
 
  for i in range(1,len(R)): #从元素R[1]开始
 
    if R[i]<R[i-1]:     #反序时
 
           tmp=R[i] #取出无序区的第一个元素
 
           j=i-1 #有序区R[0..i-1]中向前找R[i]的插入位置
 
    while True:
 
           R[j+1]=R[j] #将大于tmp的元素后移
 
           j-=1 #继续向前比较
 
           if j<0 or R[j]<=tmp:
 
              break   #若j<0或者R[j]<=tmp,退出循环
 
    R[j+1]=tmp #在j+1处插入R[i]
 
 
 
#方法二：
 
def cmp(x,y): #实现递增排序的自定义比较函数
 
  if x<y: return True
 
  else: return False
 
 
 
def InsertSort(R): #对R[0..n-1]按递增有序进行直接插入排序
 
  for i in range(1,len(R)): #从R[1]元素开始
 
     if cmp(R[i],R[i-1]):      #反序时
 
       tmp=R[i] #取出无序区的第一个元素
 
       j=i-1; #在有序区R[0..i-1]中从右向左找R[i]的插入位置
 
       while True:
 
           R[j+1]=R[j] #将大于tmp的元素后移
 
           j-=1 #继续向前比较
 
           if j<0 or not cmp(tmp,R[j]):
 
              break   #若j<0或者R[j]<=tmp,退出循环
 
       R[j+1]=tmp #在j+1处插入R[i]
 
 
 
 
 
#主程序
 
if __name__ == '__main__':
 
    R=[9,8,7,6,5,4,3,2,1,0]
 
    print("初始序列",end=' ')
 
    print(R)
 
    print("排序")
 
    InsertSort(R)
 
    print("排序序列",end=' ')
 
print(R)

2． （1）给出算法的基本设计思想。

  （2）根据设计思想，采用Python语言描述算法，关键之处给出注释。

def ShellSort(R): #对R[0..n-1]按递增有序进行希尔排序
 
  d=len(R)//2    #增量置初值
 
  while d>0:
 
    for i in range(d,len(R)):    #对所有相隔d位置的元素组采用直接插入排序
 
       if R[i]<R[i-d]:      #反序时
 
          tmp=R[i]
 
          j=i-d
 
          while True:
 
             R[j+d]=R[j] #将大于tmp的元素后移
 
             j=j-d              #继续向前找
 
             if j<0 or R[j]<=tmp:
 
               break   #若j<0或者R[j]<=tmp,退出循环
 
          R[j+d]=tmp           #在j+d处插入tmp
 
    d=d//2 #递减增量
 
 
 
#主程序
 
if __name__ == '__main__':
 
    R=[9,8,7,6,5,4,3,2,1,0]
 
    print("初始序列",end=' ')
 
    print(R)
 
    print("希尔排序")
 
    ShellSort(R)
 
    print("希尔排序序列",end=' ')
 
    print(R)

3． （1）给出算法的基本设计思想。

  （2）根据设计思想，采用Python语言描述算法，关键之处给出注释。

def BubbleSort(R):     #对R[0..n-1]按递增有序进行冒泡排序
 
  for i in range(len(R)-1):
 
    exchange=False #本趟前将exchange置为False
 
    for j in range(len(R)-1,i,-1): #一趟中找出最小关键字的元素
 
       if R[j]<R[j-1]:          #反序时交换
 
          R[j],R[j-1]=R[j-1],R[j] #R[j]和R[j-1]交换,将最小元素前移
 
          exchange=True #本趟发生交换置exchange为True
 
    if exchange==False: return    #本趟没有发生交换，中途结束算法