精华内容
下载资源
问答
  • 由于不可抗力原因导致拖更两天,很是惭愧,今天尽量多更一点~社 畜 之 泪插入排序 (Insertion Sort)算法思想插入排序的算法思想也很直观:每次待排序数组中取个元素,在已排序数组中找到其应该在的位置插入,...

    4895b11625d46716b7ba34dc007daee0.png

    由于不可抗力原因导致拖更两天,很是惭愧,今天尽量多更一点~

    2e543108be5179c98ada623300a828e3.png
    社 畜 之 泪

    插入排序 (Insertion Sort)

    算法思想

    插入排序的算法思想也很直观:每次从待排序数组中取一个元素,在已排序数组中找到其应该在的位置插入,后面的元素则依次向后移动一位。

    算法步骤

    1. 第一个元素默认已有序;
    2. 取下一个待比较元素,从已排序的序列中从后往前扫描;
    3. 如果当前已排序序列元素 > 当前待比较元素,则已排序序列元素向后移动一个位置;
    4. 重复直到将待比较元素插入到已排序序列中;
    5. 重复上述操作直到所有元素有序。

    动图更直观~ 图片来自网络

    59647b7ab4d0ebddab6253c611aa3205.gif
    可以看到,只需要O(1)额外空间

    代码实现

    def Insertion_Sort(arr): 
        for i in range(1, len(arr)): 
            tmp = arr[i] 
            j = i-1
            while j >=0 and tmp < arr[j] : 
                    arr[j+1] = arr[j] 
                    j -= 1
            arr[j+1] = tmp

    a5d2383e65bb9c1a39e5bf3bce6dffd8.png

    改进思路

    由于比较操作是从有序序列从后向前遍历比较,这样复杂度会比较大,可以考虑使用二分查找法,减少比较次数。但是由于交换的次数是不会改变的,所以算法时间复杂度仍然是

    二分查找可参考剑指offer中37题 数字在排序数组中出现的次数~

    嘿我头发呢:《剑指offer》python实现 合集(下)zhuanlan.zhihu.com
    15beb217f7171f2346b25abe9bba1ba2.png
    def bin_search(data, k):
            low = 0
            high = len(data) - 1
            while low <= high:
                mid = int((high - low)/2 +low)
                if data[mid] < k:
                    low = mid + 1
                elif data[mid] > k:
                    high = mid - 1
                elif data[mid] == k:
                    return mid
            return low # low位置就是要插入的index
    
    def bin_Insertion_Sort(array): 
        for i in range(1, len(array)): 
            tmp = array[i]
            j = bin_search(array[:i], array[i])
            t = i
            while t > j:
                array[t] = array[t-1]
                t -= 1 
            array[j] = tmp
            # print(array)

    3b6e9a6a72dbbd374713adf3f470ada0.png

    总结

    • 如果当前待排序元素与已排序序列中存在相同值元素,那么按照插入排序,会将当前元素放在已排序元素后面。相等元素的前后顺序没有改变,所以插入排序是稳定的。
    • 当序列已经是从小到大排序,最优情况,插入排序只需要比较 n-1 次;
    • 当序列是从大到小的逆序,最差情况,插入排序需要比较 1+...+n-1 = n(n-1)/2
    • 平均来说,即使是优化过的插入排序,其时间复杂度也是
    • 由于交换操作,插入排序空间复杂度

    最后附上维基百科对插入排序的解读~

    插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千;或者若已知输入元素大致上按照顺序排列,那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用,在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快速排序的补充,用于少量元素的排序(通常为8个或以下)。
    展开全文
  • 二进制/进制转换器

    2018-01-02 20:19:00
    题目要求 编写一段程序,要求...(2)转换时,要将二进制的每位转换成进制的一位,先得到的是进制的低位数,因此可以将进制数保存到一新的栈B,知道将栈A元素取完为止。 (3)最后将栈B

    题目要求
    编写一段程序,要求从终端输入一串0/1表示的二进制数,输出它的八进制表达形式。
    题目分析
    进行数制转换这类运算最简单的方法就是使用栈的数据结构。
    (1)在输入二进制数时,将每次输入的0/1压入栈A中保存。
    (2)转换时,要将二进制的每三位转换成八进制的一位,先得到的是八进制的低位数,因此可以将八进制数保存到一个新的栈B中,知道将栈A中的元素取完为止。
    (3)最后将栈B 中的八进制逐一取出显示即可。
    (初始化,入栈,出栈等) 进制存储用ASCII码值。


    程序如下:

    #include"stdio.h"
    #include"math.h"
    #define STACK_INIT_SIZE 20
    #define STACKINCREMENT 10
    
    typedef char Elemtype;
    typedef struct {
      Elemtype *top;
      Elemtype *base;
      int stacksize;
    }sqstack;
    
    //初始化栈
    void initstack(sqstack *s)
    {
        //内存中开辟一段连续的空间作为栈空间,首地址给s->base
        s->base=(Elemtype *)malloc(sizeof(Elemtype)*STACK_INIT_SIZE);
        if(!s->base) exit(0);
        s->top=s->base;
        s->stacksize=STACK_INIT_SIZE;
     }
    
     //入栈操作,将e压入栈中
     void push(sqstack *s,Elemtype e)
     {
        if(s->top-s->base>=s->stacksize)
        s->base=(Elemtype *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(Elemtype));
        if(!s->base) exit(0);
        s->top=s->base+s->stacksize;        //追加空间首地址加上原大小为顶
        s->stacksize=s->stacksize+STACKINCREMENT;  
        *(s->top)=e;
        s->top++;
     }
    
     //出栈操作,用e将栈顶元素返回
     void pop(sqstack *s,Elemtype *e)
     {
         if(s->top==s->base)  return ;
         *e=*--(s->top);
     }
    
     //计算栈当前长度
     int stacklen(sqstack *s)
     {
        return(s->top-s->base);
     }
    
     main()
    {
          sqstack s1,s2;
          Elemtype c;
          int len,i,j,sum=0;
          initstack(&s1);
          printf("Please input a binary number and type # for end\n");
          scanf("%c",&c);
          while(c!='#')
          {
             if('c'==0||'c'==1)
                   push(&s1,c);
             scanf("%c",&c);
          }    
          initstack(&s2);
          len=stacklen(&s1);
          for(i=0;i<len;i=i+3)
          {
              for(j=0;j<3;j++)
             {
                 pop(&s1,&c);
                 sum=sum+(c-48)*pow(2,j);
                 if(s1.top==s1.base) break;  //有可能不是3的倍数
             }
             push(&s2,sum+48);
             sum=0;                         //计算八进制每一位时别忘了sum清0
          }
         //输出八进制内容
          while(s2->top!=s2->base)
        {
            pop(&s2,&c);
            printf("%d",c);
         }
        getche();
    }
    展开全文
  • 200经典C程序【源码】

    千次下载 热门讨论 2013-08-08 10:48:40
    028 键盘读入实数 029 字符行排版 030 字符排列 031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件的字符数 ...
  • 【1】案例分析【百度百科】:n个不同元素中m(m≤n)个元素,按照一定的顺序排列起来,叫做n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。 a,b,c,d的全排列如下(程序生成)a b ...

    偶尔刷题,经常遇到需要全排列的地方,一直想用for循环做(n层),理论上是可行的,,可是实际(两三层还行,十层八层,n层,不太合适吧),再次重温一下全排列算法。



    【1】案例分析

    【百度百科】:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
    a,b,c,d的全排列如下(程序生成)

    a  b  c  
    a  c  b  
    b  a  c  
    b  c  a  
    c  b  a  
    c  a  b  



    【2】设计思想

    采用递归的思想,,(以{“a”, “b”, “c”}为例。)
    【1】由于每个元素只能使用一次,所以主要使用交换的方式。
    【2】先挑选第一个位置的元素,将a和a,b,c,三个都交换一次(a和a交换保证能选择到a)
    【3】挑完第一个使用递归挑选下一个,重读【2】

    执行流程图如下:
    这里写图片描述



    【3】算法实现

    package algorithm_1;
    
    /**
     * Created by zsl on 2017/8/20.
     */
    public class FullPermutation {
        public static int total = 0;
    
        public static void main(String[] args) {
            String str[] = {"a", "b", "c"};
            arrange(str, 0, str.length);
            System.out.println(total);
        }
    
        /**
         * 交换str数组的 i和 j。
         *
         * @param str
         * @param i
         * @param j
         */
        public static void swap(String[] str, int i, int j) {
            String temp = new String();
            temp = str[i];
            str[i] = str[j];
            str[j] = temp;
        }
    
        /**
         * 对str数组,,从st到len进行全排列
         *
         * @param str
         * @param st
         * @param len
         */
        public static void arrange(String[] str, int st, int len) {
            if (st == len - 1) {
                for (int i = 0; i < len; i++) {
                    System.out.print(str[i] + "  ");
                }
                System.out.println();
                total++;
            } else {
                for (int i = st; i < len; i++) {
                    swap(str, st, i);
                    arrange(str, st + 1, len);
                    swap(str, st, i);
                }
            }
    
        }
    }
    
    展开全文
  • 部分 数值计算与趣味数学篇 075 绘制余弦曲线和直线的迭加 076 计算高次方数的尾数 077 打鱼还是晒网 078 怎样存钱以获取最大利息 079 阿姆斯特朗数 080 亲密数 081 自守数 082 具有...
  • // 噢,忘了教长吧,让我们添加一个元素 $myphonebook["dean"] = "5397"; // 你定义的carale元素错了,让我们更正它 $myphonebook["carole"] => "4522" // 我还没有告诉你怎样使用数组的相似支持...
  • 028 键盘读入实数 029 字符行排版 030 字符排列 031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件的字符数 ...
  • 028 键盘读入实数 029 字符行排版 030 字符排列 031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件的字符数 ...
  • VBSCRIPT中文手册

    热门讨论 2010-11-12 10:13:06
    For Each...Next 语句 对于数组或集合的每一个元素,重复一组语句。 FormatCurrency 函数 返回的表达式为货币值格式,其货币符号采用系统控制面板定义的。 FormatDateTime 函数 返回格式化为日期或时间的...
  • 输入一个数,要求用折半查找法找出该数是数组第几个元素的值。如果该数不在数组,输出“不在表”。 39 7.10有一篇文章,共有3行文字,每行有80个字符。要求分别统计出其中英文大写字母,小写字母,数字,空格...
  • 028 键盘读入实数 029 字符行排版 030 字符排列 031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件的字符数 ...
  • For Each...Next 语句 对于数组或集合的每一个元素,重复一组语句。 FormatCurrency 函数 返回的表达式为货币值格式,其货币符号采用系统控制面板定义的。 FormatDateTime 函数 返回格式化为日期或时间的...
  • 例如,可以通过 scores[0] 获取数组的第一个元素 ,scores[2] 就可以到第三个元素! 而排序就是将这些数据按一定的顺序依次排列。 排序的方法有种 这里注重介绍选择排序和冒泡排序: (1)选择排序

    数组可以理解为是一个巨大的“盒子”,里面可以放多个类型相同的数据。数组中的每一个元素都有一个下标,所以可以通过下标来访问,下标从 0 开始。例如,可以通过 scores[0] 获取数组中的第一个元素 ,scores[2] 就可以取到第三个元素!
    而排序就是将这些数据按一定的顺序依次排列。
    排序的方法有八种这里写图片描述
    这里注重介绍选择排序和冒泡排序:
    (1)选择排序:
    每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

        //选择排序
        public void selectSort(int [] a) {
            int n = a.length;
            for(int k=0; k<n-1; k++) {
                int min = k;
                for(int i=k+1; i<n; i++) {
                    if(a[i] < a[min]) {
                        min = i;
                    }
                }
                if(k != min) {
                    int temp = a[k];
                    a[k] = a[min];
                    a[min] = temp;
                }
            }
        }

    (2)冒泡排序
    冒泡排序是将数组中两个相邻的元素进行两两对比,将小的往上升,大的往下沉。所以取名为冒泡排序

    public static void main(String[] orgs){
        int[] arr = {21,52,36,15,65,57};
        int  temp;
        for (int a = 0; a<arr.length-1;a++ )
        {
            for (int b = 1+a ; b<arr.length-1-a;b++)
               { 
                  if(arr[a]>arr[b])
                    {
                        temp = arr[a];
                        arr[a] = arr[b];
                        arr[b] = temp;
                    }
               }
        } 
    }
    
    展开全文
  • 面试题3:二维数组的查找:对于在一个每一行左到右依次递增,每一列上到下依次递增的二维数组查找一个元素,可以选择数组左上角开始查找array[i][j],如果目标元素大于array[i][j],i+=1,如果元素小于array...
  • 编程语言都有自己的内置函数,这些函数是不需要方文件导入的,可以直接使用的。也就是说,它们是Python的基础,Python学得好不好,就看这些内置函数用得熟不熟。 基础运算函数 abs(): 绝对值 all()...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    2. 对于给定的 n个元素,可以构造出的逻辑结构有 (1)集合 , (2)线性结构 , (3)树型结构 ,_图状结构_(4)_四种。 【中科院计算所 1999 二、1(4分)】 3.数据的逻辑结构是指(数据的组织形式,即数据元素...
  • 例如pf1和pf2 是指向同一浮点数组的两个指针变量,设pf1的值为2010H,pf2的值为2000H,而浮点数组每个元素占4个字节,所以pf1-pf2的结果为(2000H-2010H)/4=4,表示pf1和 pf2之间相差4个元素。两个指针变量不能进行...
  • 数据结构与算法.xmind

    2020-06-19 17:04:23
    递归拆分出两有序的数组,mid的位置开始拆分,递归出口:只有一值的时候就不用拆分了 合并两有序的数据 分别往两数组填充已有序的数据 比较两数组的值谁小,谁小就放到我们的...
  • JAVA面试题最全集

    2010-03-13 13:09:10
    数据结构,如何遍历List元素? 如果要按照键值保存或者访问数据,使用什么数据结构? 要掌握Collection相关的接口和类的使用 56.使用StringBuffer类与String类进行字符串连接时有何区别? 57.调用Thread类的...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    <br>实验四 综合(课程设计) 内容及步骤: 1、假定一维数组a[n]的每个元素值均在[0,200]区间内,用C++编写一个算法,分别统计出落在[0,20],[21,50],[51,80],[81,130],[131,200]等各区间内的元素...
  • VBSCRIP5 -ASP用法详解

    2010-09-23 17:15:46
    For Each...Next 语句 对于数组或集合的每一个元素,重复一组语句。 FormatCurrency 函数 返回的表达式为货币值格式,其货币符号采用系统控制面板定义的。 FormatDateTime 函数 返回格式化为日期或时间的...
  • vb Script参考文档

    2009-07-28 22:13:02
    For Each...Next 语句 对于数组或集合的每一个元素,重复一组语句。 FormatCurrency 函数 返回的表达式为货币值格式,其货币符号采用系统控制面板定义的。 FormatDateTime 函数 返回格式化为日期或时间的...
  • 具体分为三个阶段:静态代理,动态代理,还有CGLIB代理。 以动态代理来说,测试动态代理加强类时,创建main方法直接测试即可: /** * 测试 * @param args */ public static void main(String[] args) { ...
  • VBScript 语言参考

    2008-10-07 21:30:05
    For Each...Next 语句 对于数组或集合的每一个元素,重复一组语句。 FormatCurrency 函数 返回的表达式为货币值格式,其货币符号采用系统控制面板定义的。 FormatDateTime 函数 返回格式化为日期或时间的...
  • 正则表达式

    2014-12-03 14:51:39
    这些复杂的模式使用的正则表达式语法指定了该表达式个元素要重复出现的次数. 指定复制的字符总是出现在它们所作用的模式后面.由于某种复制类型相当常用.所以有一些特殊的字符专门用于表示它们.例如: +号匹配的...
  • 算法导论(part2)

    2010-09-09 22:54:12
    ·为了使更多的算法可以更早地在书出现,第1版有关数学背景知识的章内容第一部分移到了附录,即现在的第部分。 ·新增了40多思考题和超过185练习题。 ·明确地使用循环不变式来证明算法的正确性。...
  • 算法导论(part1)

    2010-09-09 22:51:05
    ·为了使更多的算法可以更早地在书出现,第1版有关数学背景知识的章内容第一部分移到了附录,即现在的第部分。 ·新增了40多思考题和超过185练习题。 ·明确地使用循环不变式来证明算法的正确性。...

空空如也

空空如也

1 2 3 4 5
收藏数 90
精华内容 36
关键字:

从八个元素中取三个