包括冒泡排序、选择排序、插入排序、快速排序和归并排序。前三者的时间复杂度为O（n*n）,后两者的时间复杂度为O（nlogn），两者的基本思想都是分治和递归。
1. 冒泡排序
def buble_sort(nums):
n=len(nums)
for i in range(n):
## j的边界值需要满足，j+1<n-1.range(n-1)无法取到最后一个值
for j in range(0,n-i-1):
if nums[j]>nums[j+1]:
nums[j],nums[j+1]=nums[j+1],nums[j]
return nums
2. 选择排序。选择一个元素，判断是否是最小的元素。
https://www.runoob.com/python3/python-selection-sort.html
def select_sort(nums):
n=len(nums)
for i in range(n):
min_index=i
for j in range(i+1,n):
if nums[j]<nums[min_index]:
min_index=j
## 只有当位置发生改变时，才交换
if min_index != i:
nums[i],nums[min_index]=nums[min_index],nums[i]
return nums
3. 插入排序。将当前元素插入到已排序的序列的正确的位置
https://www.runoob.com/python3/python-insertion-sort.html
def insert_sort(nums):
n=len(nums)
for i in range(1,n):
j=i
## 若当前元素小于该元素之前的所有元素，先保存当前元素的值，再将其之前的元素逐一后移，最后将该元素放到合适的位置
while j>0:
if nums[j-1]>nums[j]:
nums[j-1],nums[j]=nums[j],nums[j-1]
j -= 1
return nums
## 以下方法较上述方法，交换方式略微不同
def insert_sort2(nums):
n=len(nums)
for i in range(1,n):
key=nums[i]
j=i-1
## 若当前元素小于该元素之前的所有元素，先保存当前元素的值，再将其之前的元素逐一后移，最后将该元素放到合适的位置
while j>=0 and nums[j]>key:
nums[j+1] = nums[j] ## 后移一位
j -= 1
nums[j+1] = key ## 将元素放到正确的位置.注意是j+1
return nums
4. 快速排序。分治和递归的思想结合。时间复杂度是nlogn。
https://blog.csdn.net/weixin_43250623/article/details/88931925
def quick_sort(nums,start,end):
if start >= end: ## 相等，退出递归
return
low,high=start,end
```
中间元素的选取，影响后面比较的顺序。
当mid=nums[low]时，则应先从右往左比较，再从左往右比较。
目的是保证nums[low] 能被替换为正确的元素。如果比较顺序相反，则不能得到正确的结果。
```
mid=nums[low]
## 比mid 元素大的放到右边，比mid元素小的放到左边
while low<high :
while low < high and nums[high]>=mid:
high -= 1
nums[low]=nums[high]
while low < high and nums[low]<mid:
low += 1
nums[high]=nums[low]
nums[low] = mid
## 从基准元素的靠左一位开始递归。此处也不必再比较中间元素mid，因为它已经放到了正确的位置
quick_sort(nums,start,low-1)
quick_sort(nums,low+1,end)
5. 归并排序。也是分治和递归思想的结合，时间复杂度也是nlogn，但是比快排算法需要更多的空间，因为需要另外开辟一个数组。
https://blog.csdn.net/qq_36813467/article/details/88848415
def merge_sort(alist):
if len(alist)<=1:
return alist
mid=len(alist)//2
left=merge_sort(alist[:mid])
right=merge_sort(alist[mid:])
return merge(left,right)
## 需要另开一个列表存储已排序的序列
def merge(left,right):
l,r=0,0
s=[]
while l<len(left) and r<len(right):
if left[l] < right[r]:
s.append(left[l])
l += 1
else:
s.append(right[r])
r += 1
## 将一个列表合并到已有列表，应当使用extend（比+代价更小）。append只是增加一个元素。
s.extend(left[l:]) if l<len(left)
s.extend(right[r:]) if r<len(right)
return s
测试用例：
if __name__ == '__main__':
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(buble_sort(alist))
参考：
https://blog.csdn.net/weixin_41624982/article/details/89486592
网友评论