一、插入排序
def InsertSort(lst, n):
'''
插入排序(升序排列)
思想：在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。直到整个序列有序
:param lst: 待排序数组
:param n: 数组长度
:return: 排序好的数组
'''
for i in range(n - 1):
# 记录有序序列最后一个元素的下标
index = i
# 待插入的元素
insert = lst[index + 1]
# 单趟排--每次比较时不是互换位置，而是大的6往后移一位，原位置仍是大的6，直到找到应插入的位置，将其插入
# 这样数列中后持续保持多出一个重复的大数字，但是在最后找到插入位置后，多出来的会被消去
while index >= 0:
# 比插入的数大就向后移
if insert < lst[index]:
lst[index + 1] = lst[index]
index -= 1
# 找到应插入的位置，结束小循环
else:
break
lst[index + 1] = insert
return lst
def main():
n = int(input())
lst = list(map(int, input().split()))
lst = InsertSort(lst, n)
print(lst)
if __name__ == "__main__":
main()
#时间复杂度：最好O(N),最坏O(N*N)
#空间复杂度：O(1) 二、哈希排序
# 希尔排序
def ShellSort(lst, n):
gap = n
while gap > 1:
# 每次对gap折半操作
gap = gap / 2
# 单趟排序
for i in (n - gap):
index = i
tem = lst[index + gap]
while index >= 0:
if tem < lst[index]:
lst[index + gap] = lst[end]
index -= gap
else:
break
lst[index + gap] = tem
def main():
n = int(input())
lst = list(map(int, input().split()))
lst = ShellSort(lst, n)
print(lst)
if __name__ == "__main()__":
main()
# 时间复杂度：平均O(N^1.3)
# 空间复杂度：O(1) 三、选择排序
def SelectionSort(lst, n):
'''
选择排序:每次未排序好部分的最小最大值排到已排序好部分的后面
:param lst:
:param n:
:return:
'''
for i in range(n):
min_index = i
for j in range(i + 1, n):
if lst[j] < lst[min_index]:
min_index = j
lst[i], lst[min_index] = lst[min_index], lst[i]
return lst
def main():
n = int(input())
lst = list(map(int, input().split()))
lst = SelectionSort(lst, n)
print(lst)
if __name__ == "__main__":
main()
一趟比较同时排好最小的和最大的
def SelectionSort(lst, n):
'''
选择排序：一趟排序排出一个最小的和一个最大的
:param lst:
:param n:
:return:
'''
# 保存参与单趟排序的第一个数和最后一个数的下标
begin, end = 0, n - 1
while begin < end:
max_index = begin
min_index = begin
for i in range(begin, end + 1):
if lst[i] < lst[min_index]:
min_index = i
if lst[i] > lst[max_index]:
max_index = i
lst[begin], lst[min_index] = lst[min_index], lst[begin]
# 防止最大的数在begin位置被换走
if begin == max_index:
max_index = min_index
lst[end], lst[max_index] = lst[max_index], lst[end]
begin += 1
end -= 1
return lst
def main():
n = int(input())
lst = list(map(int, input().split()))
lst = SelectionSort(lst, n)
print(lst)
if __name__ == "__main__":
main()
#时间复杂度： 最好O(N^2) 最坏O(N^2)
#空间复杂度： O(1)四、冒泡排序
def BubbleSort(lst, n):
end = n
while end > 0:
# 用于判断是否有交换，若一趟循环一次交换都没有，则说明前面的已经排序好了
flat = 0
for i in range(1, end):
if lst[i - 1] > lst[i]:
lst[i - 1], lst[i] = lst[i], lst[i - 1]
flag = 1
if flag == 0:
break
end -= 1
return lst
def main():
n = int(input())
lst = list(map(int, input().split()))
lst = BubbleSort(lst, n)
print(lst)
if __name__ == "__main__":
main()