Python实现常见排序算法下
一、快速排序
快速排序(Quick Sort),又称为划分交换排序(Partition-exchange Sort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要笑,然后在按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
1、快速排序过程:
① 从数列中选出一个元素,称为“基准”(pivot)。
② 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准大的摆在基准的后面(相同的数,可以放到任意一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
③ 递归(recursive)把小于基准值元素子数列和大于基准值元素的子数列排序。
递归的的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。
2、python实现过程:
这里提供两种快速排序的方式,基本思想一样,第一种是在原有列表进行操作(通过游标进行),第二种则是新建左右子列表进行存储。
# coding=utf-8
def quick_sort1(ls, start, end):
"""
快速排序-1
low 和 high 分别指向序列的头和尾
low += 1, high -= 1
在low自增过程中,直到找到大于 mid_val 的下标
在high自增减过程中,直到找到小于 mid_val 的小标
然后将这两个值交换
"""
# 递归退出条件
if start >= end:
return
low = start
high = end
mid_val = ls[low]
while low < high:
while low < high and ls[high] > mid_val:
high -= 1
ls[low] = ls[high]
while low < high and ls[low] < mid_val:
low += 1
ls[high] = ls[low]
ls[low] = mid_val
print("mid:", mid_val, ls)
quick_sort1(ls, start, low - 1) # 左边的子序列
quick_sort1(ls, low + 1, end) # 右边的子序列
return ls
def quick_sort2(ls):
"""快速排序-2"""
# 递归退出条件
if len(ls) <= 1:
return ls
left_ls, right_ls = [],[]
mid_val = ls[0]
for i in range(1, len(ls)):
if ls[i] < mid_val:
left_ls.append(ls[i])
else:
right_ls.append(ls[i])
print(left_ls, mid_val, right_ls)
# 递归调用,左右子列表
left_res = quick_sort2(left_ls)
right_res = quick_sort2(right_ls)
return left_res + [mid_val] + right_res
if __name__ == "__main__":
ls1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
ls2 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print("before:", ls1)
res1 = quick_sort1(ls1, 0, len(ls1) - 1)
print("quick sort1: ", res1)
print("-"*50)
print("before: ", ls2)
res2 = quick_sort2(ls2)
print("quick sort2:", res2)
执行结果:
3、时间复杂度:
最优时间复杂度:O(nlogn)
最坏时间复杂度:O(n2)
稳定性:不稳定
二、归并排序
归并排序是采用分治法的一种非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组。
将数组分解最小之后,然后合并两个有序数组,基本思路:比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直到一个数组为空,最后把另外一个数组的剩余部分复制过来即可。
1、归并排序过程,图示:
分而治之
可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。
再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。
2、python实现过程:
先把序列拆分成 left_ls 和 right_ls ,然后再合并成一个res。
# coding=utf-8
def merge_sort(ls):
"""归并排序"""
n = len(ls)
# 递归退出条件
if n <= 1:
return ls
mid = n // 2
# 1、拆分子序列
left_ls = merge_sort(ls[:mid])
right_ls = merge_sort(ls[mid:])
# 2、合并子序列:left_ls 和 right_ls
left_point, right_point = 0, 0
res = []
# 当left_ls或者right_ls 结束,就会退出 while,而另外一个则可能未结束,所有后面需要 res +=
while left_point < len(left_ls) and right_point < len(right_ls):
# 比较两个子序列,小的先加入到 res[]
if left_ls[left_point] < right_ls[right_point]:
res.append(left_ls[left_point])
left_point += 1
else:
res.append(right_ls[right_point])
right_point += 1
print("res:", res)
res += left_ls[left_point:]
res += right_ls[right_point:]
return res
if __name__ == "__main__":
ls = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print("before: ", ls)
res = merge_sort(ls)
print("merge sort: ", res)
执行结果:
3、时间复杂度:
最优时间复杂度:O(nlogn)
最坏时间复杂度:O(nlogn)
稳定性:稳定
三、二分查找
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,其缺点是要求待查找表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。
基本思想:假设表中元素是按升序排序,将表中间位置记录关键字与查找关键字比较,如果两者相等,则查找成功,否则利用中间位置记录分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一个子表。重复以上过程,知道找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
1、二分查找过程,图示(图片来源网络):
2、python实现过程:
这里主要两种实现方式,一种递归,另一种非递归。
# coding=utf-8
def binary_search_recursion(ls, item):
"""二分查找---递归"""
n = len(ls)
if n < 1:
return False
mid = n // 2
# 与中间值比较
if item == ls[mid]:
return True
# 去左边子序列查找
elif item < ls[mid]:
return binary_search_recursion(ls[:mid], item)
# 去右边子序列查找
else:
return binary_search_recursion(ls[mid + 1:], item)
def binary_search(ls, item):
"""二分查找---非递归"""
n = len(ls)
start = 0
end = n - 1
while start <= end:
mid = (start + end) // 2
if item == ls[mid]:
return True
elif item < ls[mid]:
end = mid - 1
else:
start = mid + 1
return False
if __name__ == "__main__":
ls = [17, 20, 26, 31, 44, 54, 55, 77, 93]
num = int(input("请输入一个整数:"))
res = binary_search(ls, num)
print("查找结果:", res)
3、时间复杂度:
最优时间复杂度:O(nlogn)
最坏时间复杂度:O(n2)
稳定性:稳定