1.冒泡排序
def bubble_sort(A):
n = len(A)
for j in range(n-1):
count = 0
for i in range(n-1-j):
if A[i] > A[i+1]:
A[i], A[i+1] = A[i+1], A[i]
count += 1
if count == 0:
return
if __name__ == '__main__':
data = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(data)
bubble_sort(data)
print(data)
2.选择排序
def select_sort(A):
n = len(A)
for j in range(n-1):
min_index = j
for i in range(j+1, n):
if A[min_index] > A[i]:
min_index = i
A[j], A[min_index] = A[min_index], A[j]
if __name__ == '__main__':
data = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(data)
select_sort(data)
print(data)
3.插入排序
def insert_sort(A):
n = len(A)
for j in range(1, n):
i = j
while i > 0:
if A[i] < A[i-1]:
A[i], A[i-1] = A[i-1], A[i]
i -= 1
else:
break
if __name__ == '__main__':
data = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(data)
insert_sort(data)
print(data)
4.希尔排序(带间隔的插入排序)
def shell_sort(A):
n = len(A)
gap = n//2
while gap >0:
for j in range(gap, n):
i = j
while i>0:
if A[i] < A[i - gap]:
A[i], A[i-gap] = A[i-gap], A[i]
i -= gap
else:
break
gap //= 2
if __name__ == '__main__':
data = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(data)
shell_sort(data)
print(data)
5.快速排序
def quick_sort(A,first, last):
if first >= last:
return
mid_value = A[first]
low = first
high = last
while low < high:
while low < high and A[high] >= mid_value:
high -= 1
A[low] = A[high]
while low < high and A[low] < mid_value:
low += 1
A[high] = A[low]
A[low] = mid_value
quick_sort(A, first, low - 1)
quick_sort(A, low + 1, last)
if __name__ == '__main__':
data = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(data)
lens = len(data)
quick_sort(data, 0, lens-1)
print(data)
6.归并排序
def merge_sort(A):
n = len(A)
if n <= 1:
return A
mid = n // 2
left_A = merge_sort(A[:mid])
right_A = merge_sort(A[mid:])
left_pointer, right_pointer = 0, 0
result = []
while left_pointer < len(left_A) and right_pointer < len(right_A):
if left_A[left_pointer] < right_A[right_pointer]:
result.append(left_A[left_pointer])
left_pointer += 1
else:
result.append(right_A[right_pointer])
right_pointer += 1
result += left_A[left_pointer:]
result += right_A[right_pointer:]
return result
if __name__ == '__main__':
data = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(data)
lens = len(data)
datas = merge_sort(data)
print(datas)
- 根据问题进行编码,由于数组下标是从0开始的,而树的节点从1开始,我们还需要引入一个辅助位置,Python提供的原始数据类型list实际上是一个线性表(Array),由于我们需要在序列最左边追加一个辅助位,线性表这样做的话开销很大,需要把数组整体向右移动,所以list类型没有提供形如appendleft的函数,但是在一个链表里做这种操作就很简单了,Python的collections库里提供了链表结构deque,我们先使用它初始化一个无序序列
from collections import deque
def swap_param(L, i, j):
L[i], L[j] = L[j], L[i]
return L
def heap_adjust(L, start, end):
temp = L[start]
i = start
j = 2 * i
while j <= end:
if (j < end) and (L[j] < L[j + 1]):
j += 1
if temp < L[j]:
L[i] = L[j]
i = j
j = 2 * i
else:
break
L[i] = temp
def heap_sort(L):
L_length = len(L) - 1
first_sort_count = L_length // 2
for i in range(first_sort_count):
heap_adjust(L, first_sort_count - i, L_length)
for i in range(L_length - 1):
L = swap_param(L, 1, L_length - i)
heap_adjust(L, 1, L_length - i - 1)
return [L[i] for i in range(1, len(L))]
def main():
L = deque([50, 16, 30, 10, 60, 90, 2, 80, 70])
L.appendleft(0)
print(heap_sort(L))
if __name__ == '__main__':
main()