精华内容
下载资源
问答
  • NULL 博文链接:https://emavaj.iteye.com/blog/673327
  • 仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的,针对排序算法,我们还有一个重要...如果3的前后顺序没有发生变化,那么这种就叫稳定的排序。如果发生变化就叫不稳定排序。 举一个实际的例子:要给电商的订...

    仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的,针对排序算法,我们还有一个重要的度量指标,稳定性。

    这个概念就是如果待排序的序列中存在值相同的元素,经过排序之后,相等元素之间原有的先后顺序不变。

    我来举一个例子说明下:2,9,3,4,8,3。排序后为2 3 3 4 8 9.如果3的前后顺序没有发生变化,那么这种就叫稳定的排序。如果发生变化就叫不稳定排序。

    举一个实际的例子:要给电商的订单排序,订单有两个属性,一个是下单时间,一个是订单金额。

    要求:对订单根据金额从小到大排序,金额相同的话按照下单时间再排序。

    那我们的做法可能先根据金额排序,之后对于每个金额相同的小区间按照下单时间排队,这种思路简单,但是实现稍显复杂

    借助稳定排序算法,我们可以先按照订单时间排序,之后再用稳定爱旭按照金额排序。稳定排序算法可以保证金额相同的两个对象再排序后的前后顺序不变。

    冒泡:原地排序,稳定排序。

    快速排序:不稳定

    例如6,11,3,9,8,7,3,2

    比如9为pivot,交换之后后面的3就会跑到前面。所以不是稳定的。

     

     

     

     

    展开全文
  • 超火动态排序疫情变化图,这次我们用 Plotly来绘制各位同学早上好,我是 Lemonbit 。国内的疫情基本进入扫尾阶段了,但国外疫情还处于爆发的高峰...

    超火动态排序疫情变化图,

    这次我们用 Plotly来绘制

    各位同学早上好,我是 Lemonbit 。

    国内的疫情基本进入扫尾阶段了,但国外疫情还处于爆发的高峰期。以前是咱们国家各个省对口支援湖北的一个市,现在开启一个省支援一个国家的模式。

    大国风范,为祖国点赞!!!

    近期,我写了几篇用 Plotly 来演示全球疫情情况的文章,如下:

    作为延伸,今天,来分享用 Plotly 来制作动态排名各个国家疫情变化情况的柱状图。先来看最终的效果:

    上图中,国家排名以及确诊数量,都是动态变化的。类似的图,估计大伙已经看到用其他工具制作的,今天,我们来看看如何用 Plotly 来实现。

    数据来源

    本次我们主要来可视化分析国外疫情的发展情况。疫情的数据来源于开源项目 Akshare,由于使用该项目获取数据时,有时不太稳定,可能会遇到连接失败的情况。所以,这里我提供了保存好的数据供大家练习使用,本文的代码及数据文件在文末提供了获取方式。

    当然,大家也可以使用 Akshare 的数据,因为会不时的更新,如果连接中断的话,换个时间重试下就好。

    准备工作

    照例,还是先介绍下我运行的环境。

    • Mac 系统

    • Anaconda(Python 3.7)

    • Jupyter Notebook

    我是在 Jupyter Notebook 中运行代码的,本次使用到的 Python 库包括 akshare, pandas, plotly 等,导入如下:

    import akshare as ak
    import pandas as pd
    import plotly
    import plotly.graph_objs as go
    from plotly.offline import iplot, init_notebook_mode,plot
    import plotly.express as px
    from datetime import datetime
    # 在PyCharm、VS Code等IDE中运行时,
    # 需要注释下面这行代码
    init_notebook_mode()
    

    使用的几个 Python 库的版本如下:

    print(f'pandas version: {pd.__version__}')
    print(f'akshare version: {ak.__version__}')
    print(f'plotly version: {plotly.__version__}')
    # pandas version: 1.0.1
    # akshare version: 0.4.27
    # plotly version: 4.5.0
    

    接着,我们读取已获得的数据(已保存的数据是截至3月16日)。

    # 从 akshare 获取数据
    # df_all_history = ak.epidemic_history()
    # 从csv文件获取数据,这个数据文件的数据截止到3月10日
    df_all_history = pd.read_csv('epidemic_all_20200316.csv',index_col=0)
    df_all_history
    

    从上面获取的数据,有些数据格式需要加以调整,对于日期,我们这里会组织两列数据,一列是时间格式的日期( ['date']),一列是字符串格式的日期 ( ['dates'])。这样设置的原因,是因为我们后续分别需要用到这两种格式的日期。

    # 将数据复制一份
    df_all = df_all_history
    # 将字符串格式的日期转换为 日期格式
    df_all['date'] = pd.to_datetime(df_all['date'])
    # 将时间格式转为字符串格式的日期,以 YYYY-mm-dd 的形式保存
    df_all['dates'] = df_all['date'].apply(lambda x:x.strftime('%Y-%m-%d'))
    # 添加现存确诊列
    df_all['current'] = df_all['confirmed'] - df_all['cured'] - df_all['dead']
    print(df_all.info())
    # df_all
    

    全球概况

    上面的数据,是全球的数据,其中也包括国内各个省市的数据。我们可以将数据进行整理,分别提取出中国和海外国家的数据。

    # 国内总计数量
    df_china_total = df_all.query("country=='中国' and province==''") 
    df_china_total = df_china_total.sort_values('date',ascending=False)
    # df_china_total
    # ---------
    # 国外,按国家统计
    df_oversea = df_all.query("country!='中国'") 
    df_oversea.fillna(value="", inplace=True)
    # df_oversea
    # ---------
    # 全球统计
    df_global =  df_china_total.append(df_oversea)
    # df_global
    

    进一步,我们可以梳理出全球各个国家最近的疫情情况,这里,我们是按累计确诊数量进行排序的。

    # 全球最近的概况
    # 按日期进行排序
    df_global_date = df_global.sort_values('date',ascending=False)
    # 获取最新的日期
    latest_day = df_global_date['dates'].values[0]
    # query 函数中,变量需要加 @ ,
    df_global_latest = df_global_date.query('dates==@latest_day')
    # 按累计确诊数量排序
    df_global_latest = df_global_latest.sort_values('confirmed',ascending=False)
    df_global_latest
    

    可以看出,累计确诊人数,中国最多,但现存确诊人数,3月16日,是意大利最多了。

    海外疫情情况

    国外的疫情发展情况,大部分国家从2月10日起,发展趋势较为明显,因此,后面我们重点分析这段时间之后的情况。

    # 现有数据演示从 2020年2月10日开始
    df_oversea_recent = df_oversea.set_index('date')
    df_oversea_recent = df_oversea_recent['2020-02-10':]
    # df_oversea_recent
    

    由于部分国家的数据不是从2020年2月10日开始记录的,所以要补充数据。我们可以手动新建一个 excel数据表,将补充日期的数值填充为 0 。

    至于为什么要补充数据呢,因为如果没有补充的话,这个国家在绘制的图里就不会出来,有兴趣的同学可以测试下。

    2月10日开始的数据,没有伊朗的,因为伊朗的数据是很靠前的所以必须纳入分析的范围内。其他国家,如果有需要补充的,后续可以继续完善。

    补充的数据在 epidemic_buchong.xlsx 这个文件里。

    # 由于部分国家,数据不是从2020年2月10日开始的,所以要补充数据,数值为 0
    # 数据在 excel 表格中进行补充,这里进行读取
    df_oversea_buchong = pd.read_excel('epidemic_buchong.xlsx')
    df_oversea_buchong['dates'] = df_oversea_buchong['date'].apply(lambda x:x.strftime('%Y-%m-%d'))
    df_oversea_buchong.set_index('date', inplace=True)
    df_oversea_buchong.fillna(value="", inplace=True)
    print(df_oversea_buchong.info())
    # df_oversea_buchong
    

    将需要补充的数据弄好后,我们可以合并上面这两部分数据,一起进行分析。

    # 合并补充数据
    df_oversea_recent_new = df_oversea_recent.append(df_oversea_buchong)
    df_oversea_recent_new.sort_index(inplace=True)
    # df_oversea_recent_new
    

    对于上面的数据,有一点要说明下,在数据源中,日本的数据前期是包含了钻石公主号邮轮的数量的,后续是将钻石公主号的数据从日本单独列出来了,所以你会发现日本的数据有下降的现象。

    动态排名的柱状图

    得到合并的数据后,我们就可以来进行可视化了,之前 Lemonbit 已经展示了如何用动态气泡图和动态柱状图来可视化,但上次的柱状图没有实现动态排名这个功能,这次我们用动态排名的柱状图来可视化。

    当需要对国家进行动态排名时,首先给每个国家定义一个确定的颜色,以便国家在上下移动的时候,每个国家的颜色保持不变。

    # 准备国家列表和 国家的颜色列表
    countries = list(df_oversea_recent_new['country'].unique())
    countries_count = len(countries) # 国家数量
    # 为每一个国家定义颜色
    color_1 = [px.colors.qualitative.Alphabet[i] for i in range(26)]
    color_2 = [px.colors.qualitative.Light24[i] for i in range(24)]
    color_3 = [px.colors.qualitative.Dark24[i] for i in range(24)]
    color_list = (color_1 + color_2 + color_3)*3  # 颜色数量,比国家数量大
    color_list = color_list[:countries_count]      # 颜色数量跟国家数量一致
    print(f'国家数量:{countries_count}')
    print(f'国家颜色数量:{len(color_list)}')
    

    截止3月16日,全球已经有 150多个国家和区域有疫情的数据了。

    后续,还需要做一些数据上的准备,就是计算出海外单个国家累计确诊人数的最高值。以及,在原来的 DataFrame 中增加了颜色列,为每个国家指定一种颜色。

    计算海外单个国家累计确诊人数的最高值

    # 海外单个国家死亡人数的最高值
    max_dead = df_oversea_recent_new['dead'].max()
    # 海外单个国家累计确诊人数的最高值
    max_confirmed = df_oversea_recent_new['confirmed'].max()
    print(f'海外单个国家累计确诊人数的最高值为{max_confirmed}')
    print(f'海外单个国家死亡人数的最高值为{max_dead}')
    

    为每个国家指定一种颜色

    df  = df_oversea_recent_new
    # df 添加颜色列,每个国家给定一种颜色
    for country,color in zip(countries, color_list):
        df.loc[df['country']==country, 'color'] = color
    # 保存数据到 csv文件
    # df.to_csv(f'epidemic_all_{today}_update.csv')
    # df
    

    动态排名可视化

    到这里,我们准备工作告一段落,可以来进行可视化了。下面的代码有些长,我们实现的是海外国家累计确诊人数排名前 20 的国家进行动态排名,这个是通过 pandas 的 nlargest 功能来实现的。

    对于需要动态排名的柱状图,这里可视化用的是原生的 Plotly , 而不是 plotly.express 。

    在下面代码中,核心的思路是,需要构造一个字典,以 key:value 的形式保存每天的 疫情数据,其中疫情数据是以 DataFrame 的形式保存于 value 中。

    dates_list = list(df['dates'].unique())
    dict_keys = [str(i) for i in range(len(dates_list))]
    n_frame={}
    for date, d in zip(dates_list, dict_keys):
        dataframe=df[df['dates']==date]
        # 排名前20的国家
        dataframe=dataframe.nlargest(n=20,columns=['confirmed'])
        dataframe=dataframe.sort_values(by=['dates','confirmed'])
        n_frame[d]=dataframe
    # print (n_frame)
    #-------------------------------------------
    fig = go.Figure(
        data=[
            go.Bar(
            x=n_frame['0']['confirmed'], y=n_frame['0']['country'],orientation='h',
            text=n_frame['0']['confirmed'], texttemplate='%{text:.3s}',
            textfont={'size':12}, textposition='inside', insidetextanchor='middle',
            width=0.9, marker={'color':n_frame['0']['color']})
        ],
        layout=go.Layout(
            xaxis=dict(range=[0, max_confirmed*1.1], autorange=False, title=dict(text='confirmed',
                                                                  font=dict(size=12))),
            yaxis=dict(range=[-0.5, 20.5], autorange=False,tickfont=dict(size=14)),
            title=dict(text='Confirmed numbers per Country: 2020-02-10',font=dict(size=28),x=0.5,xanchor='center'),
            # 添加按钮
            updatemenus=[dict(
                type="buttons",
                buttons=[dict(label="Play",
                              method="animate",
                              # https://github.com/plotly/plotly.js/blob/master/src/plots/animation_attributes.js
                              args=[None,
                              {"frame": {"duration": 1000, "redraw": True},
                              "transition": {"duration":250,
                              "easing": "linear"}}]
                )]
            )]
        ),
        frames=[
                go.Frame(
                    data=[
                            go.Bar(x=value['confirmed'], y=value['country'],
                            orientation='h',text=value['confirmed'],
                            marker={'color':value['color']})
                        ],
                    layout=go.Layout(
                            xaxis=dict(range=[0, max_confirmed*1.1], autorange=False),
                            yaxis=dict(range=[-0.5, 20.5], autorange=False,tickfont=dict(size=10)),
                            title=dict(text='Confirmed numbers per Country: '+str(value['dates'].values[0]),
                            font=dict(size=28))
                        )
                )
            for key, value in n_frame.items()
        ]
    )
    #-------------------------------------------
    fig.show()
    

    上面代码中,动态排名时通过每天对 go.Frame 中的数据进行更新来实现的。上面的 duration 可以来控制按钮点击后变化的速度。

    运行上述代码后,得到的效果如下:

    是不是很棒啊。

    在文末,Lemonbit 给大家提供了本文完整的PDF版内容(含代码)以及数据文件。

    但这里,通过运行效果,可以看出,由于现在的确诊数量较大,而刚开始的时候数据较小,所以当 x轴 固定不动时,动态化演示的效果不是太理想,我们希望 x轴 上的数据也能动态变化,这样效果会更理想。

    要使 x轴 上的数据也能动态变化,实现文章开始图中的效果,核心是定义 x轴 的范围时,实现动态变化, x轴 的核心代码如下:

    展开全文
  • 排序算法太多了,有很多可能你连名字都听说过,比如猴子排序、睡眠排序、面条排序等。我只讲众多排序算法中的一小撮,也是最经典的、最常用的:冒泡排序、插入排序、选择排序、归并排序、快速排序...

    排序对于任何一个程序员来说,可能都不会陌生。你学的第一个算法,可能就是排序。大部分编程语言中,也都提供了排序函数。在平常的项目中,我们也经常会用到排序。排序非常重要,所以我会花多一点时间来详细讲一讲经典的排序算法。

    排序算法太多了,有很多可能你连名字都没听说过,比如猴子排序、睡眠排序、面条排序等。我只讲众多排序算法中的一小撮,也是最经典的、最常用的:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。我按照时间复杂度把它们分成了三类,分三节课来讲解。

    在这里插入图片描述

    带着问题去学习,是最有效的学习方法。所以按照惯例,我还是先给你出一个思考题:插入排序和冒泡排序的时间复杂度相同,都是 O(n2),在实际的软件开发里,为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢?

    你可以先思考一两分钟,带着这个问题,我们开始今天的内容!

    如何分析一个“排序算法”?
    学习排序算法,我们除了学习它的算法原理、代码实现之外,更重要的是要学会如何评价、分析一个排序算法。那分析一个排序算法,要从哪几个方面入手呢?

    排序算法的执行效率
    对于排序算法执行效率的分析,我们一般会从这几个方面来衡量:

    1. 最好情况、最坏情况、平均情况时间复杂度

    我们在分析排序算法的时间复杂度时,要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外,你还要说出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。

    为什么要区分这三种时间复杂度呢?第一,有些排序算法会区分,为了好对比,所以我们最好都做一下区分。第二,对于要排序的数据,有的接近有序,有的完全无序。有序度不同的数据,对于排序的执行时间肯定是有影响的,我们要知道排序算法在不同数据下的性能表现。

    2. 时间复杂度的系数、常数 、低阶

    我们知道,时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势,所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中,我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据,所以,在对同一阶时间复杂度的排序算法性能对比的时候,我们就要把系数、常数、低阶也考虑进来。

    3. 比较次数和交换(或移动)次数

    这一节和下一节讲的都是基于比较的排序算法。基于比较的排序算法的执行过程,会涉及两种操作,一种是元素比较大小,另一种是元素交换或移动。所以,如果我们在分析排序算法的执行效率的时候,应该把比较次数和交换(或移动)次数也考虑进去。

    排序算法的内存消耗
    我们前面讲过,算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外。不过,针对排序算法的空间复杂度,我们还引入了一个新的概念,原地排序(Sorted in place)。原地排序算法,就是特指空间复杂度是 O(1) 的排序算法。我们今天讲的三种排序算法,都是原地排序算法。

    排序算法的稳定性
    仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法,我们还有一个重要的度量指标,稳定性。这个概念是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

    我通过一个例子来解释一下。比如我们有一组数据 2,9,3,4,8,3,按照大小排序之后就是 2,3,3,4,8,9。

    这组数据里有两个 3。经过某种排序算法排序之后,如果两个 3 的前后顺序没有改变,那我们就把这种排序算法叫作稳定的排序算法;如果前后顺序发生变化,那对应的排序算法就叫作不稳定的排序算法。

    你可能要问了,两个 3 哪个在前,哪个在后有什么关系啊,稳不稳定又有什么关系呢?为什么要考察排序算法的稳定性呢?

    很多数据结构和算法课程,在讲排序的时候,都是用整数来举例,但在真正软件开发中,我们要排序的往往不是单纯的整数,而是一组对象,我们需要按照对象的某个 key 来排序。

    比如说,我们现在要给电商交易系统中的“订单”排序。订单有两个属性,一个是下单时间,另一个是订单金额。如果我们现在有 10 万条订单数据,我们希望按照金额从小到大对订单数据排序。对于金额相同的订单,我们希望按照下单时间从早到晚有序。对于这样一个排序需求,我们怎么来做呢?

    最先想到的方法是:我们先按照金额对订单数据进行排序,然后,再遍历排序之后的订单数据,对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难,但是实现起来会很复杂。

    借助稳定排序算法,这个问题可以非常简洁地解决。解决思路是这样的:我们先按照下单时间给订单排序,注意是按照下单时间,不是金额。排序完成之后,我们用稳定排序算法,按照订单金额重新排序。两遍排序之后,我们得到的订单数据就是按照金额从小到大排序,金额相同的订单按照下单时间从早到晚排序的。为什么呢?

    稳定排序算法可以保持金额相同的两个对象,在排序之后的前后顺序不变。第一次排序之后,所有的订单按照下单时间从早到晚有序了。在第二次排序中,我们用的是稳定的排序算法,所以经过第二次排序之后,相同金额的订单仍然保持下单时间从早到晚有序。

    在这里插入图片描述

    冒泡排序(Bubble Sort)
    我们从冒泡排序开始,学习今天的三种排序算法。

    冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

    我用一个例子,带你看下冒泡排序的整个过程。我们要对一组数据 4,5,6,3,2,1,从小到到大进行排序。第一次冒泡操作的详细过程就是这样:

    在这里插入图片描述

    可以看出,经过一次冒泡操作之后,6 这个元素已经存储在正确的位置上。要想完成所有数据的排序,我们只要进行 6 次这样的冒泡操作就行了。

    在这里插入图片描述

    实际上,刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时,说明已经达到完全有序,不用再继续执行后续的冒泡操作。我这里还有另外一个例子,这里面给 6 个元素排序,只需要 4 次冒泡操作就可以了。

    在这里插入图片描述

    冒泡排序算法的原理比较容易理解,具体的代码我贴到下面,你可以结合着代码来看我前面讲的原理。

    // 冒泡排序,a 表示数组,n 表示数组大小
    public void bubbleSort(int[] a, int n) {
      if (n <= 1) return;
     
     for (int i = 0; i < n; ++i) {
        // 提前退出冒泡循环的标志位
        boolean flag = false;
        for (int j = 0; j < n - i - 1; ++j) {
          if (a[j] > a[j+1]) { // 交换
            int tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
            flag = true;  // 表示有数据交换      
          }
        }
        if (!flag) break;  // 没有数据交换,提前退出
      }
    }
    

    现在,结合刚才我分析排序算法的三个方面,我有三个问题要问你。

    第一,冒泡排序是原地排序算法吗?

    冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为 O(1),是一个原地排序算法。

    第二,冒泡排序是稳定的排序算法吗?

    在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。

    第三,冒泡排序的时间复杂度是多少?

    最好情况下,要排序的数据已经是有序的了,我们只需要进行一次冒泡操作,就可以结束了,所以最好情况时间复杂度是 O(n)。而最坏的情况是,要排序的数据刚好是倒序排列的,我们需要进行 n 次冒泡操作,所以最坏情况时间复杂度为 O(n2)。

    在这里插入图片描述

    最好、最坏情况下的时间复杂度很容易分析,那平均情况下的时间复杂是多少呢?我们前面讲过,平均时间复杂度就是加权平均期望时间复杂度,分析的时候要结合概率论的知识。

    对于包含 n 个数据的数组,这 n 个数据就有 n! 种排列方式。不同的排列方式,冒泡排序执行的时间肯定是不同的。比如我们前面举的那两个例子,其中一个要进行 6 次冒泡,而另一个只需要 4 次。如果用概率论方法定量分析平均时间复杂度,涉及的数学推理和计算就会很复杂。我这里还有一种思路,通过“有序度”和“逆序度”这两个概念来进行分析。

    有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样:

    有序元素对:a[i] <= a[j], 如果 i < j。
    

    在这里插入图片描述

    同理,对于一个倒序排列的数组,比如 6,5,4,3,2,1,有序度是 0;对于一个完全有序的数组,比如 1,2,3,4,5,6,有序度就是n*(n-1)/2,也就是 15。我们把这种完全有序的数组的有序度叫作满有序度。

    逆序度的定义正好跟有序度相反(默认从小到大为有序),我想你应该已经想到了。关于逆序度,我就不举例子讲了。你可以对照我讲的有序度的例子自己看下。

    逆序元素对:a[i] > a[j], 如果 i < j。
    关于这三个概念,我们还可以得到一个公式:逆序度 = 满有序度 - 有序度。我们排序的过程就是一种增加有序度,减少逆序度的过程,最后达到满有序度,就说明排序完成了。

    我还是拿前面举的那个冒泡排序的例子来说明。要排序的数组的初始状态是 4,5,6,3,2,1 ,其中,有序元素对有 (4,5) (4,6)(5,6),所以有序度是 3。n=6,所以排序完成之后终态的满有序度为 n*(n-1)/2=15。

    在这里插入图片描述

    冒泡排序包含两个操作原子,比较和交换。每交换一次,有序度就加 1。不管算法怎么改进,交换次数总是确定的,即为逆序度,也就是n*(n-1)/2–初始有序度。此例中就是 15–3=12,要进行 12 次交换操作。

    对于包含 n 个数据的数组进行冒泡排序,平均交换次数是多少呢?最坏情况下,初始状态的有序度是 0,所以要进行 n*(n-1)/2 次交换。最好情况下,初始状态的有序度是 n*(n-1)/2,就不需要进行交换。我们可以取个中间值 n*(n-1)/4,来表示初始有序度既不是很高也不是很低的平均情况。

    换句话说,平均情况下,需要 n*(n-1)/4 次交换操作,比较操作肯定要比交换操作多,而复杂度的上限是 O(n2),所以平均情况下的时间复杂度就是 O(n2)。

    这个平均时间复杂度推导过程其实并不严格,但是很多时候很实用,毕竟概率论的定量分析太复杂,不太好用。等我们讲到快排的时候,我还会再次用这种“不严格”的方法来分析平均时间复杂度。

    插入排序(Insertion Sort)
    我们先来看一个问题。一个有序的数组,我们往里面添加一个新的数据后,如何继续保持数据有序呢?很简单,我们只要遍历数组,找到数据应该插入的位置将其插入即可。

    在这里插入图片描述

    这是一个动态排序的过程,即动态地往有序集合中添加数据,我们可以通过这种方法保持集合中的数据一直有序。而对于一组静态数据,我们也可以借鉴上面讲的插入方法,来进行排序,于是就有了插入排序算法。

    那插入排序具体是如何借助上面的思想来实现排序的呢?

    首先,我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

    如图所示,要排序的数据是 4,5,6,1,3,2,其中左侧为已排序区间,右侧是未排序区间。

    在这里插入图片描述

    插入排序也包含两种操作,一种是元素的比较,一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时,需要拿 a 与已排序区间的元素依次比较大小,找到合适的插入位置。找到插入点之后,我们还需要将插入点之后的元素顺序往后移动一位,这样才能腾出位置给元素 a 插入。

    对于不同的查找插入点方法(从头到尾、从尾到头),元素的比较次数是有区别的。但对于一个给定的初始序列,移动操作的次数总是固定的,就等于逆序度。

    为什么说移动次数就等于逆序度呢?我拿刚才的例子画了一个图表,你一看就明白了。满有序度是 n*(n-1)/2=15,初始序列的有序度是 5,所以逆序度是 10。插入排序中,数据移动的个数总和也等于 10=3+3+4。

    在这里插入图片描述

    插入排序的原理也很简单吧?我也将代码实现贴在这里,你可以结合着代码再看下。

    // 插入排序,a 表示数组,n 表示数组大小
    public void insertionSort(int[] a, int n) {
      if (n <= 1) return;
     
      for (int i = 1; i < n; ++i) {
        int value = a[i];
        int j = i - 1;
        // 查找插入的位置
        for (; j >= 0; --j) {
          if (a[j] > value) {
            a[j+1] = a[j];  // 数据移动
          } else {
            break;
          }
        }
        a[j+1] = value; // 插入数据
      }
    }
    

    现在,我们来看点稍微复杂的东西。我这里还是有三个问题要问你。

    第一,插入排序是原地排序算法吗?

    从实现过程可以很明显地看出,插入排序算法的运行并不需要额外的存储空间,所以空间复杂度是 O(1),也就是说,这是一个原地排序算法。

    第二,插入排序是稳定的排序算法吗?

    在插入排序中,对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法。

    第三,插入排序的时间复杂度是多少?

    如果要排序的数据已经是有序的,我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置,每次只需要比较一个数据就能确定插入的位置。所以这种情况下,最好是时间复杂度为 O(n)。注意,这里是从尾到头遍历已经有序的数据。

    如果数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据,所以最坏情况时间复杂度为 O(n2)。

    还记得我们在数组中插入一个数据的平均时间复杂度是多少吗?没错,是 O(n)。所以,对于插入排序来说,每次插入操作都相当于在数组中插入一个数据,循环执行 n 次插入操作,所以平均时间复杂度为 O(n2)。

    选择排序(Selection Sort)
    选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

    在这里插入图片描述

    照例,也有三个问题需要你思考,不过前面两种排序算法我已经分析得很详细了,这里就直接公布答案了。

    首先,选择排序空间复杂度为 O(1),是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2)。你可以自己来分析看看。

    那选择排序是稳定的排序算法吗?

    答案是否定的,选择排序是一种不稳定的排序算法。从我前面画的那张图中,你可以看出来,选择排序每次都要找剩余未排序元素中的最小值,并和前面的元素交换位置,这样破坏了稳定性。

    比如 5,8,5,2,9 这样一组数据,使用选择排序算法来排序的话,第一次找到最小元素 2,与第一个 5 交换位置,那第一个 5 和中间的 5 顺序就变了,所以就不稳定了。正是因此,相对于冒泡排序和插入排序,选择排序就稍微逊色了。

    解答开篇
    基本的知识都讲完了,我们来看开篇的问题:冒泡排序和插入排序的时间复杂度都是 O(n2),都是原地排序算法,为什么插入排序要比冒泡排序更受欢迎呢?

    我们前面分析冒泡排序和插入排序的时候讲到,冒泡排序不管怎么优化,元素交换的次数是一个固定值,是原始数据的逆序度。插入排序是同样的,不管怎么优化,元素移动的次数也等于原始数据的逆序度。

    但是,从代码实现上来看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要 3 个赋值操作,而插入排序只需要 1 个。我们来看这段操作:

    冒泡排序中数据的交换操作:

    if (a[j] > a[j+1]) { // 交换
       int tmp = a[j];
       a[j] = a[j+1];
       a[j+1] = tmp;
       flag = true;
    }
    

    插入排序中数据的移动操作:

    if (a[j] > value) {
      a[j+1] = a[j];  // 数据移动
    } else {
      break;
    }
    

    我们把执行一个赋值语句的时间粗略地计为单位时间(unit_time),然后分别用冒泡排序和插入排序对同一个逆序度是 K 的数组进行排序。用冒泡排序,需要 K 次交换操作,每次需要 3 个赋值语句,所以交换操作总耗时就是 3*K 单位时间。而插入排序中数据移动操作只需要 K 个单位时间。

    这个只是我们非常理论的分析,为了实验,针对上面的冒泡排序和插入排序的 Java 代码,我写了一个性能对比测试程序,随机生成 10000 个数组,每个数组中包含 200 个数据,然后在我的机器上分别用冒泡和插入排序算法来排序,冒泡排序算法大约 700ms 才能执行完成,而插入排序只需要 100ms 左右就能搞定!

    所以,虽然冒泡排序和插入排序在时间复杂度上是一样的,都是 O(n2),但是如果我们希望把性能优化做到极致,那肯定首选插入排序。插入排序的算法思路也有很大的优化空间,我们只是讲了最基础的一种。如果你对插入排序的优化感兴趣,可以自行学习一下希尔排序

    内容小结?

    要想分析、评价一个排序算法,需要从执行效率、内存消耗和稳定性三个方面来看。因此,这一节,我带你分析了三种时间复杂度是 O(n2) 的排序算法,冒泡排序、插入排序、选择排序。你需要重点掌握的是它们的分析方法。

    在这里插入图片描述

    这三种时间复杂度为 O(n2) 的排序算法中,冒泡排序、选择排序,可能就纯粹停留在理论的层面了,学习的目的也只是为了开拓思维,实际开发中应用并不多,但是插入排序还是挺有用的。后面讲排序优化的时候,我会讲到,有些编程语言中的排序函数的实现原理会用到插入排序算法。

    今天讲的这三种排序算法,实现代码都非常简单,对于小规模数据的排序,用起来非常高效。但是在大规模数据排序的时候,这个时间复杂度还是稍微有点高,所以我们更倾向于用下一节要讲的时间复杂度为 O(nlogn) 的排序算法。

    课后思考
    我们讲过,特定算法是依赖特定的数据结构的。我们今天讲的几种排序算法,都是基于数组实现的。如果数据存储在链表中,这三种排序算法还能工作吗?如果能,那相应的时间、空间复杂度又是多少呢?

    一、对于课后题,觉得应该有个前提,是否允许修改链表的节点value值,还是只能改变节点的位置?

    一般而言,考虑只能改变节点位置,冒泡排序相比于数组实现,比较次数一致,但交换时操作更复杂;插入排序,比较次数一致,不需要再有后移操作,找到位置后可以直接插入,但排序完毕后可能需要倒置链表;选择排序比较次数一致,交换操作同样比较麻烦。综上,时间复杂度和空间复杂度并无明显变化,若追求极致性能,冒泡排序的时间复杂度系数会变大,插入排序系数会减小,选择排序没有明显变化。

    展开全文
  • 基于深度学习的变化检测算法实现

    万次阅读 热门讨论 2019-06-12 23:04:37
    我是研究生期间研究主要研究SAR影像的变化检测,这是一段简单的基于深度学习的变化检测方法,以CNN实现。 后续我会把整个代码的思路写上,由于这个是自己写的代码,如果有哪些地方写的不太好请大家见谅,如果有不懂...

    我是研究生期间研究主要研究SAR影像的变化检测,这是一段简单的基于深度学习的变化检测方法,以CNN实现。

    首先说下基于深度学习的变化检测任务的思路:
    制作训练样本 -> 训练模型 -> 使用训练的模型遍历图片中每个像元得出结果

    1 筛选训练样本

    第一步,通过两幅影像生成差异图。
    第二部,使用一个简单的方法对差异图进行分割,生成一幅较为粗略的二值图 。
    第三部,选取变化样本和未变化样本,选择方式一般有两种:

    • 1 从差异图中选择%T像素值最大和最小的像元,每个像元取其邻域分别作为变化样本和未变化样本;
    • 2 从生成的粗略二值图中随机选择一部分像元,每个像元根据其类别取其邻域分别作为变化样本和未变化样本;

    2 训练模型

    将制作好的变化样本和未变化样本输入模型中进行训练,模型的选择通常有:

    • 受限玻尔兹曼机(RBM),使用最多
    • 降噪自编码器(DAE)
    • 卷积神经网络(CNN)

    3 得出变化图

    直接使用训练的模型遍历图片中每个像元的邻域对每个像元进行二分类即可得出检测结果。

    虽然是走的监督学习的路线,但其并没有用到人工标注的gt,本质上该变化检测任务是一种非监督方法

    从深度学习的角度上讲,它属于图像分类的领域,相当于对每个像素的邻域(3×3,5×5,7×7,9×9)进行二分类。

    实例代码

    代码是自己写的,里面有很多地方可以完善,后续会慢慢完善,筛选样本部分耗时特别大,这里大家可自行完善一下(排序方式改一改就能快很多),或改成随机选择训练样本,注意在这个代码不更改的情况下最好只使用500×500左右的图像进行检测,太大的话会跑不动。

    输入两幅影像

    import tensorflow as tf
    import numpy as np
    import cv2 as cv
    # 读取影像
    path = 'E:/data changing2/'
    img1 = cv.imread(path+'1_1997.05.tif')
    img2 = cv.imread(path+'1_1997.08.tif')
    
    img1 = cv.copyMakeBorder(img1, 2, 2, 2, 2, cv.BORDER_REFLECT)   #给影像填充边界
    img2 = cv.copyMakeBorder(img2, 2, 2, 2, 2, cv.BORDER_REFLECT)
    
    img_row = img1.shape[0]   # 行
    img_columns = img1.shape[1]     # 列
    
    img1 = np.asarray(img1, np.float32)
    img2 = np.asarray(img2, np.float32)
    

    生成差异图和差异二值图

    img_change = []
    temp = np.longfloat(0)
    for i in range(img_row):
        for j in range(img_columns):
                temp = np.square(img1[i][j][0]-img2[i][j][0]) + np.square(img1[i][j][1]-img2[i][j][1])\
                       + np.square(img1[i][j][2]-img2[i][j][2])
                temp = np.sqrt(temp)
                img_change.append(temp)
    
    # img_change = np.asarray(img_change, np.float32)
    # max_ = img_change.max()
    # min_ = img_change.min()
    max_ = max(img_change)
    min_ = min(img_change)
    print('max = ', max_, 'min = ', min_)
    for i in range(len(img_change)):
        img_change[i] = (img_change[i]-min_)/(max_ - min_)*255
    
    # 生成差异图和差异二值图
    img_gray = [[0 for col in range(img_columns)] for row in range(img_row)]
    img_gray = np.asarray(img_gray, np.float32)
    
    k = 0
    for i in range(img_row):
        for j in range(img_columns):
            img_gray[i][j] = img_change[k]
            k += 1
    
    img_gray01 = cv.imread(path + 'FCM.bmp', 0)   # 使用一个比较粗的结果来筛选纯净样本
    img_gray01 = cv.copyMakeBorder(img_gray01, 2, 2, 2, 2, cv.BORDER_REFLECT)
    img_gray = np.asarray(img_gray, np.uint8)
    img_gray01 = np.asarray(img_gray01, np.uint8)
    
    # io.imsave(path + 'chayitu.bmp', img_gray)
    # io.imsave(path + '2zhitu.bmp', img_gray01)
    print("差异图,基础二值图生成完毕")
    

    制作训练样本
    这里采用简单选择排序,邻域大小选择为7*7.

    # 1. 给 img_change 排序(只排序(T%*2)以加快程序运行速度)   2. 选出(T% * 2)的样本作为训练数据集并生成相应的图像
    # 1
    
    # T 阈值
    T = 0.02
    T_num = int(len(img_change)*T)
    print("changdu:", len(img_change))
    print('T:', T_num)
    #  将img_change的值赋给img_change_sort(切记不能用 = !!!! 这个会共享数据)
    img_change_sort = []
    for i in range(len(img_change)):
        img_change_sort.append(img_change[i])
    label_change = []
    for i in range(len(img_change)):
        label_change.append(i)
    
    for i in range(T_num):
        temp_max = img_change_sort[i]
        img_label_1 = i
        for j in range(i, len(img_change)):
            if img_change_sort[j] > temp_max:
                temp_max = img_change_sort[j]
                img_label_1 = j
        img_change_sort[img_label_1] = img_change_sort[i]
        img_change_sort[i] = temp_max
    
        label_change[i] = label_change[img_label_1]
        label_change[img_label_1] = i
    
    for i in range(T_num):
        temp_min = img_change_sort[len(img_change_sort)-i-1]
        img_label_0 = len(img_change_sort) - i - 1
        for j in range(len(img_change)-i):
            if img_change_sort[j] < temp_min:
                temp_min = img_change_sort[j]
                img_label_0 = j
        img_change_sort[img_label_0] = img_change_sort[len(img_change_sort)-i-1]
        img_change_sort[len(img_change_sort)-i-1] = temp_min
    
        label_change[len(img_change_sort)-i-1] = label_change[img_label_0]
        label_change[img_label_0] = len(img_change_sort) - i - 1
    
    # 2
    data = []
    label = []
    data1 = []
    data0 = []
    img_1 = [[0 for col1 in range(img_columns)] for row1 in range(img_row)]
    ratio = 0.88
    data_1_count = 0
    data_0_count = 0
    for i in range(img_row):
        for j in range(img_columns):
            img_1[i][j] = 125
    for i in range(T_num):
            region = []
            row_1 = int(label_change[i]/img_columns)
            column_1 = label_change[i] % img_columns
            if row_1 < 2 or column_1 < 2 or row_1 >= (img_row-2) or column_1 >= (img_columns - 2):
                continue
            else:
                count = 0
                for k in range(row_1 - 2, row_1 + 3):
                    for l in range(column_1 - 2, column_1 + 3):
                        if img_gray01[k][l] == 255:
                            count += 1
                if count / 25 >= ratio:
                # if count / 49 >= 0.5:
                    for k in range(row_1 - 2, row_1 + 3):
                        for l in range(column_1 - 2, column_1 + 3):
                            for m in range(3):
                                region.append(img1[k][l][m])
                            for n in range(3):
                                region.append(img2[k][l][n])
                    data1.append(region)
                    data_1_count += 1
                    img_1[row_1][column_1] = 255
    data1 = np.asarray(data1, np.float32)
    
    for i in range(T_num):
            row_0 = int(label_change[len(img_change)-i-1] / img_columns)
            column_0 = label_change[len(img_change)-i-1] % img_columns
            region = []
            if row_0 < 2 or column_0 < 2 or row_0 >= (img_row-2) or column_0 >= (img_columns - 2):
                continue
            else:
                count = 0
                for k in range(row_0 - 2, row_0 + 3):
                    for l in range(column_0 - 2, column_0 + 3):
                        if img_gray01[k][l] == 0:
                            count += 1
                if count / 25 >= ratio:
                # if count / 25 >= 0.6:
                    for k in range(row_0 - 2, row_0 + 3):
                        for l in range(column_0 - 2, column_0 + 3):
                            for m in range(3):
                                region.append(img1[k][l][m])
                            for n in range(3):
                                region.append(img2[k][l][n])
                    data0.append(region)
                    # label.append(0)
                    data_0_count += 1
                    img_1[row_0][column_0] = 0
    img_1 = np.asarray(img_1, np.int64)
    cv.imwrite(path + 'xunlianyangben.bmp', img_1)
    data0 = np.asarray(data0, np.float32)
    
    c = min(data1.shape[0], data0.shape[0])
    for i in range(c):
        data.append(data1[i])
        label.append(1)
        data.append(data0[i])
        label.append(0)
    
    data = np.asarray(data, np.float32)
    label = np.asarray(label, np.int32)
    print(data_1_count, data_0_count)
    print('data.shape:', np.shape(data))
    
    # 打乱样本顺序
    num_example = data.shape[0]
    arr = np.arange(num_example)
    np.random.shuffle(arr)
    data = data[arr]
    label = label[arr]
    

    制作测试样本
    测试样本就是直接遍历整幅影像,它经过模型后输出的便是变化检测结果, 这里发现如果一个列表太大的时候会出现问题,就分成两个数组分别保存了

    # 制作测试样本
    data_test = []
    label_test = []
    for i in range(202):
        for j in range(img_columns):
            if i < 2 or j < 2 or i >= (img_row-2) or j >= (img_columns - 2):
                continue
            else:
                region = []
                for k in range(i - 2, i + 3):
                    for l in range(j - 2, j + 3):
                        for m in range(3):
                            region.append(img1[k][l][m])
                        for n in range(3):
                            region.append(img2[k][l][n])
                data_test.append(region)
                label_test.append(img_gray01[i][j]/255)
    data_test = np.asarray(data_test, np.float32)
    label_test = np.asarray(label_test, np.int32)
    
    data_test1 = []
    label_test1 = []
    for i in range(202, img_row):
        for j in range(img_columns):
            if i < 2 or j < 2 or i >= (img_row-2) or j >= (img_columns - 2):
                continue
            else:
                region = []
                for k in range(i - 2, i + 3):
                    for l in range(j - 2, j + 3):
                        for m in range(3):
                            region.append(img1[k][l][m])
                        for n in range(3):
                            region.append(img2[k][l][n])
                data_test1.append(region)
                label_test1.append(img_gray01[i][j]/255)
    data_test1 = np.asarray(data_test1, np.float32)
    label_test1 = np.asarray(label_test1, np.int32)
    

    创建并训练模型

    data = np.reshape(data, [len(data), 5, 5, 6])
    data_test = np.reshape(data_test, [len(data_test), 5, 5, 6])
    data_test1 = np.reshape(data_test1, [len(data_test1), 5, 5, 6])
    # -----------------构建网络----------------------
    # 占位符
    x = tf.placeholder(tf.float32, shape=[None, 5, 5, 6], name='x')
    y_ = tf.placeholder(tf.int32, shape=[None, ], name='y_')
    
    
    # 第一个卷积层(5——>5)
    conv1 = tf.layers.conv2d(
        inputs=x,
        filters=32,
        kernel_size=[3, 3],
        padding="same",
        activation=tf.nn.relu,
        kernel_initializer=tf.truncated_normal_initializer(stddev=0.01))
    
    # 第二个卷积层(5->5)
    conv2 = tf.layers.conv2d(
        inputs=conv1,
        filters=32,
        kernel_size=[3, 3],
        padding="same",
        activation=tf.nn.relu,
        kernel_initializer=tf.truncated_normal_initializer(stddev=0.01))
    pool1 = tf.layers.max_pooling2d(inputs=conv2, pool_size=[2, 2], strides=1)
    
    re1 = tf.reshape(pool1, [-1, 4 * 4 * 32])
    
    # 全连接层
    logits = tf.layers.dense(inputs=re1,
                             units=2,
                             activation=tf.nn.softmax,
                             kernel_initializer=tf.truncated_normal_initializer(stddev=0.01),
                             kernel_regularizer=tf.contrib.layers.l2_regularizer(0.003))
    
    
    loss = tf.losses.sparse_softmax_cross_entropy(labels=y_, logits=logits)
    train_op = tf.train.AdamOptimizer(learning_rate=0.001).minimize(loss)
    correct_prediction = tf.equal(tf.cast(tf.argmax(logits, 1), tf.int32), y_)
    acc = tf.reduce_mean(tf.cast(correct_prediction, tf.float32))
    
    
    # 定义一个函数,按批次取数据
    def minibatches(inputs=None, targets=None, batch_size=None, shuffle=False):
        assert len(inputs) == len(targets)
        if shuffle:
            indices = np.arange(len(inputs))
            np.random.shuffle(indices)
        for start_idx in range(0, len(inputs) - batch_size + 1, batch_size):
            if shuffle:
                excerpt = indices[start_idx:start_idx + batch_size]
            else:
                excerpt = slice(start_idx, start_idx + batch_size)
            yield inputs[excerpt], targets[excerpt]
    
    
    # 训练CNN模型,可将n_epoch设置更大一些
    
    n_epoch = 20
    batch_size = 128
    sess = tf.InteractiveSession()
    sess.run(tf.global_variables_initializer())
    for epoch in range(n_epoch):
        start_time = time.time()
    
        # training
        train_loss, train_acc, n_batch = 0, 0, 0
        for x_train_a, y_train_a in minibatches(data, label, batch_size, shuffle=True):
            _, err, ac = sess.run([train_op, loss, acc], feed_dict={x: x_train_a, y_: y_train_a})
            train_loss += err
            train_acc += ac
            n_batch += 1
        print("   train loss: %f" % (train_loss / n_batch))
        # print("   train acc: %f" % (train_acc / n_batch))
    

    将测试样本输入训练过模型得出最终结果

    # 用训练好的模型得出结果
    final_img = []
    final = sess.run(logits, feed_dict={x:  data_test, y_: label_test})
    for i in range(len(data_test)):
        if final[i][0] >= final[i][1]:
            finals = 0
        else:
            finals = 255
        final_img.append(finals)
    print(len(final_img))
    k = 0
    
    img_final2 = [[125 for i in range(img_columns-4)] for j in range(img_row-4)]
    for i in range(200):
        for j in range(img_columns-4):
            img_final2[i][j] = final_img[k]
            k += 1
    
    final_img1 = []
    final1 = sess.run(logits, feed_dict={x:  data_test1, y_: label_test1})
    for i in range(len(data_test1)):
        if final1[i][0] >= final1[i][1]:
            finals = 0
        else:
            finals = 255
        final_img1.append(finals)
    print(len(final_img1))
    k = 0
    for i in range(img_row-4-200):
        for j in range(img_columns-4):
            img_final2[i+200][j] = final_img1[k]
            k += 1
    
    img_final2 = np.asarray(img_final2, np.uint8)
    cv.imwrite(path + 'final/2zhitu_final_not_use_CNN_5_new.bmp', img_final2)
    sess.close()
    

    完整代码: https://blog.csdn.net/weixin_39853245/article/details/97670214

    展开全文
  • 封装变化

    2017-11-16 12:38:00
    变化时候是无穷尽的,于是项目开发就在反复的修改更新中无限期地延迟交付的日期。变化如悬在头顶的达摩克斯之剑,令许多软件工程专家一筹莫展。正如无法找到解决软件开发的“银弹”,要彻底将变化扼杀在摇篮之中,...
  • 在数据库设计过程中我们要本着够用的原则,如果一味的把数据字段范围设最大或者默认值的话,会导致存储空间大量的浪费。在数据量特别大的情况下,这样的设计原理将会使数据库空间造成严重的浪费,也会对数据库的...
  • Matlab 用sort函数排序

    2021-04-18 14:00:59
    help文档中第一句就说明,可以用sort将参量中的元素按升序或降序排列~格式:B = sort(A)...若 A 复数的,则按元素幅值的从小到大排列,若有幅值相同的复数元素,则再按它们在区间[-π ,π]的幅角从小到大排列;若 ...
  • 一个日志表中记录了某个商户费率变化状态的所有信息, 现在有个需求,要取出按照时间轴顺序, 发生了状态变化的数据行; 建表语句 create table shop( id string, rate string, rq date ); 数据 insert into...
  • 数组排序——快速排序

    千次阅读 2018-04-18 09:55:25
    数组排序——快速排序1、数组排序之快速排序 一趟快速排序的算法是: 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1; 2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0]; 3)从j开始向前搜索,即由...
  • 定义json如下,希望转换下给...原因:因为key数字,默认的就会按照key值进行排序。 解决办法:key“字符+数字”,其中的数字可以和对象中的id值保持一致,方便后续根据前端传递的id直接定位是哪个对象。 ...
  • 引:2019年408中数据结构一道考察快速排序的选择题 定位:这道题在考察快速排序中一趟的概念。 思路: 回想教材(《数据结构》严)里对一趟的定义 算法描述: 可见第一张图的过程实际上是递归形式实现的...
  • 关于左连接查询出现排序问题

    千次阅读 2019-05-23 12:07:08
    最近在项目中遇到,limit 分页查询,查看最后一条记录时出现和预想的结果不一样的情况,本身是应该出现主表的最后几条数据,但是并没有。出现了中间的顺序。 经过自己多次的检查最后不要 limit 查询的结果大吃一惊...
  • 使用JS实现数值动态变化动画效果

    千次阅读 2020-06-03 15:43:42
    本文主要回顾整理一下之前(大概一年前,????,这一年实在比较忙 )写的一个页面...一、滚动式变化 这一种的呈现方式也是我在项目中最终应用的方式,个人觉得更好看一点 ???? 1.关于实现原理 其实想要实现这种滚动式
  • 排序算法系列:基数排序

    万次阅读 多人点赞 2016-06-16 23:14:07
    这也是基数排序的魅力所在,基数排序可以理解成是建立在“计数排序”的基础之上的一种排序算法。在实际项目中,如果对效率有所要求,而不太关心空间的使用时,我会选择用计数排序(当然还有一些其他的条件),或是...
  • 执行任务的时候,为了提高编译器和处理器的执行性能,编译器和处理器(包括内存系统,内存在行为没有重排但是存储的时候是有变化的)会对指令重排序。编译器优化的重排序是在编译时期完成的,指令重排序和内存重排序是...
  • 现在有某区域的高分影像和对应范围的土地利用现状数据,现在的耕地面积比二调大了很多,需要把没有备案的土地清查出来。简单的说就是要找出哪些绿地是新增的或者由其他用地类型转化而来的。 2.总体技术路线 (1)...
  • 在数据库设计过程中我们要本着够用的原则,如果一味的把数据字段范围设最大或者默认值的话,会导致存储空间大量的浪费。在数据量特别大的情况下,这样的设计原理将会使数据库空间造成严重的浪费,也会对数据库的...
  • 写django的时候,我有个模板的名字叫detail.html,被detail视图函数渲染 因为那个detail写乱了,但是里面有东西要参考,我删掉... 改了几次,发现怎么改,前端都不变,为什么??????? Django能自动关联,准确的说应该是...
  • volatile 变量提供了线程的可见性,并不能保证线程...什么是线程的可见性: 锁提供了两种主要特性:互斥(mutual exclusion) 和可见性(visibility)。互斥即一次只允许一个线程持有某个特定的锁
  • 对于缓慢变化维的历史数据的处理

    千次阅读 2014-05-20 10:56:15
    在做数据仓库的时候有一个备件维度,该维度由两张表构成。 一张是
  • 一、说在前面的话 一些涉及数据分析处理的系统,常常...需要计算同一张表前后两次的全量数据计算变化量,这种变化量数据包括insert、update、delete等,后续分析处理只针对这些变化量数据进行,由于业务系统中变化...
  • Angular应用的变化(Component属性的变化和DOM的变化)分成2个阶段(按发生先后顺序排序): 异步事件发生(比如用户点击或者AJAX请求完成),注册的回调函数被执行(比如 (click)="handler($event)"> ),这些回...
  • 排序1-几大经典排序算法

    千次阅读 2019-03-03 20:32:58
    本文仅先对一些经典的排序算法做一个比较简略的综述,后续会按照本文的算法列表顺序来进行逐个地实现以及剖析优化。本系列是自己学习过程中的总结,所以不免会记录一些看起来比较无聊的概念之类的东西,并且会有很多...
  • 前几天刚做完排序,本来以为没什么问题的,结果今天被告知要优化一下。。功能上是问题,但是有一些小细节需要优化。比如我做的是每次拖拽完成之后,都在stop方法里面请求ajax保存顺序。但是要考虑到,有时候用户...
  • 1. 发球的变化:原来发五个球,可以根据对方的技术情况,发五种不同的球,或某五种球的某种排列组合,现在,每次发2个球,只能发两种不同的球,或某2种球的某种排列组合。那么发球变化少了很多,那么得分就会发生...
  • 大数据时代的到来改变了人们的生活方式、思维模式和研究范式,我们可以总结出 10 个重大变化,如图 1 所示。 图 1大数据时代的 10 个重大变化 对研究范式的新认识:从第三范式到第四范式 2007 年 1 月,图灵奖...
  • 排列熵(permutation entropy)

    万次阅读 热门讨论 2019-02-23 11:48:58
    排列熵算法是一种动力学突变检测方法,能够方便、准确的定位系统发生突变的时刻,并且对于信号的微小变化具有放大作用1 2 排列熵的计算步骤 1、对时间序列X进行相空间重构(相空间大小记m),得到矩阵。矩阵的每一...
  • 大根堆与小根堆的理解,如何手写一个堆,以及什么时候用自己手写的堆,什么时候用语言提供堆的api,(二者的区别) 定义 Heap是一种数据结构具有以下的特点: 1)完全二叉树; 2)heap中存储的值是偏序; Min-heap: ...
  • 当DELETE后面跟条件的时候,...delete from table_name清除了数据,同时数据表的空间也会变为0如果已经删除了表数据的很大一部分,或者有很多变化和变长表行(VARCHAR表,VARBINARY、BLOB或文本列)进行了更改,因为删...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 274,351
精华内容 109,740
关键字:

为什么排序的时候没有变化