冒泡排序和快速排序

冒泡排序

伪代码

//对数组A[0..n-1]排序
//input: A[0..n-1]
//output: 非降序排序的数组A[0..n-1]
for i<-0 to n-2 do
    for j<-0 to n-2-i do
        if A[j+1]<A[j] swap A[j] and A[j+1]

缺点

由于多次的逐个交换导致其速度慢。
O(n^2)

快速排序

优化后的冒泡排序。

选择排序和堆排序

选择排序

伪代码

//对数组A[0..n-1]排序
//input: A[0..n-1]
//output: 升序排序的数组A[0..n-1]
for i<-0 to n-2 do
    min<-i
    for j<-i+1 to n-1 do
        if A[j]<A[min] min<-j
    swap A[j] and A[min]

缺点

多次的比较导致较慢。

时间复杂度

O(n^2)

堆排序

优化后的选择排序
O(n*log(n))

插数排序和希尔排序

插数排序

希尔排序

优化后的插数排序

顺序查找和蛮力字符匹配

顺序查找

分治法

伪代码

//使用查找键座位限位器
//input: 一个n个元素的数组A和一个查找键K
//output: 第一个值==K元素的位置，如果找不到这样的元素，return-1
A[n]<-K
i<-0
while A[i]!=K do
    i<-i+1
if i<n return i
else return -1

蛮力字符匹配

一位位匹配；字符与数组对应长度字符匹配，从0~max。

伪代码

//input: 一个n个字符的数组T[0..n-1],代表一段文本
         一个m个字符的数组P[0..m-1],代表一个模式
//output: 查找成功，返回文本第一个匹配子串中第一个字符位置，否则返回-1
fro i<-0 to n-m do
    j<-0
    while j<m and P[j]=T[i+j] do
        j<-j+1
        if j=m return i
return -1

改进思路

当遇见重复元素(例:0000001中的000000)可以直接跳过数组中该部分。

最近对和凸包问题的蛮力算法

最近对问题

最近点对

一堆二维点中，距离最近的两点组成最近点对。

伪代码

//求平面中距离最近的两点
//input: 一个n(n>=2)个点的列表p，p1=(x1,y1),...,pn(xn,yn)
//output: 两个最近点的距离
d<-∞
for i<-1 to n-1 do
    for j<-i+1 to n do
        d<-min(d,sqrt((xi-xj)^2+(yi-yj)^2))
return d;

时间复杂度

O(n^2)

凸包问题

凸包

最小的覆盖n个点的凸多边形。由直线所围成的图形一定为凸包。

凸

任意两点的连线在图形内部

问题

给予n个点将这n个点的凸包画出。

解决方案

遍历直线，点在一边即为组成凸包的直线
直线ax+by=c，将其余点带入，结果都<=或>=c即可。
穷举n(n-1)/2个点。O(n^3)

蛮力法解题步骤

1. 划定解空间
2. 遍历解空间
3. 找出可行解

   穷举查找

   NP困难问题

   例：旅行商问题、汉罗塔问题、背包问题。
   常规算法：暴力穷举法、贪心算法、分支定界法、动态规划法
   启发式算法：遗传算法、蚁群算法、粒子群算法、模拟返火法

   旅行商问题

   问题

   求一个图的最短哈密顿回路(图的每个顶端都只穿越一次)。

   解决

   深度优先搜索

   背包问题

   问题

   给定n个重量为w1…wn价值为v1…vn的物品和一个称重为W的背包，求这些物品中一个最有价值的子集。

   分配问题

   问题

   有n个任务需要分配给n个人执行，一个任务对应一个人。对于每一对i，j=1…n来说，将第j个任务分配给第i个人的成本是C【i，j】。求总成本最小方案。

   深度优先查找

广度优先查找

BFS的升级版：Dijkstra，再次升级：A*