用python实现常用排序算法（二）
文章目录
用python实现常用排序算法（二）
前言一. 希尔排序1）实现代码2）算法的简介及流程图3）算法的难点
二. 归并排序1）实现代码2）算法的简介及流程图3）算法的难点
总结
前言
今天带大家利用Python，写希尔排序以及归并排序的排序算法，比上次咋们说的排序算法在一定程度下快些。
一. 希尔排序
1）实现代码
希尔排序，是根据step一步一步的进行排序，首先先上代码:
def shell_sort(list1
):
count
= len(list1
)
step
= count
// 2
while step
> 0 :
for i
in range(step
,count
):
for j
in range(i
, 0 , -step
):
if list1
[j
] < list1
[j
- step
]:
list1
[j
],list1
[j
-step
] = list1
[j
-step
] , list1
[j
]
step
= step
// 2
return list1
注意我这里使用的是从小到大排序哦，想从大到小排序的，请把所有有关判断大小的操作倒过来即可。
2）算法的简介及流程图
希尔排序其实可以看做是插入排序的特殊版本。只不过不像插入排序那样找的是之前未排序的部分，而是根据步长step，将对应的值插入list1[i - step] , list1[i - 2*step]中。这里的步长首先取的是list1长度的一半，你也可以根据自己的需要取其他的值（一般来说都是直接取整体列表长度的一半），之后每次做完一次循环，就会将step缩小为原来的1/2。
算法的流程图如下：
3）算法的难点
难点1: python地板除 // ,可以得到一个整数 难点2::for i in range(step,count) ，为什么不从0开始 我们是把list1[i]插入list1[i - step] , list1[i - 2 * step] 的，小于step的值，前面是没有对应的值。 难点3:for j in range(i , 0 , -step) 这句话其实等于 for(int j = i ; j >= step ; j -= step) python的语法决定 range 是左闭右开的 难点4: 还是上面那句话,为什么不是到step的开始位置结束呢? 请注意一下,我们进行比较的是 j 和 j-step ,其实已经把开始位置算在内了,再进行比较的话就会有数组的越界了哦 难点5: 为什么要step >0 结束呢 数组的长度如果是偶数的话，是step = 2,奇数的话step = 1, 结束后所有的数字都已经排好了
二. 归并排序
1）实现代码
是按照从小到大顺序进行排列的，先看看代码:
def merge_sort(mergelist1
,mergelist2
):
restart
= []
mergelist_i
= 0
mergelist_j
= 0
countmergelist1
= len(mergelist1
)
countmergelist2
= len(mergelist2
)
while mergelist_i
< len(mergelist1
) and mergelist_j
< len(mergelist2
):
if mergelist1
[mergelist_i
] < mergelist2
[mergelist_j
]:
restart
.append
(mergelist1
[mergelist_i
])
mergelist_i
= mergelist_i
+ 1
else:
restart
.append
(mergelist2
[mergelist_j
])
mergelist_j
= mergelist_j
+ 1
if mergelist_i
== countmergelist1
:
restart
.extend
(mergelist2
[mergelist_j
:])
if mergelist_j
== countmergelist2
:
restart
.extend
(mergelist1
[mergelist_i
:])
return restart
def mergesort(list1
):
count
= len(list1
)
if count
< 2:
return list1
mid
= count
// 2
mergelist1
= mergesort
(list1
[0:mid
])
mergelist2
= mergesort
(list1
[mid
:])
return merge_sort
(mergelist1
,mergelist2
)
2）算法的简介及流程图
归并排序，讲究的就是分离之后再合并，首先不断不断进行分离，直到分离出最小的单元，然后通过最小的单元进行合并。 1）如何分离：左右两边同时开工 , 利用mid中间值不断地对列表进行分割 2）如何合并:因为分开按照的是左右两边分开的嘛，所以合并也得按照左右两边进行合并，如果左边的值小于右边的值，那么就把右边的值放到你设定的存放答案的列表ans中，同理，如果右边值小于左边值，就把左边值放到ans里。（当然，我这是按照从小到大进行排序的，如果是从大到小进行排序的，过程就是相反的）
大体分离思路（以[0-16]的数组为例）： 合并的思路算法流程图是:
3）算法的难点
难点1:记住一定是先分离,再进行合并，这才是归并。 难点2:在分离的时候，记得判断左右两边的列表是否超过边界，如果某一个列表超过边界，那么直接就把没有超过边界的另一个列表放到存放答案的列表里就好了 （整个放进去就好了，因为之前的数组已经是排好序的了）。 难点3：进行测试的时候 ，应该是
list1
=[1,4,5,2,3,4]
res
= mergesort
(list1
)
print(res
)
不能直接对list1进行输出，函数并没有直接改变list1的值
总结
今天介绍了希尔排序和归并排序，这两种都是比之前的排序性能有提升的排序算法，可能会有点错误，希望大家能够原谅新手小白，我也会及时修正。
