国内做视频网站需要啥,哪个网站网站空间最好,海口网站关键词优化,wordpress 嵌套软件快速排序
找一个基准值x(默认是第一个值)#xff0c;把列表分成三部分:小于等于x的数字#xff0c;x,大于x的数字左半部分和右半部分递归使用该策略
例: a【3,5,8,1,2,9,4,7,6】
找到基准值3,【1,2】3 【5,8,9,4,7,6】左半部分【1,2】作为一个子问题求解#xff1b;
右半…快速排序
找一个基准值x(默认是第一个值)把列表分成三部分:小于等于x的数字x,大于x的数字左半部分和右半部分递归使用该策略
例: a【3,5,8,1,2,9,4,7,6】
找到基准值3,【1,2】3 【5,8,9,4,7,6】左半部分【1,2】作为一个子问题求解
右半部分【5,8,9,4,7,6】作为一个子问题求解。
def quick_sort(li,left,right):if leftright:midpartition(li,left,right) # 返回下标值,从列表第一个值开始,每次定位在中间值quick_sort(li,left,mid-1)quick_sort(li,mid1,right)def partition(li,left,right):tmpli[left] # 把第一个值存起来while leftright:while leftright and li[right]tmp:right-1 # 往左走一步li[left]li[right] # 右边的值写到左边空位上while leftright and li[left]tmp:left1li[right]li[left] # 把左边的值写到右边空位li[left]tmp # 把tmp归位return left # 返回mid值,left,right都行nint(input())
alist(map(int,input().split()))
quick_sort(a,0,n-1)
print( .join(map(str,a)))
归并排序
数据结构算法--5 归并排序-CSDN博客 非常详细解答
def merge(li, low, mid, high):i lowj mid 1ltmp []while i mid and j high: # 只要两边都有数if li[i] li[j]:ltmp.append(li[i])i 1else:ltmp.append(li[j])j 1# 执行完上个while,肯定有一部分没数了while i mid:ltmp.append(li[i])i 1while j high:ltmp.append(li[j])j 1li[low:high 1] ltmpdef merge_sort(li, low, high): # 这里递归就是左右,最后左右一起if low high: # 至少有两个元素,递归mid (low high) // 2merge_sort(li, low, mid) # 等其递归完成返回一个左侧有序列表merge_sort(li, mid 1, high) # 等其递归完返回一个右侧有序列表merge(li, low, mid, high) # 将两个合并n int(input())
a list(map(int, input().split()))
merge_sort(a, 0, n - 1)
print( .join(map(str,a)))
桶排序
首先将元素分在不同的桶中在对每个桶中的元素排序。
def buckt_sort(li, n10, max_num1000): # n为桶的个数buckets [[] for _ in range(n)] # 创建桶for val in li:i min(val // (max_num // n), n - 1) # max_num//n为每个桶内的容量,i表示val放到几号桶buckets[i].append(val) # 加入到i号桶# 保持桶内的顺序for j in range(len(buckets[i]) - 1, 0, -1): # 步数为-1,反向冒泡排序if buckets[i][j] buckets[i][j - 1]:buckets[i][j], buckets[i][j - 1] buckets[i][j - 1], buckets[i][j]else:breaksotr_list []for buc in buckets: # buc为一个列表(每个桶),一维sotr_list.extend(buc)return sotr_listn int(input())
a list(map(int, input().split()))
a buckt_sort(a)
print( .join(map(str, a)))
