冒泡排序以及堆排序的实现

完成时间：大二上

问题建模

冒泡排序：通过对一个列表进行两两比较并交换次序来达到排序的目的

for i in range(arr.len-1):
    for j in range(arr.len-1):
        if arr[j] > arr[j+1]:
            a = arr[j+1]
            arr[j+1] =arr[j]
            arr[j] = a

堆排序：
先建立一个完全二叉树，再对其左右节点赋值，使其满足“堆”的定义
建立二叉树:

largest = i  
l = 2 * i + 1     # left = 2*i + 1 
r = 2 * i + 2     # right = 2*i + 2 

构建堆：

if l < n and arr[i] < arr[l]: 
    largest = l 
  
if r < n and arr[largest] < arr[r]: 
    largest = r 
  
if largest != i: 
    arr[i],arr[largest] = arr[largest],arr[i]   
  
    heapify(arr, n, largest) 

排序部分：

def heapSort(arr): 
n = len(arr) 
  
# Build a maxheap. 
for i in range(n, -1, -1): 
    heapify(arr, n, i) 
  
# 一个个交换元素
for i in range(n-1, 0, -1): 
    arr[i], arr[0] = arr[0], arr[i]   # 交换
    heapify(arr, i, 0) 
  
heapSort(L) 

源码

冒泡排序：

print("----——冒泡排序——----")
n = (input("请输入元素个数："))
L = []
for i in range(int(n)):
    L.append(int(input("请输入第"+str(i+1)+"个整数；")))
print("当前列表为:",end=’ ‘)
print(L)
for i in range(int(n)-1):
    for j in range(int(n)-1):
        if L[j] > L[j+1]:
            a = L[j+1]
            L[j+1] = L[j]
            L[j] = a
print("排序结果为:",end=’ ’)
print(L)

堆排序：

print("-----——堆排序——-----")
n = (input("请输入元素个数："))
L = []
for i in range(int(n)):
    L.append(int(input("请输入第"+str(i+1)+"个整数；")))
print("当前列表为:",end=’ ’)
print(L)

def heapify(arr, n, i): 
    largest = i  
    l = 2 * i + 1     # left = 2*i + 1 
    r = 2 * i + 2     # right = 2*i + 2 
  
    if l < n and arr[i] < arr[l]: 
        largest = l 
  
    if r < n and arr[largest] < arr[r]: 
        largest = r 
  
    if largest != i: 
        arr[i],arr[largest] = arr[largest],arr[i]  # 交换
  
        heapify(arr, n, largest) 
  
def heapSort(arr): 
    n = len(arr) 
  . 
    for i in range(n, -1, -1): 
        heapify(arr, n, i) 
  
    # 一个个交换元素
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i]   # 交换
        heapify(arr, i, 0) 
  
heapSort(L) 
n = len(L) 
print("排序结果为:",end=’ ’)
print(L)

说明

本实验完成于大二上学期（2021下半年），所使用语言为Python