跳舞演示排序 https://zhuanlan.zhihu.com/p/49271189
1. 冒泡排序
时间复杂度: O(n^2)
空间复杂度: O(1)
def bubble_sort(nums):
for i in range(len(nums) - 1):
for j in range(len(nums) - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
2. 选择排序
时间复杂度: O(n^2)
空间复杂度: O(1)
def select_sort(lis):
for i in range(len(lis)-1):
min_loc = i
for j in range(i + 1, len(lis)):
if lis[j] < lis[min_loc]:
min_loc = j
if min_loc != i:
lis[i], lis[min_loc] = lis[min_loc], lis[i]
3. 归并排序
时间复杂度: O(nlogn)
空间复杂度: O(n)
# 分离后的有序列表合并
def marge(nums, left, mid, right):
i = left
j = mid + 1
ltmp = []
# 取出两个列表的第一个值, 对比, 小的放到新的列表中, 再往后挪一位继续
while i <= mid and j <= right:
if nums[i] < nums[j]:
ltmp.append(nums[i])
i=i+1
else:
ltmp.append(nums[j])
j=j+1
# 下面两个while循环处理当其中一个列表数据处理完成后另一个列表剩下的数据
while i <= mid:
ltmp.append(nums[i])
i+=1
while j <=right:
ltmp.append(nums[j])
j+=1
# 将新列表覆值盖原列表值
nums[left:right+1]=ltmp
# 拆分列表
def mergesort(nums, left, right):
if left < right:
mid = (left + right) // 2
mergesort(nums, left, mid)
mergesort(nums, mid + 1, right)
marge(nums, left, mid, right)
# left 为最左边的索引值
# mid 为切分点(中间)的索引值
# right为最右边的索引值
4. 快速排序
时间复杂度: O(nlogn)
空间复杂度: O(1)
def partition(nums, left, right):
tmp = nums[left]
while left < right:
while left < right and tmp <= nums[right]:
right -= 1
nums[left] = nums[right]
while left < right and tmp >= nums[left]:
left += 1
nums[right] = nums[left]
nums[left] = tmp
return left
def quick_sort(nums, left, right):
if left < right:
mid = partition(nums, left, right)
quick_sort(nums, left, mid-1)
quick_sort(nums, mid + 1, right)
5. 计数排序
时间复杂度: O(nlogn)
空间复杂度: O(1)
def count_sort(li, max_num):
count = [0 for i in range(max_num + 1)]
for num in li:
count[num] += 1
i = 0
for num,m in enumerate(count):
for j in range(m):
li[i] = num
i += 1
6. 插入排序
时间复杂度: O(n^2)
空间复杂度: O(1)
def insert_sort(li):
for i in range(1, len(li)):
tmp = li[i]
j = i - 1
while j >= 0 and tmp < li[j]:
li[j + 1] = li[j]
j = j - 1
li[j + 1] = tmp
