1. 冒泡排序
平均时间复杂度：O(n^2)
稳定性：不稳定
思路：以第一个元素为基准开始与相邻的元素比较，让无序列表中最大的元素一直像右移动（冒泡上升）
bad_list= [7,9,3,1,0,5,4,2,8,6]
def bubble_sort(bad_list):
length = len(bad_list)
for i in range(length-1):
for j in range(length-1-i): #有序列表长度在增加
if bad_list[j] > bad_list[j+1]:
bad_list[j], bad_list[j+1] = bad_list[j+1], bad_list[j]
return bad_list
bubble_sort(bad_list)
2. 选择排序
平均时间复杂度：O(n^2)
稳定性：不稳定
举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法
思路：记录无序列表中最小的元素，然后与无序列表的表头元素交换
bad_list= [7,9,3,1,0,5,4,2,8,6]
def select_sort(bad_list):
length = len(bad_list)
for i in range(length):
min_idx = i #假设最小元素的下标
for j in range(i,length-1):
if bad_list[j+1] < bad_list[min_idx]:
min_idx = j + 1 #注意不是 min_idx += 1
bad_list[i], bad_list[min_idx] = bad_list[min_idx], bad_list[i]
return bad_list
select_sort(bad_list)
3. 直接插入排序
平均时间复杂度：O(n^2)
稳定性：稳定
思路：不断地从头到尾逐渐增加有序列表的长度，将无序列表中第一个元素插入到有序列表中的正确位置
bad_list= [7,9,3,1,0,5,4,2,8,6]
def insert_sort(bad_list):
length = len(bad_list)
for i in range(length):
while i>=1:
if bad_list[i] < bad_list[i-1]:
bad_list[i], bad_list[i-1] = bad_list[i-1], bad_list[i]
i -= 1
return bad_list
insert_sort(bad_list)
4. 希尔排序
平均时间复杂度：O(nlogn)
稳定性：不稳定
思路：是直接插入排序的改良版，由大块变小块，对块与块之间的相对位置进行排序，相对位置的计算引入了gap变量
bad_list= [7,9,3,1,0,5,4,2,8,6]
def shell_sort(bad_list):
length = len(bad_list)
gap = length // 2
while gap >= 1:
for i in range(gap,length):
while i>=1:
if bad_list[i] < bad_list[i-gap]:
bad_list[i], bad_list[i-gap] = bad_list[i-gap], bad_list[i]
i -= gap
gap = gap // 2
return bad_list
shell_sort(bad_list)
5. 快速排序
平均时间复杂度：O(nlogn)
稳定性：不稳定
思路：大块变小块，并用前后指针。每一次排序都有一个元素作为标准值，比他大的在它右边，比他小的在它左边。
bad_list= [7,9,3,1,0,5,4,2,8,6]
def quick_sort(bad_list,start,end):
length = len(bad_list)
mid = bad_list[start]
low = start
high = end
if low >= high:
return
while low < high:
while low < high and bad_list[high] >= mid: #注意条件
high -= 1
bad_list[low] = bad_list[high]
while low < high and bad_list[low] <= mid:
low += 1
bad_list[high] = bad_list[low]
bad_list[low] = mid
quick_sort(bad_list,start,low-1)
quick_sort(bad_list,low+1,end)
return bad_list
quick_sort(bad_list,0,len(bad_list)-1)
6.归并排序
平均复杂度：O(nlogn)
稳定性：稳定
思路：分治(先分再排序)，先分成小块，然后再合并，合并的过程中进行排序。
bad_list= [7,9,3,1,0,5,4,2,8,6]
def merge_sort(bad_list):
length = len(bad_list)
if length <= 1:
return bad_list
mid = length // 2
left = merge_sort(bad_list[:mid])
right = merge_sort(bad_list[mid:])
return merge(left,right)
def merge(left,right):
result = []
while len(left) > 0 and len(right)> 0:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result += left
result += right
return result
merge_sort(bad_list)
```ddddd
网友评论