程序算法

  • Python里实现快速排序的方法

    Python里实现快速排序的方法

    快速排序由C. A. R. Hoare在1962年提出,它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。具体实现步骤如下:1、先从数列中取出一个数作为基准数2、分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边3、再对左右区间重复第二步,直到各区间只有一个数网上搜了个示意图如下:Python里代码实现:# Autor:...

  • Python里实现二分查找算法

    Python里实现二分查找算法

    二分查找也称折半查找,它是一种效率较高的查找方法。但是二分查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。同时二分查找算法也是面试中经常会考到的一个算法,所以一定要弄清楚原理!二分查找的时间复杂度O(logn),至于为什么是O(logn),有兴趣的童靴可以查查推导方法。本文主要讲解Python里如何实现二分查找算法,分递归和非递归两种方式。具体代码如下:# Autor: 5bug # WebSite: http://www.XuePython.wang...

  • 常用排序算法稳定性分析

    常用排序算法稳定性分析

    排序算法的稳定性通俗点说就是同样一组数据,使用某些排序算法的时候,是否会出现排列的结果的某些元素位置不一样的情况。本文主要是介绍几种常见的排序算法的稳定性,以及简单的理由。冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。选择排序选择排序是...

    程序算法 2018-02-01 661 0 排序算法
  • Python里实现LZW压缩解压缩算法

    Python里实现LZW压缩解压缩算法

    压缩算法是编程的时候经常会用到的一种算法,本文主要是提供了LZW压缩算法在Python里的具体实现过程!LZW 压缩算法string = "thisisthe" dictionary = {chr(i):i for i in range(97,123)}   last = 256 p = "" result = []...

    程序算法 2018-01-22 757 0
  • Python里实现求最长的回文子串长度

    Python里实现求最长的回文子串长度

    给定一个字符串,求它最长的回文子串长度,例如输入字符串'35534321',它的最长回文子串是'3553',所以返回4。最容易想到的办法是枚举出所有的子串,然后一一判断是否为回文串,返回最长的回文子串长度。不用我说,枚举实现的耗时是我们无法忍受的。那么有没有高效查找回文子串的方法呢?答案当然是肯定的,那就是中心扩展法,选择一个元素作为中心,然后向外发散的寻找以该元素为圆心的最大回文子串。但是又出现了新的问题,回文子串的长度即可能是基数,也可能好是偶数,对于长度为偶数的回文子串来说是不...

  • Python里实现基数排序

    Python里实现基数排序

    本文主要讲解的是Python里基数排序的实现方法。思路  首先准备0号桶~9号桶:      根据个位上的数值选择几号桶,后再将数字依次倒出桶:        根据序列的顺序十位上的数值选择几号桶,后再将数字依次倒出桶:        根据序列的顺序百位上的数值选择几号桶,后再将数字依次倒出桶,最后一次倒出桶的顺序就是排序的顺序:      Python实现# -*- coding:utf-8 -*- class RadixSort:   &nbs...

  • Python里实现计数排序

    Python里实现计数排序

    本文主要讲解的是Python里计数排序的实现方法。概要   时间复杂度O(n),空间复杂度O(k),k是输入序列的值的范围(最大值-最小值),是稳定的。计数排序一般用于已知输入值的范围相对较小,比如给公司员工的身高体重信息排序。思路  输入数组A为{3,5,1,2,4,3},值的范围是1~5,所以创建5个桶,序号1,2,3,4,5。装桶时遍历一遍输入数组,A[0]=3,把它放到3号桶;A[1]=5,放到5号桶;1放到1号桶……最后3放到3号桶。现在三号桶的值为2,其他桶的值为1,再遍历一遍桶数组,按顺序把桶倒出,元...

  • Python实现冒泡法排序算法

    Python实现冒泡法排序算法

    冒泡法排序算是一个入门级的算法了,但在很多面试场合中会经常面试官拿来考面试者的,由于在实际工作中,很多算法都被封装为现成的可以直接使用的库了,相信有大部分人都忘记了一些算法的底层实现方式了。吾八哥也借着刚刚接触学习Python的机会,把常用的算法都用Python来实现一遍,今天这里分享的是冒泡法排序。冒泡法排序原理排序的原理是比较相邻的两个元素,如果顺序不对,就进行交换,一直这样交换到顺序正确为止。Python实现冒泡法排序根据排序原理,我们需要从头到尾的去比较相邻的两个元素的顺序然后进行交换,具体实现代码如下:#...

  • Python实现插入排序算法

    Python实现插入排序算法

    今天来用Python实现插入排序算法,每种算法看起来简单,但一定得自己动手写一次了解具体的原理,这样才能加深理解!插入排序原理插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种,今天我们实现直接插入排序算法。Python实现插入排序算法具体代码如下:# Autor: 5bug # WebSite: http://www.5bug.wang # 吾八哥网技术交流QQ群:&nbs...

  • 用Python解答百度测试开发算法面试题

    用Python解答百度测试开发算法面试题

    吾八哥本人之前有幸能接到百度北京总部的人工智能测试开发岗位的面试机会,在二面的过程中,面试官出了一道算法题,题目是:有一组“+”和“-”符号,要求将“+”排到左边,“-”排到右边,写出具体的实现方法。很明显这是一道排序算法题,基本上随便哪种算法都能实现,但这显然不是面试官要的答案,但是何种算法最合适呢?当时紧张的气氛下,开始是想到从头循环到尾部,遇到“-”就移动到尾部,将尾部的数据跟首位的数据交换。不过面试官提醒了下说如果起始和结束都是“-”呢?一想吧,确实是的,那就死循环了,后来再仔细想了下,这个得头部和尾部一起...

1