冒泡排序

"""冒泡排序思想：冒泡排序的思想就是通过在无序的序列中,让两个相邻的元素一一对比,小的元素左移,大的元素右移.即小的元素逐渐上浮,大的元素逐渐下沉,一轮循环下来找到序列的最大值,重复此循环,直到给所有元素排好顺序
"""
import timedef bubble_sort(li):# 外层循环控制待确定位置元素的个数for j in range(len(li) - 1, 0, -1):# 内层循环控制相邻位置的元素对比for k in range(j):# 当左边元素大于右边元素时if li[k] > li[k + 1]:# 调换两个元素的位置li[k], li[k + 1] = li[k + 1], li[k]return liif __name__ == '__main__':t1 = time.time()li = [6, 3, 5, 4, 2, 7, 1, 8, 0, 0.2, 9]result = bubble_sort(li)t2 = time.time()print(result)print('执行时间是：%.8f秒' % (t2 - t1))

快速排序

"""快速排序：思想：快速排序的核心思想是分而治之：先将序列的第一个元素作为基准值创建两个游标,左游标指到基准值后面的第一个元素,右游标指到序列的最后一个元素然后左游标右移,右游标左移,当左游标所指的值大于基准值时,左游标停止当右游标所指的值小于基准值时,右游标停止,两个元素调换位置两个游标循环移动,当左游标索引值大于右游标索引值时,将右游标所指的值与基准值调换位置此时第一个基准值就找到了它在序列中的确定位置再利用递归思想,循环往复,找到所有元素的确定位置
"""
import timedef quick_sort(li, first, last):# 由题意知,当只剩下最后一个待确定的值时,即左右游标指向同一个元素时,此时是退出条件# 而下面调用递归的方法,一个是右游标减一的情况,另一个是左游标加一的情况# 此时左游标的值都是大于右游标的,所以退出条件如下if语句if first > last:return# 调用函数,取出已确定基准值位置的下标索引split_pos = quick(li, first, last)# 将序列按照已确定基准值位置的值,分成两部分 quick_sort(li, first, split_pos - 1)quick_sort(li, split_pos + 1, last)def quick(li, first, last):# 取序列的第一个元素当做基准值mid = li[first]# 基准值后面的第一个元素作为左游标lcur = first + 1# 获取右游标rcur = lastsign = Truewhile sign:# 当左游标小于右游标,且左游标指向值小于基准值时,左游标右移while lcur <= rcur and li[lcur] <= mid:lcur += 1# 当左游标小于右游标,且右游标指向值大于基准值时,左游标右移while lcur <= rcur and li[rcur] >= mid:rcur -= 1# 程序走到这有两种情况# 第一：左游标的值大于右游标的值# 第二：左游标找到了比基准值大的值,右游标找到了比基准值小的值if lcur > rcur:# 第一种情况,设置退出条件,调换基准值和右游标的位置sign = Falseli[first], li[rcur] = li[rcur], li[first]# 第二种情况,调换左右游标的位置else:li[lcur], li[rcur] = li[rcur], li[lcur]# 返回右游标位置,即基准值位置return rcurif __name__ == '__main__':t1 = time.time()li = [6, 3, 5, 4, 2, 7, 1, 8, 0, 0.2, 9]quick_sort(li, 0, len(li) - 1)t2 = time.time()print(li)print('执行时间是：%.8f秒' % (t2 - t1))

归并排序

"""归并排序思想：归并排序的核心思想是分而治之.先分：先将一个无序序列的元素一一的划分成最小单元,再和：在按照大小顺序一一的放好位置.
"""
import timedef merge_sort(li):# 递归出口, 当分割成最小单元时if len(li) == 1:return li# 将序列分开sid = len(li) // 2left = li[:sid]right = li[sid:]# 递归递推过程left_list = merge_sort(left)right_list = merge_sort(right)# 返回值在递归之后,由内向外,回推过程return merge(left_list, right_list)def merge(left_list, right_list):# 定义空列表,依次加入元素result = []# 当两个列表都有元素时,循环加入元素while left_list and right_list:# 判断两个列表的首个元素大小if left_list[0] < right_list[0]:# 将首个元素弹出,追加到起初准备的列表中result.append(left_list.pop(0))else:# 将首个元素弹出,追加到起初准备的列表中result.append(right_list.pop(0))# 当有一个列表为空时,循环结束,将不为空的列表直接合并到结果列表中# 注：此处也可以判断哪个列表不为空result += left_listresult += right_listreturn resultif __name__ == '__main__':t1 = time.time()li = [6, 3, 5, 4, 2, 7, 1, 8, 0, 0.2, 9]result = merge_sort(li)t2 = time.time()print(result)print('执行时间是：%.8f秒' % (t2 - t1))

查找算法

二分查找

"""二分查找思想：二分查找又称折半查找,它的前提条件是序列必须有序,二分查找即搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果中间元素大于或小于要查找元素,则在小于或大于中间元素的那一半进行搜索,而且跟开始一样从中间元素开始比较. 如果在某一步骤数组为空,则代表找不到.这种算法每一次比较都会使搜索范围缩小一半.
"""def binary_search(alist, item):n = len(alist)first = 0last = n - 1while first <= last:mid = (last + first) // 2if alist[mid] > item:last = mid - 1elif alist[mid] < item:first = mid + 1else:return Truereturn Falseif __name__ == "__main__":lis = [2, 4, 5, 12, 14, 23]if binary_search(lis, 12):print('ok')else:print('false')