冒泡排序
思想
相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。整个过程如同气泡冒起，因此被称作冒泡排序。
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()
桶排序
思想
将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序。
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)
选择排序
思想
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，继续放在起始位置知道未排序元素个数为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()
练习-基础难度
451. Sort Characters By Frequency (Medium)
桶排序的变形题。
题目描述
给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案，返回其中任何一个。
输入输出样例
输入: s = "tree"
输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
具体代码
"""
解题1：通过桶排序来做
执行用时：56 ms, 在所有 Python 提交中击败了35.11%的用户
内存消耗：28.6 MB, 在所有 Python 提交中击败了5.34%的用户
"""
def frequencySort(s):
# 统计各元素的频率
dic=dict()
for i in s:
dic[i]=dic.get(i,0)+1
# 设置桶的数量
buckets=[[]for _ in range(len(s)+1)]
for key,value in dic.items():
buckets[value].append(key)
res=""
for j in range(len(s),-1,-1):
if buckets[j]:
if len(buckets[j])!=1:
for k in buckets[j]:
res+=''.join(k*j)
else:
res += ''.join(buckets[j] * j)
return res
"""
解题2:直接调用Counter进行计算
执行用时：44 ms, 在所有 Python 提交中击败了60.44%的用户
内存消耗：14.9 MB, 在所有 Python 提交中击败了76.00%的用户
"""
from collections import Counter
def frequencySort1(s):
a=Counter(s).most_common()
res=''
for k,v in a:
res+=''.join(k*v)
return res
if __name__ == '__main__':
s = "tree"
a=frequencySort1(s)
print(a)
练习-进阶难度
75. Sort Colors (Medium)
很经典的荷兰国旗问题，考察如何对三个重复且打乱的值进行排序。
题目描述
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
输入输出样例
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
具体代码
"""
解题1：
执行用时： 12ms, 在所有 Python 提交中击败了94.81的用户
内存消耗： 12.8MB, 在所有 Python 提交中击败了94.34的用户
"""
def sortColors(nums):
sum_0,sum_1=0,0
for num in nums:
if num==0:
sum_0+=1
elif num==1:
sum_1+=1
for i in range(len(nums)):
if i<sum_0:
nums[i]=0
elif i<(sum_0+sum_1):
nums[i]=1
else:
nums[i]=2
return nums
if __name__ == '__main__':
nums = [2, 0, 2, 1, 1, 0]
result = sortColors(nums)
print(result)
