算法基础

算法定义

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

时间复杂度

时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

时间复杂度

刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。n一般就是执行的次数，f（n）就是问题的规模

常见的时间复杂度

按数量级递增排列，常见的时间复杂度有：
常数阶O(1), 对数阶O(log2n), 线性阶O(n), 线性对数阶O(nlog2n), 平方阶O(n^2)，立方阶O(n^3),…， k次方阶O(n^k), 指数阶O(2^n) 。

常用排序

名称	复杂度	说明	备注
冒泡排序Bubble Sort	O(N*N)	将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮
插入排序Insertion sort	O(N*N)	逐一取出元素，在已经排序的元素序列中从后向前扫描，放到适当的位置	起初，已经排序的元素序列为空
选择排序	O(N*N)	首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此递归。
快速排序Quick Sort	O(n *log2(n))	先选择中间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（递归）。
堆排序 HeapSort	O(n *log2(n))	利用堆（heaps）这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于（或者大于）它的父节点。	近似完全二叉树
箱排序 Bin Sort	O(n)	设置若干个箱子，把关键字等于 k 的记录全都装入到第k 个箱子里 ( 分配 ) ，然后按序号依次将各非空的箱子首尾连接起来 ( 收集 ) 。	分配排序的一种：通过” 分配 ” 和 ” 收集 ” 过程来实现排序。

冒泡排序

冒泡排序详情
python代码

def bubble(array):
    count=0
    length=len(array)

    exchange=length-1 #从0索引的
    while exchange!=0:
        length=exchange
        exchange=0
        for i in range(length):
            if array[i]>array[i+1]:
                temp=array[i+1]
                array[i+1]=array[i]
                array[i]=temp
                exchange=i+1  #exchange索引后的序列为顺序列表
        count+=1
        # print '第%d轮'%count,

    return array

选择排序

思想

选择排序的思想非常直接，不是要排序么？那好，我就从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。可以很清楚的发现，选择排序是固定位置，找元素。相比于插入排序的固定元素找位置，是两种思维方式。不过条条大路通罗马，两者的目的是一样的。

代码

def select_sort(array):
    length=len(array)
    for i in range(0,length):
        index=i   #记录最最小值的索引
        for j in range(i+1,length):
            if array[index]>array[j]:
                index=j
        if (index!=i):
            temp=array[index]
            array[index]=array[i]
            array[i]=temp
    return array

插入排序

给定一个记录序列(r1,r2,…,rn)，其相应的关键码分别是（k1,k2,…kn），排序是将这些记录排列成顺序为(r s1,r s2,… r sn)的一个序列，使得相应的关键码满足ks1<=ks2<=..<=ksn。

直接插入排序

思想

直接插入排序是插入排序中最简单的排序方法，类似于玩纸牌的时候整理手中纸牌的过程，其基本思想是：以此将待排序序列中的每一个记录插入到一个已经排好序的序列中，直到全部记录都排好序。（在排序问题中，通常讲数据元素称为记录）

排序过程

将整个待排序的记录序列划分为有序区和无序区，初始时有序区为待排序记录系列中的第一个记录，无序区包括所有剩余待排序的记录
将无序区的第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序区增加一个记录。
重复执行（2），直到无序区中没有记录为止

将第一个记录看成是初始有序区，然后从第二个记录起依次插入到这个有序区中，直到将第n个记录插入完毕

for(i=2;i<=n;i++){
    插入第i个记录
}

一般情况下，在i-1个记录的有序区r[1]~r[i-1]中插入一个记录r[i]时，首先要查找r[i]的正确插入位置，最简单的，可以采用顺序查找，为了在寻找插入位置的过程中避免数组下标越界，在r[0]处设置“哨兵”，在自i-1起前往查找的过程中，同时后移记录

r[0]=r[i]
for(j=i-1;r[0]<r[j];j--){
    r[j+1]=r[j]
}

退出循环，说明找到了插入的位置，因为r[j]刚刚比较完毕，所以r[j+1]为正确的插入位置，将待差记录插入到有序表中：

r[j+1]=r[0]

代码实现

def insert_sort_1(array):
    # 设置哨兵位
    array.insert(0, 0)
    length = len(array)
    # 有序表的插入
    for i in range(2, length):
        array[0] = array[i]
        for j in range(i - 1, 0, -1):
            # 元素往后移
            if array[0] < array[j]:
                array[j + 1] = array[j]
            else:
                array[j + 1] = array[0]
                break
            #判断这个数是不是最小的
            if array[0]<array[1]:
                array[1]=array[1]

    return array[1:]

折半插入排序

分析直接插入排序算法，由于寻找插入位置的操作是在有序区进行的，因此可以通过折半查找来实现，由此进行的插入排序称为折半插入排序

代码实现

def insert_sort_2(array):
    "折半插入排序"
    array.insert(0,0)
    length=len(array)
    for i in range(2,length):
        array[0]=array[i]
        #在有序表中折半查找
        low=1
        high=i-1
        while low<=high:
            mid=(high+low)/2
            if array[0]>array[mid]:low=mid+1
            else:high=mid-1
        #找到了位置
        #移动记录
        for j in range(i-1,low-1,-1):
            array[j+1]=array[j]
        print 'array=%s,mid=%s,low=%s,high=%s'%(array[0],mid,low,high),
        """
        或者：
        for j in range(i,low,-1):
            array[j]=array[j-1]
        """
        array[low]=array[0]
        print array[1:]
    return array[1:]

希尔排序

希尔排序是对直接插入排序的一种改进，改进的着眼点是：
1. 若待排序记录按照关键码记录基本有序，直接插入排序的效率很高
2. 由于直接插入排序算法简单，则在待排序记录个数较少时，效率也很高

基本思想：

先将整个待排序记录序列分隔成若干个子序列，在子序列内分别进行直接插入排序，待整个序列基本有序的时候，在对全体记录进行一次直接插入排序

代码：

快速排序

快速排序详情
python代码

#coding:utf-8

"快速排序"
def quick_sort(array,first,end):
    if(first<end):
        "递归调用"
        "[23,13,35,6,19,50,28]----->[19, 13, 6, 23, 35, 50, 28]一次划分后的结果"
        pivot=partions(array,first,end)  #接受返回的轴值的索引
        #递归的对右侧的子序列进行快速排序
        quick_sort(array,pivot+1,end)
        #递归的对左侧的子序列进行快速排序
        quick_sort(array,first,pivot-1)

    return array

def partions(array,first,end):
    "一次划分"
    while first<end:
        #进行右侧扫描
        while first<end and array[first]<array[end]:end-=1
        #在右侧找到了一个比轴值小的数，交换这两个数，然后这个数（包括这个数）
        # 前面的就排好了，最后让first加1
        if(array[first]>array[end]):
            temp=array[first]
            array[first]=array[end]
            array[end]=temp
            first+=1

        #进行左侧扫描
        while first<end and array[first]<array[end]:first+=1
        #在左侧找到了一个比轴值的大的数,将这个数和轴值交换,然后这个数后面的数就排好了，让end减1
        if array[first]>array[end]:
            temp=array[first]
            array[first]=array[end]
            array[end]=temp
            end-=1

    #return array
    "返回轴值的索引"
    return first

def main():
    array=[23,13,35,6,19,50,28]
    pass
    print partions(array,0,6) #[19, 13, 6, 23, 35, 50, 28]一次划分后的结果

    print quick_sort(array,0,6) #[6, 13, 19, 23, 28, 35, 50]


if __name__ == '__main__':
    main()