首页 > 其他分享 >归并排序(递归)(NB)

归并排序(递归)(NB)

时间:2023-08-12 23:34:29浏览次数:60  
标签:归并 递归 NB mid low 排序

博客地址:https://www.cnblogs.com/zylyehuo/

递归思路

# _*_coding:utf-8_*_

import random


def merge(li, low, mid, high):
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high:  # 只要左右两边都有数
        if li[i] < li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1
    # while执行完,肯定有一部分没数了
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high + 1] = ltmp


def merge_sort(li, low, high):
    if low < high:  # 至少有两个元素,递归
        mid = (low + high) // 2
        merge_sort(li, low, mid)
        merge_sort(li, mid + 1, high)
        merge(li, low, mid, high)


li = list(range(10))

random.shuffle(li)
print(li)
merge_sort(li, 0, len(li) - 1)
print(li)

标签:归并,递归,NB,mid,low,排序
From: https://www.cnblogs.com/zylyehuo/p/17625837.html

相关文章

  • 堆排序(topk 问题)(NB)
    博客地址:https://www.cnblogs.com/zylyehuo/#_*_coding:utf-8_*_#比较排序importrandomdefsift(li,low,high):#堆的向下调整(小根堆)i=lowj=2*i+1tmp=li[low]whilej<=high:ifj+1<=highandli[j+1]<li[j]:......
  • 堆排序(内置模块 heapq )(NB)
    博客地址:https://www.cnblogs.com/zylyehuo/#_*_coding:utf-8_*_importheapq#q->queue优先队列importrandomli=list(range(10))random.shuffle(li)print(li)heapq.heapify(li)#建堆(小根堆)n=len(li)foriinrange(n):print(heapq.heappop(li),......
  • 算法——初级排序算法之归并排序
    介绍将两个有序的数组归并成一个更大的有序数组,这种算法叫归并排序特点优点:能够保证将任意长度为N的数组排序所需时间和NlogN成正比缺点:所需的额外空间和N成正比1、**原地归并**实现归并的一种直截了当的办法是将两个不同的有序数组归并到每三个数组中,两个数组中的元素......
  • 快速排序(NB)
    博客地址:https://www.cnblogs.com/zylyehuo/#_*_coding:utf-8_*_defpartition(li,left,right):tmp=li[left]whileleft<right:whileleft<rightandli[right]>=tmp:#从右面找比tmp小的数right-=1#往左走一步l......
  • 递归的进一步思考
    翻转二叉树:首先要想整体思路:翻转一个二叉树就是先将左子树和右子树翻转,然后对作用左子树翻转函数(对左子树中的所有左右结点翻转),对右子树进行翻转函数那么递归部分如下:swap(node->left,node->right);reverse(node->left);reverse(node->right);这里需要注意的是reverse......
  • 拓端数据tecdat|R语言代写通过WinBUGS对MGARCH和MSV模型进行贝叶斯估计和比较
    多变量广义自回归条件异方差(MGARCH)和多变量随机波动率(MSV)模型与马尔可夫链蒙特卡罗方法的贝叶斯估计和比较可以直接和成功地在WinBUGS包中进行。经济全球化和金融市场的完整性促进了对资产定价,风险管理,投资组合选择等各个领域的多元波动建模的需求。因此,两种类型的模型-多变量广......
  • 王道408---冒泡排序、快速排序、直接插入排序、希尔排序、二路归并排序、简单选择排序
    一、冒泡排序冒泡排序属于交换类的排序//时间复杂度:O(n^2)//空间复杂度:O(1)//稳定排序算法#include<stdio.h>#include<iostream>usingnamespacestd;intarr[16];voiddebug(){for(inti=1;i<16;i++){printf("%d",arr[i]);}puts("......
  • 插件Rainbow Brackets插件使用
    插件RainbowBrackets1.自带花括号彩虹色2.高亮部分代码块command+右键代码块3.着重展示,其余都黑标alt+右键代码块4.取消代码高亮按esc......
  • 汉诺塔问题(递归)
    博客地址:https://www.cnblogs.com/zylyehuo/#_*_coding:utf-8_*_defhanoi(n,a,b,c):ifn>0:hanoi(n-1,a,c,b)print("movingfrom%sto%s"%(a,c))hanoi(n-1,b,a,c)hanoi(5,'A','B�......
  • 递归的用法
    递归主要有两难:1.判断递归方法的执行主体,具体从入参来看: 例如第一个递归方法入参是文件夹,确保了是可以保存文件。那么执行的时候就不需要判断入参是否是文件夹;第二个递归方法的入参是文件,不能确定是否是文件夹,需要第一步进行判断。但是两种方法都实现了查找文件夹下的文件的......