最近面试中经常考察排序算法，所以这里用python实现一下常用的排序算法。
1、直接插入排序
"""插入排序"""
def insertion_sort(a_list):
for index in range(1,len(a_list)):
current_value = a_list[index]
#这里不能减1
position = index
# 这里比较的是前一个位置的值
while position > 0 and a_list[position - 1]> current_value:
a_list[position] = a_list[position - 1]
position -= 1
a_list[position] = current_value
def insertion_sort_binarysearch(a_list):
for index in range(1,len(a_list)):
low = 0
high = index - 1
current_value = a_list[index]
position = index
while low<=high:
middle = (low+high)//2
if a_list[middle] > current_value:
high = middle -1
else:
low = middle + 1
while position > low:
a_list[position] = a_list[position - 1]
position -= 1
a_list[low] = current_value
a_list = [54, 26, 93, 15, 77, 31, 44, 55, 20]
insertion_sort(a_list)
print(a_list)
insertion_sort_binarysearch(a_list)
print(a_list)
2、冒泡排序
def short_bubble_sort(a_list):
pass_num = len(a_list)-1
exchanges = True
while pass_num > 0 and exchanges:
exchanges = False
for i in range(pass_num):
if a_list[i] > a_list[i+1]:
a_list[i],a_list[i+1] = a_list[i+1],a_list[i]
exchanges = True
pass_num -= 1
3、选择排序
"""选择排序"""
def selection_sort(a_list):
for fill_slot in range(len(a_list)-1,0,-1):
max_index = 0
for i in range(1,fill_slot+1):
if a_list[i] > a_list[max_index]:
max_index=i
a_list[max_index],a_list[fill_slot] = a_list[fill_slot],a_list[max_index]
if __name__ == '__main__':
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
selection_sort(a_list)
print(a_list)
4、归并排序
def merge_sort(a_list):
print("Splitting ", a_list)
if len(a_list) > 1:
mid = len(a_list)//2
left_half = a_list[:mid]
right_half = a_list[mid:]
merge_sort(left_half)
merge_sort(right_half)
i=0
j=0
k=0
while i<len(left_half) and j<len(right_half):
if left_half[i] < right_half[j]:
a_list[k]=left_half[i]
i+=1
k+=1
else:
a_list[k] = right_half[j]
j+=1
k+=1
while i<len(left_half):
a_list[k]=left_half[i]
i+=1
k+=1
while j<len(right_half):
a_list[k] = right_half[j]
j+=1
k+=1
print ('Mergeing',a_list)
5、希尔排序
def shell_sort(a_list):
#how many sublists, also how many elements in a sublist
sublist_count = len(a_list) // 2
while sublist_count > 0:
for start_position in range(sublist_count):
gap_insertion_sort(a_list, start_position, sublist_count)
print("After increments of size", sublist_count, "The list is", a_list)
sublist_count = sublist_count // 2
def gap_insertion_sort(a_list, start, gap):
#start+gap is the second element in this sublist
for i in range(start + gap, len(a_list), gap):
current_value = a_list[i]
position = i
while position >= gap and a_list[position - gap] > current_value:
a_list[position] = a_list[position - gap] #move backward
position = position - gap
a_list[position] = current_value
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20, 88]
shell_sort(a_list)
print(a_list)
6、快速排序
def quick_sort(a_list):
quick_sort_helper(a_list,0,len(a_list)-1)
def quick_sort_helper(a_list,first,last):
if first<last:
split_point = partition(a_list,first,last)
quick_sort_helper(a_list,0,split_point-1)
quick_sort_helper(a_list,split_point+1,last)
def partition(a_list,first,last):
pivot_value = a_list[first]
left_mark=first+1
right_mark=last
done = False
while not done:
while left_mark <= right_mark and a_list[left_mark] <= pivot_value:
left_mark+=1
while a_list[right_mark] >= pivot_value and right_mark >= left_mark:
right_mark -= 1
if right_mark < left_mark:
done = True
else:
a_list[right_mark],a_list[left_mark] = a_list[left_mark],a_list[right_mark]
a_list[first],a_list[right_mark] = a_list[right_mark],a_list[first]
return left_mark
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
my_quick_sort(a_list)
print(a_list)
7、堆排序
def perceDown(a_list,i,N):
temp = a_list[i]
while (2*i + 1) < N:
child = 2 * i + 1
if child < N - 1 and a_list[child+1] > a_list[child]:
child = child + 1
if temp < a_list[child]:
a_list[i] = a_list[child]
i = child
else:
break
a_list[i] = temp
def heap_sort(a_list,N):
for i in range(N//2,-1,-1):
perceDown(a_list,i,N)
for i in range(N-1,-1,-1):
a_list[0],a_list[i] = a_list[i],a_list[0]
perceDown(a_list,0,i)
if __name__ == '__main__':
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
heap_sort(a_list,9)
print(a_list)
