上海网站运营,wordpress代码,大型网站域名,衡阳网站优化方案目录
常见的三种排序方法
冒泡排序
插入排序
选择排序
其他经典的排序方法
快速排序
堆排序
归并排序 希尔排序 不同排序方法的各维度对比 排序方式的稳定性#xff1a;若两个相同的元素在排序前后的相对位置不发生改变的排序为稳定排序#xff0c;否则不稳定排序 常…目录
常见的三种排序方法
冒泡排序
插入排序
选择排序
其他经典的排序方法
快速排序
堆排序
归并排序 希尔排序 不同排序方法的各维度对比 排序方式的稳定性若两个相同的元素在排序前后的相对位置不发生改变的排序为稳定排序否则不稳定排序 常见的三种排序方法
以【3,2,2,1,1】为例
冒泡排序 冒泡排序思路不断地对比相邻的两个元素将若前面的元素 大于注意不含等于) 后面的元素则两个元素进行位置交换。 # 冒泡排序复杂度为O(n^2)
def bubble_sorted(li:list)-list:for i in range(len(li)):# 第几趟exchanged False# 这个是为了防止多余的遍历如果前面的元素已经是排序好的那就不需要再进行比较了减少运行时间for j in range(len(li)-1):# 遍历列表元素if li[j] li[j1]:li[j],li[j1] li[j1],li[j]exchanged Trueif not exchanged:return li第一趟
3212211122(1)32(211122(1)2(2)31(1)1(2)2(1)2(2)1(1)31(2)2(1)2(2)1(1)1(2)3
第二趟
第三趟
第四趟 、第五趟、第六趟 可见在经过冒泡排序后相同元素的相对前后位置没有发生改变 因此排序是稳定的。 插入排序 插入排序的思路从左到右分为有序区和无序区每次都是将无序区的第一个元素取出插入到有序区间中。然后从右往左遍历有序区当遍历的有序元素大于该元素时有序元素右移一位继续遍历有序区直到遍历的有序元素小于等于无序区元素第一个元素时停止遍历并且将该元素插入到停止遍历有序元素的后一个位置 # 插入排序复杂度为O(n^2)思路是从左到右抽取一个元素将这个元素与左边邻近的元素比较若比左边的小则左边元素右移
# 若不比左边的小了或者已经到最左边了则将抽取的元素赋值给原本左边元素
def insert_sorted(li:list)-list:for i in range(1,len(li)):# 趟数也就是抽牌的顺序从第一张牌开始抽tmp li[i]j i - 1# 左边元素while j 0 and li[i] li[j]:# 若抽取的元素小于邻近左边的元素则将左边元素右移一格li[j1] li[j]j - 1# 这时候的j已经不满足上述条件了因此这个j位置上的元素没有移动而j1上位置的元素移动了是空的li[j1] tmpreturn li
3212211122(1)32(211122(1)2(2)31(1)1(2)1(1)2(1)2(2)31(2)1(1)1(2)2(1)2(2)3可见在经过插入排序后相同元素的相对前后位置没有发生改变 因此排序是稳定的。 选择排序 选择排序的思路分为有序区和无序区每次将无序区的最小元素放在无序区的第一个位置期间会发生元素的交换 # 选择排序复杂度为O(n^2)思路是遍历一趟元素后选择最小的值放在无序区的第一位
def select_sorted(li:list)-list:for i in range(len(li)):min_loc i# 初始化最小值的位置为第一个for j in range(i1,len(li)-1):if li[j]li[min_loc]:li[j],li[min_loc] li[min_loc],li[j]# 交换元素return li 第一趟
3212211122(1)32(211122(1)32(2)1(1)1(2)1(1)32(2)2(1)1(2)
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。 在第一趟的选择排序种我们可以看到相同元素21和22的相对位置在排序前后发生了变化因此是不稳定排序。 其他经典的排序方法
快速排序 快排的思路先取序列首元素作为基准值将序列中小于基准值的元素放在左边大于基准值的元素放在右边相等的元素放在任一边均可。然后以该基准值作为边界对左右子序列递归进行快速排序即可实现排序 具体步骤 1选择序列首元素作为基准值左指针指向序列首位右指针指向序列尾部 2若右指针的元素值大于基准值右指针继续左移否则将右指针指向的元素赋值给左指针 3赋值完后移动左指针若左指针的元素小于基准值左指针右移否则将左指针指向的元素赋值给右指针处 4重复23直到左右指针重合将基准值赋值给重合的位置 5对左右子序列递归使用1-4步骤这样就实现了对序列的快速排序递归终止条件为序列含有1个元素即leftright这里保证有两个元素的时候进行递归否则退出 def partition(li:list,left:int,right:int)-int:这是根据路飞商城的思路来的将p元素归位的函数取第一个元素为p元素移动right若right指针的值大于P,则right继续往左移动否则停止移动将值赋值给left所在的位置然后再移动left若left指针的值小于P,则left继续往右移动否则停止移动将值赋值给right所在的位置如此交替移动直到leftright时停止并将P值赋值给leftright:param li: 需要归位的列表:param left: 列表左指针索引初始值为0:param right: 列表右指针索引初始值为len(li-1:return: 返回p归位的索引#得到要归位的元素第一个元素p li[left]#当列表有两个元素时才进行排序while left right:# 保证有两个元素#这里我们从列表的右边开始进行元素的比较while left right and p li[right]: # 至少两个元素并且p元素值小于等于right指针指向的值时右指针左移right - 1 # right 左移一步li[left] li[right] # 不满足上述循环条件时停止移动right并且将right上的值赋值给left#右指针停止移动后开始进行左指针的移动while left right and p li[left]:left 1li[right] li[left]#当left right时说明已经归位了将p赋值给归位位置li[left] preturn leftdef quickSorted(li,left,right):对列表进行快排:param li: 需要排序的列表:param left: 左索引:param right: 右索引:return: 返回排好序的列表if left right:mid partition(li, left, right) # 首先得到第一个归位索引# 对左边列表进行排序quickSorted(li,left,mid-1)# 对右边列表进行排序quickSorted(li,mid 1,right) 第一趟
基准值p 5
541942854194284241942842419984241598由上面可以看出在进行一趟排序后两个4的相对位置发生了改变因此快速排序是不稳定的 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
堆排序
堆排序是利用了二叉树的数据结构来实现的稳定排序
归并排序 归并排序的思路将两个有序序列利用双指针进行合并 难点如何将待排序的序列变成两个有序序列当元素只有一个的时候序列是有序的这个是比较容易理解的。因此这里利用递归的方式先将列表拆成一个个单元素列表然后再一个个元素有序序列合并回溯即可实现排序 归并排序的主要思路将两个有序的子列表归并为一个有序的大列表
#归并函数假设li是由左右两个有序的子列表组成,假设两个子列表都是从小到大排好序的列表
def merge(li,low,mid,high)::param li: 由左右两个有序的子列表组成的大列表:param low: 列表的起始索引:param mid: 两个子列表的分解处的索引这里取前面子列表的最后一个元素的索引为mid:param high: 大列表最后一个索引:return: 从小到大排序的列表# 当列表中有两个元素时进行归并操作i low # 第一个子列表的起始索引j mid 1 # 第二个子列表的起始索引比较好了的元素lTmp [] # 用于保存while i mid and j high: # 当两个子列表都没有遍历完时if li[i] li[j]:lTmp.append(li[j])j 1else:lTmp.append(li[i])i 1while i mid:# 当右列表访问结束后直接将左列表进行添加lTmp.append(li[i])i 1while j high:lTmp.append(li[j])j 1li[low:high1] lTmp#归并排序
def mergeSorted(li,low,high)::param li: 列表:param low: 列表起始索引:param high: 列表结束索引:return: if low high: # 保证列表有两个元素mid (low high)//2mergeSorted(li,low,mid) # 对左列表进行排序mergeSorted(li,mid1,high) # 对右列表进行排序merge(li,low,mid,high) # 将排好序的两个列表进行归并 归并排序是稳定排序方式因为在进行有序列表的合并时这里看成左右子序列的合并只有当左序列中的元素大于右子序列的元素的时候才会将右子序列的元素添加到列表中这也就保证了在左右序列中有相等元素时会先将左序列的元素存放在列表中然后再将右序列的元素存放在列表中 希尔排序 希尔排序思路希尔排序的思路其实和归并排序是类似的都是利用分治的方法实现不同的是归并排序是另开一个数组来合并两个有序的序列进而实现序列的排序而希尔排序则是利用插入的方式将两个子序列合并在一起在序列原地进行修改。 希尔排序将列表分成多组对每一组进行插入排序最后合并在一起d1len//2,did(i-1)//2,直到di1,退出
def insert_sorted_shell(li:list,gap:int)-list::param li: 列表:param gap: 分组的组数和每个元素在大列表中的间隔:return: for i in range(gap,len(li)):# 趟数也就是抽牌的顺序从第一张牌开始抽tmp li[i]j i - gap# 左边元素while j 0 and li[i] li[j]:# 若抽取的元素小于邻近左边的元素则将左边元素右移一格li[jgap] li[j]j - gap# 这时候的j已经不满足上述条件了因此这个j位置上的元素没有移动而j1上位置的元素移动了是空的li[jgap] tmpreturn lidef shellSorted(li):n len(li)d n//2while d 1:insert_sorted_shell(li,d)d // 2 注意快速排序、归并排序的左右索引都是闭区间 不同排序方法的各维度对比
排序方法冒泡排序插入排序选择排序快速排序归并排序希尔排序稳定性稳定稳定不稳定不稳定稳定稳定时间复杂度O(n^2)O(n^2)O(n^2)O(nlgn)O(nlogn)O(n^(3/2) )空间复杂度O(1)O(1)O(1)O(1)O(n)O(1)从时间复杂度性能上来说一般选择快速排序是一种排序比较快的排序方法 从稳定性来说一般选择的是归并排序
