二分查找，选择排序，快速排序，归并排序，冒泡排序

墨蓝 2023-01-23 10:55 18阅读 0赞

# 二分查找 平均时间复杂度logn
    def bianryfind(list,item):
    	low =0;
    	high= len(list)-1
    	
    	while low <= high：
    		mid = int((low+high)/2)
    		guess= list[mid]
    		if guess == item:
    			return guess
    		else if guess>item:
    			high = mid-1
    		else:
    			low =mid+1
    	return None
    	
    # 将数组元素按照从小到大的顺序排序，每次从数组中取出最小值
    # 平均时间复杂度n^2
    def getSmallestIndex(arr):
    	min_value = arr[0]
    	min_index = 0
    	
    	for i in range(1,len(arr)):
    		if arr[i]<min_value:
    			min_value = arr[i]
    			min_index = i
    	return min_index
    	
    def selectionFind(arr):
    	newarr =[]
    	for i in range(0,len(arr)):
    		min_index = getSmallestIndex(arr)
    		newarr.append(arr[min_index])
    	return newarr
    
    # 递归
    # 快速排序，分而治之的策略
    # 平均时间复杂度 nlogn
    def quickSort(arr):
    	if len(arr)<2:
    		return arr;
    	else:
    		pivot = arr[0]
    		less = [i for i in arr[1:] if i <= pivot]
    		print(less)
    		greater = [i for i in arr[1:] if i> pivot]
    		print(greater)
    		
    	return quickSort(less)+pivot+quickSort(greater)
    
    
    #simplesort 把小的不断往前排
    # 时间复杂度为n^2
    def simplesort(arr):
    	for i in range(len(arr)-1):
    		for j in range(i,range(arr)):
    			if arr[i]<arr[j]:
    				temp = arr[i]
    				arr[i]= arr[j]
    				arr[j] = temp
    	return arr
    
    # mergesort nlogn
    def mergesort(arr):
    	if len(arr)<2:
    		return arr
    	else:
    		mid = int(len(arr)/2)
    		right = mergesort(arr[mid:])
    		left = mergesort(arr[:mid])
    	return merge(left,right)
    
    #merge 合并两个已经排好序的列表，产生一个新的列表
    
    def merge(left,right):
    	newarr =[]
    	i=0
    	j=0
    	#对两个列表中的元素进行对比，将最小的元素放到新的列表中
    	while i < len(left) and j< len(right):
    		if left[i]<right[j]:
    			newarr.append(left[i])
    			i+=1
    		else:
    			newarr.append(right[j])
    			j+=1
    	#此时left 或者right已经被添加完毕,将其全部加到newarr中
    	newarr+=left[i:]
    	newarr+=right[j:]
    	return newarr