python字符串选择排序轨迹_python算法学习第——第7天(二分查找、选择排序、快速排序)...
1、二分查找
对一串有序数字进行二分查找。
函数 binary_search 接受一个有序数组和一个元素。如果指定的元素包含在数组中，这个函数将返回其位置。你将跟踪要在其中查找的数组部分——开始时为整个数组
low = 0
high = len(list) - 1
文章图片
你每次都检查中间的元素。
mid = (low + high) // 2 # 如果(low + high)不是偶数，python自动将mid向下取整
guss = list[mid]
如果猜的数字小了，就相应的修改low。
if guess < item:
low = mid + 1
如果猜的数字大了，就修改high。
if guess > item:
high = mid - 1
全部代码如下:
def binary_search(lst, item):
low = 0
high = len(lst) - 1
while low <= high:
mid = (low + high)//2 # 向下取整
guss = lst[mid]
if guss == item:
return mid
if guss > item:
high = mid - 1
else:
low = mid + 1
return None
# print("请输入一串有序数字，以空格分隔：",end="")
# my_list = [int(i) for i in input().split()]
my_list = [int(i) for i in input("请输入一串有序数字，以空格分隔：").split()] # 将上面两句合并
# my_list = [1,3,5,7,9]
a = int(input("请 输 入 要 二 分 查 找 的 数 字："))
print(binary_search(my_list,a))
时间复杂度：O(logn)
2、选择排序
将一个无序的列表采用 选择排序 的方式进行从小到大进行排序。
代码如下:
# 找出最小元素的函数
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1,len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
# 选择排序函数
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
a = [int(i) for i in input().split()]
print(selectionSort(a))
时间复杂度：O(n^2)
3、快速排序
排序算法来说，最简单的数组什么样呢？就是根本不需要排序的数组。
文章图片
因此，基线条件为数组为空或只包含一个元素。在这种情况下，只需原样返回数组——根本就不用排序。
def quicksort(array):
if len(array) < 2:
return array
我们来看看更长的数组。对包含两个元素的数组进行排序也很容易。
文章图片
包含三个元素的数组呢？
文章图片
这里可以使用 D&C (分而治之) 的思想。
下面介绍快速排序的工作原理。首先，从数组中选择一个元素，这个元素被称为基准值(pivot)。
我们暂时将数组的第一个元素用作基准值。
接下来，找出比基准值小的元素以及比基准值大的元素。
文章图片
这被称为分区(partitioning)。现在你有：
一个由所有小于基准值的数字组成的子数组
基准值
一个由所有大于基准值的数组组成的子数组
这里只是进行了分区，得到的两个子数组是无序的。但如果这两个数组是有序的，对整个数组进行排序将非常容易。
文章图片
如果子数组是有序的，就可以像下面这样合并得到一个有序的数组：左边的数组 + 基准值 +右边的数组。在这里，就是[10, 15] + [33] + []，结果为有序数组[10, 15, 33]。
如何对子数组进行排序呢？对于包含两个元素的数组(左边的子数组)以及空数组(右边的子数组)，快速排序知道如何将它们排序，因此只要对这两个子数组进行快速排序，再合并结果，就能得到一个有序数组！
quicksort([15, 10]) + [33] + quicksort([])
> [10, 15, 33]
不管将哪个元素用作基准值，这都管用。假设你将15用作基准值。
文章图片
这个子数组都只有一个元素，而你知道如何对这些数组进行排序。现在你就知道如何对包含三个元素的数组进行排序了，步骤如下。
(1) 选择基准值。
(2) 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。
(3) 对这两个子数组进行快速排序。
包含四个元素的数组呢？
文章图片
假设你也将33用作基准值。
文章图片
左边的子数组包含三个元素，而你知道如何对包含三个元素的数组进行排序：对其递归地调用快速排序。
文章图片
因此你能够对包含四个元素的数组进行排序。如果能够对包含四个元素的数组进行排序，就能对包含五个元素的数组进行排序。为什么呢？假设有下面这样一个包含五个元素的数组。
文章图片
根据选择的基准值，对这个数组进行分区的各种可能方式如下。
文章图片
注意，这些子数组包含的元素数都在0～4内，而你已经知道如何使用快速排序对包含0～4个元素的数组进行排序！因此，不管如何选择基准值，你都可对划分得到的两个子数组递归地进行快速排序。
例如，假设你将3用作基准值，可对得到的子数组进行快速排序。
文章图片
将子数组排序后，将它们合并，得到一个有序数组。即便你将5用作基准值，这也可行。
文章图片
将任何元素用作基准值都可行，因此你能够对包含五个元素的数组进行排序。同理，你能够对包含六个元素的数组进行排序，以此类推。
代码:
def quicksort(array):
if len(array) < 2:
return array # 基线条件：为空或者只包含一个元素的数组是“有序”的
else:
pivot = array[0] # 选择基准值
less = [i for i in array[1:] if i <= pivot]#由所有小于或者等于基准值的元素组成的子数组
greater = [i for i in array[1:] if i > pivot]#由所有大于基准值的元素组成的子数组
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([2, 7, 1, 3, 4, 8, 2]))
# print([1,2,3]+[4,5,6])
时间复杂度：平均情况下为 O(nlogn)
【python字符串选择排序轨迹_python算法学习第——第7天(二分查找、选择排序、快速排序)...】原文链接:https://blog.csdn.net/weixin_43624626/article/details/114098514
推荐阅读
- python学习|6.2.3 python二分查找算法及LeetCode题目(3)之二维数组 —— Search a 2D Matrix
- Python 3的教程
- 中文起，Python 字体反爬实战案例，再一点
- python常用标准库（时间模块time和datetime）
- Python常用标准库（pickle序列化和JSON序列化）
- Python实战|逻辑回归实战-股票客户流失预警模型(Python代码)
- centos python3 安装psycopg2 模块
- Python技能树共建Python爬虫模拟登录
- 西瓜书阅读笔记（一）|西瓜书阅读笔记（一） ------模型评估与选择
- Python <算法思想集结;之初窥基础算法