001.二分查找
# 二分查找
'''
1.end问题
2.44对应的end<start 找不到情况
3.返回值递归的情况
4,611,aim太大的情况
'''
l = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
def find(l, aim, start=0, end=None):
end = len(l) if end is None else end
Mid_index = (end - start) // 2 + start
if aim <= l[len(l) - 1]:
if end >= start:
if l[Mid_index] > aim:
return find(l, aim, start=start, end=Mid_index - 1)
elif l[Mid_index] < aim:
return find(l, aim, start=Mid_index + 1, end=end)
elif l[Mid_index] == aim:
return Mid_index
else:
return '找不到!'
else:
return '比列表最大数都大,找不到!'
l = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
ret = find(l, 411)
ret1 = find(l, 44)
ret2 = find(l, 66)
ret3 = find(l, 67)
print(ret, ret1, ret2, ret3) #比列表最大数都大,找不到! 找不到! 17 18
002.冒泡排序
import random
import cProfile
'''
冒泡排序:比较相邻元素,顺序错误就交换顺序
最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
最坏时间复杂度：O(n2) 2次循环
稳定性：稳定
'''
# 冒泡排序1
def bubble_sort1(nums):
for i in range(len(nums) - 1):
for j in range(len(nums) - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
# 冒泡排序2
def bubble_sort2(alist):
for j in range(len(alist) - 1, 0, -1):
# j表示每次遍历需要比较的次数，是逐渐减小的
for i in range(j):
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
return nums
nums = [random.randint(0, 10000) for i in range(10000)]
print(bubble_sort1(nums))
print(bubble_sort2(nums))
cProfile.run('bubble_sort1(nums)') # 4.881
cProfile.run('bubble_sort2(nums)') # 4.919
003.选择排序---稍微减少运行时间，是冒泡排序的改进版
import random
import cProfile
'''
选择排序:选择最小的,以此类推
最优时间复杂度：O(n2)
最坏时间复杂度：O(n2)
稳定性：不稳定（考虑升序每次选择最大的情况）
'''
# 选择排序1
def select_sort(nums):
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
if nums[i] > nums[j]:
# max = nums[i]
# nums[i] = nums[j]
# nums[j] = max
# python有更好的写法
nums[i], nums[j] = nums[j], nums[i]
return nums
# 选择排序2
def selection_sort(alist):
n = len(alist)
# 需要进行n-1次选择操作
for i in range(n - 1):
# 记录最小位置
min_index = i
# 从i+1位置到末尾选择出最小数据
for j in range(i + 1, n):
if alist[j] < alist[min_index]:
min_index = j
# 如果选择出的数据不在正确位置，进行交换
if min_index != i:
alist[i], alist[min_index] = alist[min_index], alist[i]
return nums
nums = [random.randint(0, 10000) for i in range(10000)]
print(select_sort(nums))
print(selection_sort(nums))
cProfile.run('select_sort(nums)') # 3.172
cProfile.run('selection_sort(nums)') # 3.298
004.插入排序
import random
import cProfile
'''
插入排序:假设元素左侧全部有序,找到自己的位置插入
最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
最坏时间复杂度：O(n2)
稳定性：稳定
'''
def insert_sort(alist):
# 从第二个位置，即下标为1的元素开始向前插入
for i in range(1, len(alist)):
# 从第i个元素开始向前比较，如果小于前一个元素，交换位置
for j in range(i, 0, -1):
if alist[j] < alist[j - 1]:
alist[j], alist[j - 1] = alist[j - 1], alist[j]
return nums
nums = [random.randint(0, 10000) for i in range(10000)]
print(insert_sort(nums))
cProfile.run('insert_sort(nums)') # 5.043
005.快速排序
'''
快速排序：
又称划分交换排序（partition-exchange sort），
通过一趟排序将要排序的数据分割成独立的两部分，
其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，
整个排序过程可以递归进行，以此达到整个数据变成有序序列。
1.从数列中挑出一个元素，称为"基准"（pivot），
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
最优时间复杂度：O(nlogn)
最坏时间复杂度：O(n2)
稳定性：不稳定
'''
import cProfile
import random
import time
import sys
sys.setrecursionlimit(10000) # 设置最大递归深度为3000
start_time = time.time()
def quick_sort(alist, start, end):
"""快速排序"""
# 递归的退出条件
if start >= end:
return
# 设定起始元素为要寻找位置的基准元素
mid = alist[start]
# low为序列左边的由左向右移动的游标
low = start
# high为序列右边的由右向左移动的游标
high = end
while low < high:
# 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
while low < high and alist[high] >= mid:
high -= 1
# 将high指向的元素放到low的位置上
alist[low] = alist[high]
# 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
while low < high and alist[low] < mid:
low += 1
# 将low指向的元素放到high的位置上
alist[high] = alist[low]
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
# 将基准元素放到该位置
alist[low] = mid
# 对基准元素左边的子序列进行快速排序
quick_sort(alist, start, low - 1)
# 对基准元素右边的子序列进行快速排序
quick_sort(alist, low + 1, end)
return nums
nums = [random.randint(0, 10000) for i in range(10000)]
print(quick_sort(nums, 0, len(nums) - 1))
end_time = time.time()
print(end_time - start_time) # 0.045
# 堆栈溢出
cProfile.run('quick_sort(nums, 0, len(nums) - 1)')
006.归并排序
'''
归并排序:分而治之,一分为二进行排序--我一直以为是快排(看我博客的sorry了)
归并排序的思想就是先递归分解数组，再合并数组。
最优时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
稳定性：稳定
'''
import cProfile
import random
def merge_sort(nums):
if len(nums) <= 1:
return nums
s_nums = []
l_nums = []
# 小于nums[0]放左边
for i in nums[1:]:
if i < nums[0]:
s_nums.append(i)
else:
# #大于nums[0]放右边
l_nums.append(i)
# nums[0:1]是列表[],nums[0]是int数字
# 连接左右列表加num[0:1]
return merge_sort(s_nums) + nums[0:1] + merge_sort(l_nums)
nums = [random.randint(0, 10000) for i in range(10000)]
print(merge_sort(nums))
cProfile.run('merge_sort(nums)') # 0.045
007.桶排序
'''
桶排序:最快最简单的排序
缺点:最占内存
类型:分布式排序
'''
import cProfile
import random
def bucketSort(nums):
#选出最大的数
max_num = max(nums)
#创建一个元素全是0的列表,当桶
bucket = [0]*(max_num+1)
#把所有元素放入桶中,即把对应元素个数加1
for i in nums:
bucket[i] = bucket[i] + 1
sort_nums = []
#取出桶中的元素
for j in range(len(bucket)):
if bucket[j] != 0 :
for y in range(bucket[j]):
sort_nums.append(j)
return sort_nums
nums = [random.randint(0,10000) for i in range(10000)]
print(bucketSort(nums))
cProfile.run('bucketSort(nums)') # 0.005