python查找与排序算法详解（示意图+代码、看完基础不成问题）

  

博客首页：knighthood2001

欢迎点赞评论️

❤️ 热爱python，期待与大家一同进步成长！！❤️

给大家推荐一款很火爆的刷题、面试求职网站

目录

查找

二分查找

线性查找

排序 

插入排序

快速排序

选择排序

冒泡排序

归并排序

堆排序

计数排序

希尔排序

拓扑排序

总结

        笔者最近在找一些经典算法，这时候发现牛客网中有许多，笔者根据源码并进行了一下细微的调整，现将整理好的代码及运行结果写出来，需要进行刷题的可以点此进行注册，开启刷题之旅！！

        当然，牛客网中有些代码所展示出来的格式不太好 ，比如print ()而不是print()、有些会在行后面加‘;’，不太符合python的写法。不过这些不是最主要的，接下来开启python查找与排序之旅吧！！ 

查找

二分查找

        二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

# 返回 x 在 arr 中的索引，如果不存在返回 -1
def binarySearch (arr, l, r, x):
    # 基本判断
    if r >= l:
        mid = int(l + (r - l)/2)
        # 元素整好的中间位置
        if arr[mid] == x:
            return mid
        # 元素小于中间位置的元素，只需要再比较左边的元素
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)
        # 元素大于中间位置的元素，只需要再比较右边的元素
        else:
            return binarySearch(arr, mid+1, r, x)
    else:
        # 不存在
        return -1

# 测试数组
arr = [ 2, 3, 4, 10, 40]
x = int(input('请输入元素：'))
# 函数调用
result = binarySearch(arr, 0, len(arr)-1, x)

if result != -1:
    print("元素在数组中的索引为 %d" % result)
else:
    print("元素不在数组中")

        运行结果： 

请输入元素：4
元素在数组中的索引为 2

请输入元素：5
元素不在数组中

线性查找

        线性查找指按一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止。 

def search(arr, n, x):
    for i in range (0, n):
        if (arr[i] == x):
            return i
    return -1

# 在数组 arr 中查找字符 D
arr = [ 'A', 'B', 'C', 'D', 'E' ]
x = input("请输入要查找的元素：")
n = len(arr)
result = search(arr, n, x)
if(result == -1):
    print("元素不在数组中")
else:
    print("元素在数组中的索引为", result)

        运行结果： 

请输入要查找的元素：A
元素在数组中的索引为 0

请输入要查找的元素：a
元素不在数组中

排序 

插入排序

        插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key

arr = [12, 11, 13, 5, 6, 7, 9, 9, 17]
insertionSort(arr)
print("排序后的数组:")
print(arr)

        运行结果：  

排序后的数组:
[5, 6, 7, 9, 9, 11, 12, 13, 17]

当然也可以这样写，更简洁

list1 = [12, 11, 13, 5, 6, 7, 9, 9, 17]
for i in range(len(list1)-1, 0, -1):
    for j in range(0, i):
        if list1[i] < list1[j]:
            list1[i], list1[j] = list1[j], list1[i]
print(list1)

快速排序

        快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

• 挑选基准值：从数列中挑出一个元素，称为"基准"（pivot）;
• 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成;
• 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。