冒泡排序
思想
相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。整个过程如同气泡冒起，因此被称作冒泡排序。
import random
from visual import visualizer
def maopaoSort(arr):
return maopao(arr,len(arr)-1)
def maopao(num,n):
for i in range(n):
#对前一个的数据与后一个的数据进行比较
for j in range(n):
if num[j+1]<num[j]:
visualizer.draw_bars(num, j, j + 1, len(num))
num[j],num[j+1]=num[j+1],num[j]
return num
if __name__ == '__main__':
date = list(range(1, 101))
random.shuffle(date)
visualizer.t.bgcolor('black')
maopaoSort(date)
visualizer.t.done()
快速排序
思想
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以对这两部分记录继续进行排序，以达到整个系列有序。
具体代码
import random
from visual import visualizer
def quicksort(nums):
quicksorthelper(nums,0,len(nums)-1)
return nums
def quicksorthelper(nums,startidex,rightidex):
# 如果列表中只有一个元素或者不存在的话
if startidex>=rightidex:return
# 找出第一个元素为初始值
pivotidex=startidex
privovalue=nums[pivotidex]
# 以第二个元素为左指针
left=startidex+1
# 以第最后元素为右指针
right=rightidex
while left<=right:
# 如果左指针指向的元素大于初始值大于右指针的元素，则说明左指针的值应该和右指针进行替换
if nums[left]>privovalue>nums[right]:
visualizer.draw_bars(nums, left, right, len(nums))
nums[left],nums[right]=nums[right],nums[left]
# 如果左指针的元素小于等于初始值，则不需要替换，只需要将左指针往右移动一位
if nums[left]<=privovalue:
left+=1
# 如果右指针的元素大于等于初始值，则不需要替换，只需要将右指针往左移动一位
if nums[right]>=privovalue:
right-=1
# 调换初始指针和右指针的元素位置，完成一次快速排序
nums[right],nums[pivotidex]=nums[pivotidex],nums[right]
visualizer.draw_bars(nums, pivotidex, right, len(nums))
# 每一次递归操作都需要去额外的开辟存储空间，为了尽可能降低空间复杂度
# 需要先判断左右列表的长短，先对短的进行快速排序，在对长的进行快速排序即可。
leftlength=right-startidex
rightlength=rightidex-right
if leftlength<rightlength:
quicksorthelper(nums,startidex,right-1)
quicksorthelper(nums,right+1,rightidex)
else:
quicksorthelper(nums,right+1,rightidex)
quicksorthelper(nums,startidex,right-1)
if __name__ == '__main__':
date = list(range(1, 101))
random.shuffle(date)
visualizer.t.bgcolor('black')
quicksort(date)
visualizer.t.done()
归并排序
思想
并指将两个或两个以上的有序数表合并成一个新的有序表
步骤
- 将序列中带排序数字分为若干组，每个数字分为一组
- 将若干个组两两合并，保证合并后的组是有序的
- 重复第二步操作直到只剩下一组，排序完成
import random
from visual import visualizer
def merge(nums,left,mid,right):
new_nums=[]
l,r=left,mid+1
while l<=mid and r<=right:
if nums[l]<nums[r]:
new_nums.append(nums[l])
visualizer.draw_bars(nums,l,r,len(nums))
l+=1
else:
new_nums.append(nums[r])
visualizer.draw_bars(nums,l,r,len(nums))
r+=1
while l<=mid:
new_nums.append(nums[l])
visualizer.draw_bars(nums, l, r, len(nums))
l+=1
while r<=right:
new_nums.append(nums[r])
visualizer.draw_bars(nums, l, r, len(nums))
r+=1
nums[left:right+1]=new_nums
def merge_sort(nums,left,right):
if left<right:
mid=(left+right)//2
merge_sort(nums,left,mid)
merge_sort(nums,mid+1,right)
merge(nums,left,mid,right)
visualizer.draw_bars(nums, -1, -1, len(nums))
def run(nums):
l,r=0,len(nums)-1
return merge_sort(nums,l,r)
if __name__ == '__main__':
date=list(range(1,101))
random.shuffle(date)
visualizer.t.bgcolor('black')
run(date)
visualizer.t.done()
插入排序
思想
将给定元素分为两组，开始第一个元素分为一组，后面的元素分为一组，然后通过不断遍历后面的元素不断插入到前面合适的位置。
# 原理：将给定元素分为两组，开始第一个元素分为一组，后面的元素分为一组，然后通过不断遍历后面的元素不断插入到前面合适的位置
import random
from visual import visualizer
# 0（n^2）Time | O(1) Space
# stable
def insert_arr(a):
for i in range(len(a)):
j=i
while j>0 and a[j]<a[j-1]:
visualizer.draw_bars(a,j,j-1,len(a))
a[j],a[j-1]=a[j-1],a[j]
j-=1
return a
if __name__ == '__main__':
date=list(range(1,101))
random.shuffle(date)
visualizer.t.bgcolor('black')
insert_arr(date)
visualizer.t.done()
选择排序
思想
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，继续放在起始位置知道未排序元素个数为0。
#基本原理:第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，继续放在起始位置知道未排序元素个数为0
import random
from visual import visualizer
# 时间复杂度
# 空间复杂度
# 是否稳定
def Selectsort(a):
# 将每一轮的最小值的索引找出来，并放入序列的起始位置
for i in range(len(a)-1):
# key
start_idex=i
for j in range(i+1,len(a)):
# 为了找更小的值
visualizer.draw_bars(a, i, j, len(a))
if a[start_idex]>a[j]:
start_idex=j
# start_idex为我们选出来的最小值索引，i为每一轮的初始值，就进行相应替换即可
a[start_idex],a[i]=a[i],a[start_idex]
visualizer.draw_bars(a, i, start_idex, len(a))
return a
if __name__ == '__main__':
date=list(range(1,20))
random.shuffle(date)
visualizer.t.bgcolor('black')
Selectsort(date)
visualizer.t.done()
桶排序
思想
将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序。
import random
def Tongsort(x):
# 找到数组的最大值和最小值
# 方法1
maxvalue,minvalue=x[0],x[0]
for i in range(1,len(x)):
if x[i]>maxvalue:
maxvalue=x[i]
if x[i]<minvalue:
minvalue=x[i]
# 方法2
# maxvalue,minvalue=max(x),min(x)
# 计算桶的数量
bucketnum=(maxvalue-minvalue)//3+1
bucket=[[]for i in range(bucketnum)]
# 根据数值对桶进行划分
for i in x:
bucket[i//3].append(i)
# 针对每一个桶使用快速排序
for b in bucket:
quicksorthelper(b,0,len(b)-1)
x.clear()
for i in bucket:
x.extend(i)
return x
def quicksorthelper(nums,startidex,rightidex):
# 如果列表中只有一个元素或者不存在的话
if startidex>=rightidex:return
# 找出第一个元素为初始值
pivotidex=startidex
privovalue=nums[pivotidex]
# 以第二个元素为左指针
left=startidex+1
# 以第最后元素为右指针
right=rightidex
while left<=right:
# 如果左指针指向的元素大于初始值大于右指针的元素，则说明左指针的值应该和右指针进行替换
if nums[left]>privovalue>nums[right]:
nums[left],nums[right]=nums[right],nums[left]
# 如果左指针的元素小于等于初始值，则不需要替换，只需要将左指针往右移动一位
if nums[left]<=privovalue:
left+=1
# 如果右指针的元素大于等于初始值，则不需要替换，只需要将右指针往左移动一位
if nums[right]>=privovalue:
right-=1
# 调换初始指针和右指针的元素位置，完成一次快速排序
nums[right],nums[pivotidex]=nums[pivotidex],nums[right]
# 每一次递归操作都需要去额外的开辟存储空间，为了尽可能降低空间复杂度
# 需要先判断左右列表的长短，先对短的进行快速排序，在对长的进行快速排序即可。
leftlength=right-startidex
rightlength=rightidex-right
if leftlength<rightlength:
quicksorthelper(nums,startidex,right-1)
quicksorthelper(nums,right+1,rightidex)
else:
quicksorthelper(nums,right+1,rightidex)
quicksorthelper(nums,startidex,right-1)
if __name__ == '__main__':
date=list(range(1,11))
random.shuffle(date)
b=Tongsort(date)
print(b)
可视化工具
import turtle as t
import random
def draw_bar(x,y,w,h):
t.pu()
t.goto(x,y)
t.pd()
t.seth(0)
t.begin_fill()
t.fd(w)
t.left(90)
t.fd(h)
t.left(90)
t.fd(w)
t.left(90)
t.fd(h)
t.end_fill()
def draw_bars(lst,index1,index2,M):
t.clear()
x=-420
n=len(lst)
# w柱状矩形的宽度
w=830/n
# 矩形的高度
r=650/M
# 不刷新屏幕
t.tracer(0)
# 绘制的时候看不到小箭头
t.ht()
for i in range(n):
if index1==i:
# 显示出特定的idex
t.fillcolor('red')
elif index2==i:
t.fillcolor('blue')
else:
t.fillcolor('white')
draw_bar(x,-385,w,lst[i]*r)
x+=w
t.update()
# t.clear()
# x=-420
# n=len(lst)
# # w柱状矩形的宽度
# w=830/n
# # 矩形的高度
# r=650/M
# # 不刷新屏幕
# t.tracer(0)
# # 绘制的时候看不到小箭头
# t.ht()
# for i in range(n):
# t.fillcolor('green')
# draw_bar(x,-385,w,lst[i]*r)
# x+=w
# t.update()
# lst=list(range(1,101))
# random.shuffle(lst)
# draw_bars(lst,-1,-1,len(lst))
# t.done()
