[转]经典排序算法总结与实现

经典排序算法在面试中占有很大的比重,也是基础,为了未雨绸缪,在寒假里整理并用Python实现了七大经典排序算法,包括冒泡排序,插入排序,选择排序,希尔排序,归并排序,快速排序,堆排序。希望能帮助到有需要的同学。之所以用Python实现,主要是因为它更接近伪代码,能用更少的代码实现算法,更利于理解。

本篇博客所有排序实现均默认从小到大。

作者CN: 伍 翀(WuChong) | EN: Jark

原文地址:http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/

一、冒泡排序 BubbleSort

介绍:

冒泡排序的原理非常简单,它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。

步骤:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对第0个到第n-1个数据做同样的工作。这时,最大的数就“浮”到了数组最后的位置上。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

源代码:(python实现)

def bubble_sort(arry):
    n = len(arry)                   #获得数组的长度
    for i in range(n):
        for j in range(1,n-i):
            if  arry[j-1] > arry[j] :       #如果前者比后者大
                arry[j-1],arry[j] = arry[j],arry[j-1]      #则交换两者
    return arry

不过针对上述代码还有两种优化方案。

优化1:某一趟遍历如果没有数据交换,则说明已经排好序了,因此不用再进行迭代了。用一个标记记录这个状态即可。
优化2:记录某次遍历时最后发生数据交换的位置,这个位置之后的数据显然已经有序,不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。

这两种优化方案的实现可以详见这里

二、选择排序 SelectionSort

介绍:

选择排序无疑是最简单直观的排序。它的工作原理如下。

步骤:

  1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
  2. 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  3. 以此类推,直到所有元素均排序完毕。

源代码:(python实现)

def select_sort(ary):
    n = len(ary)
    for i in range(0,n):
        min = i                             #最小元素下标标记
        for j in range(i+1,n):
            if ary[j] < ary[min] :
                min = j                     #找到最小值的下标
        ary[min],ary[i] = ary[i],ary[min]   #交换两者
    return ary

三、插入排序 InsertionSort

介绍:

插入排序的工作原理是,对于每个未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

步骤:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果被扫描的元素(已排序)大于新元素,将该元素后移一位
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

排序演示:

Enjoy it! 1

源代码:(python实现)

def insert_sort(ary):
    n = len(ary)
    for i in range(1,n):
        if ary[i] < ary[i-1]:
            temp = ary[i]
            index = i           #待插入的下标
            for j in range(i-1,-1,-1):  #从i-1 循环到 0 (包括0)
                if ary[j] > temp :
                    ary[j+1] = ary[j]
                    index = j   #记录待插入下标
                else :
                    break
            ary[index] = temp
    return ary

四、希尔排序 ShellSort

介绍:

希尔排序,也称递减增量排序算法,实质是分组插入排序。由 Donald Shell 于1959年提出。希尔排序是非稳定排序算法。

希尔排序的基本思想是:将数组列在一个表中并对列分别进行插入排序,重复这过程,不过每次用更长的列(步长更长了,列数更少了)来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身还是使用数组进行排序。

例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了,然后再以3为步长进行排序:

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为:

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序(此时就是简单的插入排序了)。

源代码:(python实现)

def shell_sort(ary):
    n = len(ary)
    gap = round(n/2)       #初始步长 , 用round四舍五入取整
    while gap > 0 :
        for i in range(gap,n):        #每一列进行插入排序 , 从gap 到 n-1
            temp = ary[i]
            j = i
            while ( j >= gap and ary[j-gap] > temp ):    #插入排序
                ary[j] = ary[j-gap]
                j = j - gap
            ary[j] = temp
        gap = round(gap/2)                     #重新设置步长
    return ary

上面源码的步长的选择是从n/2开始,每次再减半,直至为0。步长的选择直接决定了希尔排序的复杂度。在维基百科上有对于步长串行的详细介绍。

五、归并排序 MergeSort

介绍:

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递分解数组,再并数组。

先考虑合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

再考虑递归分解,基本思路是将数组分解成leftright,如果这两个数组内部数据是有序的,那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的?可以再二分,直至分解出的小组只含有一个元素时为止,此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

排序演示:

Enjoy it! 2

源代码:(python实现)

def merge_sort(ary):
    if len(ary) <= 1 : return ary
    num = int(len(ary)/2)       #二分分解
    left = merge_sort(ary[:num])
    right = merge_sort(ary[num:])
    return merge(left,right)    #合并数组

def merge(left,right):
    '''合并操作,
    将两个有序数组left[]和right[]合并成一个大的有序数组'''
    l,r = 0,0           #left与right数组的下标指针
    result = []
    while l<len(left) and r<len(right) :
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

六、快速排序 QuickSort

介绍:
快速排序通常明显比同为Ο(n log n)的其他算法更快,因此常被采用,而且快排采用了分治法的思想,所以在很多笔试面试中能经常看到快排的影子。可见掌握快排的重要性。

步骤:

  1. 从数列中挑出一个元素作为基准数。
  2. 分区过程,将比基准数大的放到右边,小于或等于它的数都放到左边。
  3. 再对左右区间递归执行第二步,直至各区间只有一个数。

排序演示:

Enjoy it! 3

源代码:(python实现)

def quick_sort(ary):
    return qsort(ary,0,len(ary)-1)

def qsort(ary,left,right):
    #快排函数,ary为待排序数组,left为待排序的左边界,right为右边界
    if left >= right : return ary
    key = ary[left]     #取最左边的为基准数
    lp = left           #左指针
    rp = right          #右指针
    while lp < rp :
        while ary[rp] >= key and lp < rp :
            rp -= 1
        while ary[lp] <= key and lp < rp :
            lp += 1
        ary[lp],ary[rp] = ary[rp],ary[lp]
    ary[left],ary[lp] = ary[lp],ary[left]
    qsort(ary,left,lp-1)
    qsort(ary,rp+1,right)
    return ary

七、堆排序 HeapSort

介绍:

堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的,虽然实质上还是一维数组。二叉堆是一个近似完全二叉树 。

二叉堆具有以下性质:

  1. 父节点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
  2. 每个节点的左右子树都是一个二叉堆(都是最大堆或最小堆)。

步骤:

  1. 构造最大堆(Build_Max_Heap):若数组下标范围为0~n,考虑到单独一个元素是大根堆,则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始,向前依次构造大根堆,这样就能保证,构造到某个节点时,它的左右子树都已经是大根堆。
  2. 堆排序(HeapSort):由于堆是用数组模拟的。得到一个大根堆后,数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点,并做最大堆调整的递归运算。第一次将heap[0]heap[n-1]交换,再对heap[0...n-2]做最大堆调整。第二次将heap[0]heap[n-2]交换,再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]heap[1]交换。由于每次都是将最大的数并入到后面的有序区间,故操作完后整个数组就是有序的了。
  3. 最大堆调整(Max_Heapify):该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整,使得子节点永远小于父节点 。

排序演示:

Enjoy it! 4

源代码:(python实现)

def heap_sort(ary) :
    n = len(ary)
    first = int(n/2-1)       #最后一个非叶子节点
    for start in range(first,-1,-1) :     #构造大根堆
        max_heapify(ary,start,n-1)
    for end in range(n-1,0,-1):           #堆排,将大根堆转换成有序数组
        ary[end],ary[0] = ary[0],ary[end]
        max_heapify(ary,0,end-1)
    return ary


#最大堆调整:将堆的末端子节点作调整,使得子节点永远小于父节点
#start为当前需要调整最大堆的位置,end为调整边界
def max_heapify(ary,start,end):
    root = start
    while True :
        child = root*2 +1               #调整节点的子节点
        if child > end : break
        if child+1 <= end and ary[child] < ary[child+1] :
            child = child+1             #取较大的子节点
        if ary[root] < ary[child] :     #较大的子节点成为父节点
            ary[root],ary[child] = ary[child],ary[root]     #交换
            root = child
        else :
            break

总结

下面为七种经典排序算法指标对比情况:

Enjoy it! 5

参考资料

注:本文所有源代码已共享到GitHub

-EOF-

分享链接:http://xn--qrqa955a.xn--fiqs8s/?p=1512
除非另有声明,本网站采用知识共享“署名-非商业性使用-相同方式共享 (by-nc-sa) 3.0 中国大陆”许可协议授权。

[转]CI上传不了rar文件处理方法

用CI自身的upload上传类(@property CI_Upload $upload)做文件上传时,
发现rar格式的压缩包文件无法上传,
打印出来的error_msg是

“The filetype you are attempting to upload is not allowed.”

说文件类型不允许,查看初始化时的配置参数allowed_types,是允许有rar格式的文件上传的。

把处理后的$this->upload句柄打印出来会发现,
rar的mimes是application/octet-stream,而mimes的配置列表里没有rar的参数项,所以解决办法是:
找到项目的config目录下的mimes.php配置文件,加上相应的参数项

‘rar’   =>  array(‘application/octet-stream’,’application/x-rar-compressed’),

就行。

这样的话,上传时就可以检测通过了。

原文地址:http://www.pangyiguang.com/blog/91.html

分享链接:http://xn--qrqa955a.xn--fiqs8s/?p=1504
除非另有声明,本网站采用知识共享“署名-非商业性使用-相同方式共享 (by-nc-sa) 3.0 中国大陆”许可协议授权。

[转]如何把老旧笔记本变成一部Chromebook

[摘要]想尝试Chrome系统的朋友,可以利用安装CloudReady来实现。

Enjoy it! 1

腾讯数码讯(Eskimo)如果你对于谷歌的Chrome OS十分好奇,但暂时还不想花钱购买一部Chromebook,那你可能会对CloudReady这款软件感兴趣。有了它,你就可以在一部普通的笔记本上面体验谷歌这款轻量级的操作系统。如果你手头恰好有一部闲置不用的笔记本,本文的指南可以让你把它变成一部Chromebook。

准备工作

CloudReady是一款完整的操作系统,它在安装时会擦除计算机原本存储的所有内容。如果你不打算将其安装在U盘,那最好还是使用一部闲置不用的计算机。CloudReady目前并不支持双系统启动。

准备好安装设备和U盘之后,你就可以前往CloudReady的网站,根据自己的设备和系统类型下载安装包了。接下来,你需要从Chrome网上应用商店下载谷歌的Chrome恢复工具,然后从相同的页面将其运行,以确保它被正确安装。然后你就可以正式开始CloudReady的安装了。

创建安装程序

点击Chrome恢复应用窗口右上角的齿轮图标进入设置菜单,选择“使用本地镜像”,然后找到之前下载的CloudReady安装文件。随后,应用会询问你是否准备好要清除U盘中的内容,点击确认之后,它便会开始格式化U盘,然后在其中创建安装程序。

创建完成之后,你需要重启计算机,然后从BIOS/UEFI中选择从U盘启动。需要注意的是,较新的机器可能会带有Secure Boot功能,而它是不支持从U盘启动的,因此你需要暂时将该功能禁用。如果你的机器不允许用户取消Secure Boot,那它就无法使用CloudReady。

Enjoy it! 2

选择从U盘启动之后,你可以直接从中使用CloudReady,或者是选择将其安装到计算机硬盘。正如上文所提到的,后者会清除计算机当中的所有内容,因此你在选择时需要格外注意。

Enjoy it! 3

将系统安装到本地十分简单,你只要遵循安装向导的指示即可。安装完成之后,你的笔记本基本上就变成了一部Chromebook。

注意事项

CloudReady大体上是一款非常容易安装的操作系统,但和其他系统一样,你在安装过程当中也可能会碰到各种各样的问题。

在硬件支持方面,只要你的计算机不是10年前的机型,那在兼容性方面应该没什么问题。不过你也可以在CloudReady官网当中找到具体的支持和清单。

在决定将CloudReady安装到计算机之前,你可以先通过U盘尝试一下,但这种运行方式可能无法提供和本地安装相同的体验(运行速度较慢)。

最后,在安装CloudReady之前,你最好先进行一次彻底的数据备份,毕竟操作系统的安装总是有可能会遇到不可预测的问题,凡事最好做到有备无患。

来源:DigitalTrends

分享链接:http://xn--qrqa955a.xn--fiqs8s/?p=1498
除非另有声明,本网站采用知识共享“署名-非商业性使用-相同方式共享 (by-nc-sa) 3.0 中国大陆”许可协议授权。