数据结构基础

发表于 | 更新于 | 分类于

总结一下数据结构的知识，以便之后忘记了可以翻阅，哈哈，就像是做了一次备份哇

基本概念与术语

数据

是对客观事物的符号表示，很笼统的概念，范围很大

数据对象

是性质相同的数据元素的集合，是数据的子集

数据元素

是组成数据的基本单位

数据项

一个数据元素可以由若干个数据项组成

数据项是数据的不可分割的最小单位

数据结构

是相互之间存在的一种或多种特定关系的数据元素的集合

逻辑结构

是指数据对象中数据元素之间的相互关系

  • 集合结构
  • 线性结构
  • 树形结构
  • 图形结构或图状结构

物理结构

是指数据的逻辑结构在计算机中存储形式

  • 顺序存储结构
  • 链式存储结构

算法

解决问题的方法

特性

  • 有穷性
  • 确定性
  • 可行性
  • 输入
  • 输出

时间复杂度

记作 T(n) = O(f(n))

表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，也称作渐进时间复杂度

小贴士：

这里我们学到优化程序，不单单是降低时间复杂度，还可以从空间复杂度来解决，如果不考虑容量，可以用空间换效率

线性表

顺序存储结构

1
2
3
4
5
6
7
#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
  ElemType data[MAXSIZE];
  int length;
}SqList;

链式存储结构

1
2
3
4
5
6
7
8
9
10
typedef int ElemType;
typedef struct Node
{
  ElemType data;
  struct Node *next;
}Node,*LinkList;

//等同typedef struct Node *LinkList;
//p = (LinkList) malloc (sizeof (Node))
//有系统生成一个Node型的结点，同时将该结点的起始位置赋给指针变量p

循环链表

表中最后的一个结点的指针域指向头结点，整个链表形成一个环

和线性链表基本一致，差别在于判断循环条件不是p或者p->next是否为空，而是它们是否等于头指针

双向链表

就是不仅仅有指向后继的指针，还有增加了指向前驱的指针

1
2
3
4
5
6
7
typedef int ElemType;
typedef struct DuNode
{
  ElemType data;
  struct DuNode *prior;
  struct DuNode *next;
}DuNode,*DuLinkList;

栈和队列

栈

后进先出 LIFO

1
2
3
4
5
6
typedef struct
{
  SElemType *base;
  SElemType *top;
  int stacksize;
}SqStack;

栈可以在程序设计语言中实现递归（调用自己的行为叫做递归）

队列

先进先出 FIFO

1
2
3
4
5
6
7
8
9
10
11
typedef struct QNode
{
  QElemType data;
  struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
  QueuePtr front;  //队头指针
  QueuePtr rear;   //队尾指针
}LinkQueue;

循环队列

特点

在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

串

1
2
3
4
5
typedef struct
{
    char *ch;
    int length;
}HString;

广义表

术语

长度

第一层（括号）的数量

深度

层数（括号数）

速学路径

http://www.zybang.com/question/17d8254f4028ac9695f79081f32542f4.html

树

基本术语

结点

树上的一个元素

度

结点拥有的子树数

叶子

度为0的结点

孩子

结点的子树

双亲

子树的派生数称为双亲

兄弟

同一个双亲的孩子互称兄弟

深度

树中结点的最大层次称为树的深度

森林

几棵互不相交的树的集合

二叉树

每个结点最多两棵子树的树

性质

  • 在二叉树的第 i 层上最多有2^i-1^个结点
  • 深度为 k 的二叉树最多有2^k^-1个结点
  • 任何一棵二叉树，如果叶子结点数为n~0~，度为2的结点数为n~2~，则n~0~ = n~2~+1
  • 具有n个结点的完全二叉树的深度为[log~2~n]+1

存储结构

顺序存储结构

根据完全二叉树的顺序，依次排列，形成顺序表

链式存储结构
1
2
3
4
5
typedef struct BiTNode
{
  TElemType data;
  struct BiTNode *lchild,*rchuld;
}BiTNode,*BiTree;

遍历二叉树

仅仅是根节点的输出顺序的前后

  • 先序遍历
  • 中序遍历
  • 后序遍历

线索二叉树

相比二叉树，他增加了前驱和后继的元素，为了节约空间，数据位还是采用之前的左右子树，但是用tag来表示是两边的数据位是左孩子还是前驱，右孩子还是后继

左数据位 标识 数据 标识 右数据位
Lchild LTag data RTag Rchild

如果tag为0，表示是孩子的数据，如果为1，表示是前驱或者后继

线索化

一般用中序遍历二叉树，使其变成线索二叉树

速学路径

http://blog.csdn.net/jiajiayouba/article/details/9224403

树和森林

树的存储结构

双亲表示法
1
2
3
4
5
6
7
8
9
10
11
#define SIZE 100
typedef struct PTNode
{
  PElemType data;
  int parent;  //双亲位置域
}PTNode;
typedef struct
{
  PTNode nodes[SIZE];
  int r,n;   //根的位置和结点数
}PTree;
孩子表示法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct CTNode   //孩子结点
{
  int child;
  struct CTNode *next;
}*ChildPtr;
typedef struct
{
  TElemType data;
  ChildPtr firstchild;   //孩子链表头指针
}CTBox;
typedef struct
{
  CTBOX nodes[SIZE];
  int r,n;   //根的位置和结点数
}CTree;
兄弟表示法
1
2
3
4
5
typedef struct CSNode
{
  ElemType data;
  struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

树与二叉树的转换

树和森林的遍历

树的遍历

把树转化成二叉树

  • 先根遍历（类似于二叉树的先序遍历）
  • 后根遍历（类似于二叉树的中序遍历）
森林的遍历

把森林转化成二叉树

  • 先序遍历森林（类似于二叉树的先序遍历）
  • 中序遍历森林（类似于二叉树的中序遍历）

赫夫曼树

转变二叉树来实现用较小的代价来访问到概率大的元素，又叫最优二叉树

生成最优树的方法

现在有一堆概率数：A:5 , B:15 , C:40 , D:30 , E:10

如上图所示，选两个目前最小的数生成N~1~，保证右子树的权值大于左子树，然后这样循环，即可生成

上图二叉树的带权路径长度(叶子结点的路径之和)
$$
40x1+30x2+15x3+10x4+5x4=205
$$

赫夫曼编码

如下图所示

主要思想还是没变，把概率最大的字母用最少的二进制字符来表示，而且每个二进制字符组代表的字母不冲突。

速学路径

http://www.jianshu.com/p/95fba425be44

图

术语

G(V,E)

G表示一个图，V是图的顶点集合，E是图的边集合

无向图

顶点之间的边没有方向

有向图

顶点之间的边有方向，这种边称为有向边，也称为弧

入度

有向边指向顶点V的数量称为入度

出度

有向边离开顶点V的数量称为出度

简单图

不存在顶点到自身的边，并且没有重复的边的图是简单图

网

有权值的图叫做网

连通图

图上任意两个顶点都连通，则为连通图

图的存储结构

邻接矩阵

1
2
3
4
5
6
7
8
9
typedef char VertexType;
typedef int EdgeType;
#define MAXSIZE 100
typedef struct
{
  VertexType vexs[MAXSIZE];         //顶点数组
  EdgeType arc[MAXSIZE][MAXSIZE];   //二维数组，边表
  int numVertexes,numEdges;         //顶点数和边数
}MGraph;

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MAX_VERTEX_NUM 20
typedef struct ArcNode
{
  int adjvex;   //储存该顶点的下标
  struct ArcNode *nextarc;  //指向下一个邻接点的指针
}ArcNode;
typedef struct VNode
{
  VertexType data;   //顶点信息
  ArcNode *firstarc;  //指向第一个邻接点
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
  AdjList vertices;
  int vexnum,arcnum;  //顶点数和弧数
}ALGraph;

十字链表

邻接表是以出度为出发点，逆邻接表是以入度为出发点，那么十字链表就是结合它们两者

顶点结点
指向该顶点的入边表的第一个结点 数据 指向该顶点的出边表的第一个结点
firstin data firstout
弧结点
弧起点的下标 弧终点的下标 指向终点相同的下一条弧 指向起点相同的下一条弧 数据
tailvex headvex hlink tlink data

邻接多重表

是无向图的另一种链式存储结构

图的遍历

深度优先遍历

一直递归地遍历第一个顶点的第一个邻接点，直到访问的顶点没有邻接点后，再对第一个顶点的第二个邻接点进行递归遍历，如此循环

广度优先遍历

以顶点为起始点，由近至远，依次访问和顶点路径想通且路径长度分别为1，2……的顶点

速学路径

http://blog.csdn.net/dreamzuora/article/details/51137132

最小生成树

把各个顶点连接起来的最小代价的树

普里姆（Prim）算法

新建一个集合，放入一个顶点，然后选出和这个顶点连通的最短路径的那个顶点，也放进这个集合，然后选出和这两个顶点连通的最短路径的那个顶点，然后再把它放进集合，直到所有的顶点都在集合里了，那最小生成树也出来了

克鲁斯卡尔（Kruskal）算法

将图中边按其权值由小到大的次序顺序选取，然后凑出来

速学路径

http://blog.csdn.net/weinierbian/article/details/8059129/

拓扑排序

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

(1) 选择一个入度为0的顶点并输出之；

(2) 从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

AOV网

在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网

关键路径

从源点到汇点的路径长度(各路径上持续时间之和)最长的路径叫关键路径

AOE网

用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE网

最短路径

迪杰斯特拉（Dijkstra）算法

按路径长度递增的次序产生最短路径的算法

速学路径

http://blog.csdn.net/qq_34845121/article/details/62056089

弗洛伊德（Floyd）算法

速学链接

http://blog.csdn.net/bjtu_dubing/article/details/50333027

查找

术语

关键字

是数据元素中某个数据项的值，用它可以标识一个数据元素

顺序查找

从第一个或者最后一个记录开始，逐个与给定的值进行匹配

折半查找

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

时间复杂度为O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// while循环
int binary_search(const int arr[], int start, int end, int khey) {
	int mid;
	while (start <= end) {
		mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
		if (arr[mid] < khey)
			start = mid + 1;
		else if (arr[mid] > khey)
			end = mid - 1;
		else
			return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
	}
	return -1;
}

// 递归版本
int binary_search(const int arr[], int start, int end, int khey) {
	if (start > end)
		return -1;

	int mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
	if (arr[mid] > khey)
		return binary_search(arr, start, mid - 1, khey);
	if (arr[mid] < khey)
		return binary_search(arr, mid + 1, end, khey);
	return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
}

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class binarySearch {
    public static <T extends Comparable<T>> int binarySearch(T[] x, T key) {
        return binarySearch(x, 0, x.length- 1, key);
    }

    // 使用循环实现的二分查找
    public static <T> int binarySearch(T[] x, T key, Comparator<T> comp) {
        int low = 0;
        int high = x.length - 1;
        while (low <= high) {
            int mid = (low + high) >>> 1; //无符号向右移一位，左侧补0
//            int mid = (high + low)/2;
            int cmp = comp.compare(x[mid], key);
            if (cmp < 0) {
                low= mid + 1;
            }
            else if (cmp > 0) {
                high= mid - 1;
            }
            else {
                return mid;
            }
        }
        return -1;
    }

    // 使用递归实现的二分查找
    private static<T extends Comparable<T>> int binarySearch(T[] x, int low, int high, T key) {
        if(low <= high) {
            int mid = low + ((high -low) >> 1); //向右移一位，就是除以2
//            int mid = (high + low)/2;  //直接平均可能會溢位，所以用上面这种算法
            if(key.compareTo(x[mid])== 0) {
                return mid;
            }
            else if(key.compareTo(x[mid])< 0) {
                return binarySearch(x,low, mid - 1, key);
            }
            else {
                return binarySearch(x,mid + 1, high, key);
            }
        }
        return -1;
    }

    public static void main(String[] args){
        Integer[] it = new Integer[5];
        for (int f = 0;f<it.length;f++){
            it[f] = f+2;
        }

        System.out.println(binarySearch(it, 3, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        }));
    }
}

binary search tree

中文翻译可为(排序二叉树,二叉搜索树,二叉查找树)

左子树上的所有结点的值均小于它的根结点的值

右子树上的所有结点的值均大于它的根结构的值

它的左右子树也分别为二叉排序树

把无序序列转成二叉排序树之后，用中序遍历的方法可以输出有序的顺序序列

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Node 二叉树上的节点
 * @author wait
 *
 */
public class Node {
    /**
     * 节点的数据，这里我们用一个int表示
     */
    public int data;
    /**
     * 节点的左孩子
     */
    public Node left;
    /**
     * 节点的右孩子
     */
    public Node right;
    /**
     * 构造函数，data初始化节点的值
     * @param data
     */
    public Node(int data){
        this.data=http://blog.csdn.net/lwxdjk/article/details/data;
    }
    /**
     * 默认构造函数，data=0
     */
    public Node(){
        this(0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/**
 * BTree二叉排序树类
 * 
 * @author wait
 * 
 */
public class BTree {
    /**
     * 树的根节点
     */
    public Node root;
    /**
     * 记录树的节点个数
     */
    public int size;

    /**
     * 默认构造函数，树的根节点为null
     */
    public BTree() {
        root = null;
        size = 0;
    }

    /**
     * 插入一个新的节点node
     * 
     * @param node
     */
    public void insert(Node node) {
        if (root == null) {
            root = node;
            size++;
            return;
        }
        Node current = root;
        while (true) {
            if (node.data <= current.data) {
                // 如果插入节点的值小于当前节点的值，说明应该插入到当前节点左子树，而此时如果左子树为空，就直接设置当前节点的左子树为插入节点。
                if (current.left == null) {
                    current.left = node;
                    size++;
                    return;
                }
                current = current.left;
            } else {
                // 如果插入节点的值大于当前节点的值，说明应该插入到当前节点右子树，而此时如果右子树为空，就直接设置当前节点的右子树为插入节点。
                if (current.right == null) {
                    current.right = node;
                    size++;
                    return;
                }
                current = current.right;
            }
        }
    }

    /**
     * 插入一个值为data的节点
     * 
     * @param data
     */
    public void insert(int data) {
        insert(new Node(data));
    }

    /**
     * 根据int数组里面的值建立一个二叉排序树
     * 
     * @param datas
     */
    public void bulidTree(int[] datas) {
        for (int i = 0, len = datas.length; i < len; i++) {
            insert(datas[i]);
        }
    }
    
     /**
     * 中序遍历，递归方法实现
     * @param node 当前访问的节点
     * @param list 存储节点值的容器
     */
    private void inOrderRe(Node node,List<Integer> list){

        if(list==null){
            list=new ArrayList<>();
        }
        if(node==null){
            return;
        }
        if(node.left!=null){
            inOrderRe(node.left,list);
        }
        list.add(node.data);
        if(node.right!=null){
            inOrderRe(node.right,list);
        }
    }
  /**
     * 中序遍历二叉排序树  非递归的方法，深度优先和栈思想
     * @return
     */
    public int[] inOrder() {
        int[] res = new int[size];
        int i = 0;
        //使用stack存储遍历到的节点
        Stack<Node> stack = new Stack<Node>();
        Node node = root;
        while (node != null) {
            //一直往下遍历，知道到左孩子节点为空
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            //左孩子节点为空之后，往后找，找到上一个节点.如果找到的上一个节点的右孩子节点为空，那么继续往上找，直到找到一个右孩子节点不为空的
            while (!stack.isEmpty() && stack.peek().right == null) {
                node = stack.pop();
                res[i++] = node.data;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                res[i++] = node.data;
                //找到了一个右孩子节点不为空的节点，就去遍历他的右孩子节点
                if (node != null) {
                    node = node.right;
                }
            }else{
                node=null;
            }

        }
        return res;
    }
}

速学路径

https://www.nowcoder.com/questionTerminal/a738e13ce2aa4daeac9ef3b4238e4b2e?pos=7&mutiTagIds=583&orderByHotValue=1

http://www.itdadao.com/articles/c15a205949p0.html

数据结构二叉树 JAVA版

B树(B-树,B-tree)

B树是多路平衡查找树，B树每个结点可以有n个元素和n+1个孩子，减少树的高度，所以可以降低内存读取外存的次数；( 对二叉查找树的改进。它的设计思想是，将相关数据尽量集中在一起，以便一次读取多个数据，减少硬盘操作次数）一般用于数据库系统中

性质

  • 根结点的儿子数为[2, M]
  • 除根结点以外的非叶子节点的儿子数为[M/2, M]
  • 每个结点存放至少M/2-1（取上整）和至多M-1个关键字
  • 每个节点的关键字比它的子节点个数少 1 (叶结点除外)
  • 所有的叶子结点都在同一个层级

速学路径

http://www.jianshu.com/p/ed76dbc0536d

B+树

B+树是B树的变种树，有n棵子树的节点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子节点。是为文件系统而生的。

为什么数据库索引采用B+树

因为从磁盘读到内存需要花很多时间，所以普通的搜索树的深度很深，会导致IO时间很长，所以用深度低的多路查找树。那为什么真实数据不放在内层节点呢，是要让磁盘块能放更多的数据项，同时数据项（索引字段）要小一点，这样可以减低树的高度。

区别

重点：B树必须用中序遍历的方法按序扫库， 而B+树直接从叶子结点挨个扫一遍就完了

B 树 B+ 树
关键字 关键字分布在整颗树中，只出现一次 所有关键字都出现在叶节点的链表中，且有序
搜索命中 可能在树中任意节点命中，搜索结束 只可能在叶节点中命中，查询路径稳定
非叶节点 非叶节点包含关键字，也包含数据 非叶节点相当于索引帮助搜索到叶节点，叶节点相当于存储关键字数据的数据层
叶节点 增加了链表指针，相当于存储关键字数据的数据层

索引

InnoDB和MyISAM的索引区别

MyISAM索引文件和数据文件是分离的，索引文件仅保存数据的地址

InnoDB中，数据文件本身就是按B+Tree组织的一个索引结构，它的叶节点就保存了完整的数据

优缺点

优点
  1. 大大加快数据的检索速度;
  2. 创建唯一性索引，保证数据库表中每一行数据的唯一性;
  3. 加速表和表之间的连接;
  4. 在使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间。
缺点
  1. 索引需要占物理空间。
  2. 当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，降低了数据的维护速度。

索引优化

  • 如果是联合索引，则把=放在最前面，范围<>between放在最后，因为从左往右匹配
  • 有了’AB’索引，就不用’A’索引了
  • 索引列匹配的时候，索引不要参与计算
  • 索引项尽量小
  • 数据量小的表不要建索引
  • 索引不是越多越好，因为数据的变更（增删改）都需要维护索引，而且更多的索引意味着也需要更多的空间
  • 索引值太单一，比如性别，就不要建索引
  • 更新非常频繁的数据也不要建索引

以下情况没有索引效果

  • Like “%xxx”，Like的参数不能以通配符开头
  • not in ， !=
  • 对列进行函数运算的情况（如 where md5(password) = “xxxx”）
  • WHERE index=1 OR A=10
  • int类型的数据 不好做索引

速学路径：

http://www.cnblogs.com/zlcxbb/p/5757245.html

平衡二叉树(AVL树)

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

平衡因子

将二叉树上结点的左子树深度减去右子树深度的值，也只能是-1，0，1

速学路径

http://www.jianshu.com/p/db5529e91f4b

红黑树

特点

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点必须是黑色
  3. 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
  4. 对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。
  5. 每个空叶子节点必须是黑色的；

速学路径

http://www.jianshu.com/p/f4639d0cc887

http://www.importnew.com/21818.html

http://www.importnew.com/21822.html

http://www.jianshu.com/p/23b84ba9a498

哈希表

线性探测法

http://blog.csdn.net/shangruo/article/details/8491733

二次探测法

http://blog.csdn.net/xyzbaihaiping/article/details/51607770

排序

直接插入排序

每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void InsertSort(SqList *L)
{
  int i,j;
  for(i=2;i<=L->length;i++){
    if(L->r[i] < L->r[i-1]){    //如果前者大于后者
      L->r[0]=L->r[i];          //把后者保存在暂存区r[0]里
      for(j=i-1;L->r[j] > L->r[0];j--){
        L->r[j+1]=L->r[j];      //后者放入前者的值，如果前者的前者比暂存区的大，则再次交换
      }
      L->r[j+1]=L->r[0];        //再把暂存区的值拿出来
    }
  }
}

void insertsort(int arr[]){                
        for(int i = 1;i < arr.length; i ++){
            if(arr[i] < arr[i-1]){
//注意[0,i-1]都是有序的。如果待插入元素比arr[i-1]还大则无需再与[i-1]前面的元素进行比较了，反之则进入if语句
                int temp = arr[i];
                int j;
                for(j = i-1; j >= 0 && arr[j] > temp; j --){                
                        arr[j+1] = arr[j];//把比temp大或相等的元素全部往后移动一个位置            
                }
                arr[j+1] = temp;//把待排序的元素temp插入腾出位置的(j+1)
            }            
        }
        
}

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void insertSort(int[] list)
    {
    int size = list.length;
    int temp = 0 ;
    int j =  0;
    
    for(int i = 0 ; i < size ; i++)
    {
        temp = list[i];
        //假如temp比前面的值小，则将前面的值后移
        for(j = i ; j > 0 && temp < list[j-1] ; j --)
        {
        	list[j] = list[j-1];
        }
        list[j] = temp;
    }
}

时间复杂度为O[n^2^]

希尔排序

有间隔的直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void ShellSort(SQLite *L)
{
  int i,j;
  int increment = L->length;
  do{
    increment = increment/3+1;        //先确定间距
    for(i = increment+1;i<=L->length;i++){
      if(L->r[i] < L->r[i-increment]){        //比较相隔increment的两值大小
        L->r[0]=L->r[i];
        for(j=i-increment;j>0&&L->r[0]<L->r[j];j-=increment){   //和直接插入法一个意思
          L->r[j+increment]=L->r[j];
        }
        L->r[j+increment]=L->r[0];
      }
    }
  }
  while(increment>1)
}

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void shellSort(int[] data)
{
    int j;
    int temp;
    //每次将步长缩短为原来的一半
    for (int increment = data.length / 2; increment > 0; increment /= 2)
    {
        for (int i = increment; i < data.length; i++)
        {
            temp = data[i];
            for (j = i; j >= increment; j -= increment)
            {
                if(temp < data[j - increment])//如想从小到大排只需修改这里
                {
                    data[j] = data[j - increment];
                }
                else
                {
                    break;
                }
            }
            data[j] = temp;
        }
    }
}

当n无穷大的时候，可以减少到n(log~2~n)^2^

快速排序

选择一个基准，将比起大的数放在一边，小的数放到另一边。对这个数的两边再递归上述方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void sort(int *a, int left, int right)
{
    if(left >= right)  /*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
      
    while(i < j)    /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 
        {
            j--;/*向前寻找*/
        }
          
        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/
          
        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }
          
        a[j] = a[i];
    }
      
    a[i] = key;             /*当在当组内找完一遍以后就把中间数key回归*/
    sort(a, left, i - 1);   /*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);  /*用同样的方式对分出来的右边的小组进行同上的做法*/
                            /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void sort(int[] list, int start, int end)
{
    if(start >= end)
    {
        return ;
    }
    int i = start;
    int j = end;
    int key = list[start]; //默认首位是key
    while(i < j)
    {
        while(i < j && key <= list[j])
        {
            j--;
        }
        list[i] = list[j];
        while(i < j && key >= list[i])
        {
            i++;
        }
        list[j] = list[i];
    }
    list[i] = key;
    sort(list, start, i - 1);
    sort(list, i + 1, end);
}

最好情况是O(nlogn)，最差情况是O(n^2^)且不稳定

选择排序

n-1次的循环比较，然后选出最小数的下标，然后进行交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void SelectSort(SQList *L)
{
  int i,j,min;
  for(i=1;i<L->length;i++){
    min = i;
    for(j=i+1;j<L->length;j++){
      if(L->r[j] < L->r[min]){
        min = j;
      }
      if(i!=min){
        swap(L,i,min);
      }
    }
  }
}

java写法

1
2
3
4
5
6
7
8
9
10
11
12
public static void selection_sort(int[] arr) {
	int i, j, min, temp, len = arr.length;
	for (i = 0; i < len - 1; i++) {
		min = i;
		for (j = i + 1; j < len; j++)
			if (arr[min] > arr[j])
				min = j;
		temp = arr[min];
		arr[min] = arr[i];
		arr[i] = temp;
	}
}

冒泡排序

  1. 比较相邻的元素。 如果第一个比第二个大，就交换他们两个。
  2. 从开始第一对到结尾的最后一对，每对相邻元素都作同样的工作，。 这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

用C写一个冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubble(int r[n])
{
  	int exchange=1;
	for(int i=0;i<=n && exchange=1; i++) //如果为0，说明已经有序
	{
      	exchange=0;
		for(int j=0; j<n-i;j++) 
			if (r[j]>r[j+1]){   //注意是从头开始比较
				temp=r[j+1];
				r[j+1]=r[j];
				r[j]=temp;
				exchange=1;
            } 
	}
}

用Java写一个冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Comparator;
 
/**
 * 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换)
 * @author骆昊
 *
 */
public interface Sorter {
 
   /**
    * 排序
    * @param list 待排序的数组
    */
   public <T extends Comparable<T>> void sort(T[] list);
 
   /**
    * 排序
    * @param list 待排序的数组
    * @param comp 比较两个对象的比较器
    */
   public <T> void sort(T[] list, Comparator<T> comp);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.Comparator;
 
/**
 * 冒泡排序
 * 
 * @author骆昊
 *
 */
public class BubbleSorter implements Sorter {
 
    @Override
    public <T extends Comparable<T>> void sort(T[] list) {
        boolean swapped = true;
        for (int i = 1, len = list.length; i < len && swapped; ++i) {
            swapped = false;
            for (int j = 0; j < len - i; ++j) {
                if (list[j].compareTo(list[j + 1]) > 0) {
                    T temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                    swapped = true;
                }
            }
        }
    }
 
    @Override
    public <T> void sort(T[] list, Comparator<T> comp) {
        boolean swapped = true;
        for (int i = 1, len = list.length; i < len && swapped; ++i) {
            swapped = false;
            for (int j = 0; j < len - i; ++j) {
                if (comp.compare(list[j], list[j + 1]) > 0) {
                    T temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                    swapped = true;
                }
            }
        }
    }
}

堆排序

大顶堆：每个结点的值都大于等于其左右孩子结点的值

小顶堆：每个结点的值都小于等于其左右孩子结点的值

将待排的序列构成一个大顶堆，然后取走堆顶（最大值），然后再调整大顶堆，再取走堆顶，如此往复

每次取走堆顶后，把堆顶替换成之前最后的那个元素，然后再重新排序

最好和最差的情况都是O(nlogn)但不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public static void sort(int[] a){
    int arrayLength=a.length;
    //循环建堆
    for(int i=0;i<arrayLength-1;i++){
        //建堆
        buildMaxHeap(a,arrayLength-1-i);
        //交换堆顶和最后一个元素
        swap(a,0,arrayLength-1-i);
    }
}
//对data数组从0到lastIndex建大顶堆
public static void buildMaxHeap(int[] data, int lastIndex){
    //从lastIndex处节点（最后一个节点）的父节点开始
    for(int i=(lastIndex-1)/2;i>=0;i--){
        //k保存正在判断的节点
        int k=i;
        //如果当前k节点的子节点存在
        while(k*2+1<=lastIndex){
            //k节点的左子节点的索引
            int biggerIndex=2*k+1;
            //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
            if(biggerIndex<lastIndex){
                //若果右子节点的值较大
                if(data[biggerIndex]<data[biggerIndex+1]){
                    //biggerIndex总是记录较大子节点的索引
                    biggerIndex++;
                }
            }
            //如果k节点的值小于其较大的子节点的值
            if(data[k]<data[biggerIndex]){
                //交换他们
                swap(data,k,biggerIndex);
                //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
                k=biggerIndex;
            }else{
                break;
            }
        }
    }
}
//交换
private static void swap(int[] data, int i, int j) {
    int tmp=data[i];
    data[i]=data[j];
    data[j]=tmp;
}

速学路径

http://blog.csdn.net/xiaoxiaoxuewen/article/details/7570621/

http://www.cnblogs.com/kkun/archive/2011/11/23/2260286.html

归并排序

把n个有序的子序列两两归并，直到归并成一个序列

最好和最差的情况都是O(nlogn)但稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public int[] gb_sort(int[] nums, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
        // 左边
        gb_sort(nums, low, mid);
        // 右边
        gb_sort(nums, mid + 1, high);
        // 左右归并
        merge(nums, low, mid, high);
    }
    return nums;
}

public void merge(int[] nums, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;// 左指针
    int j = mid + 1;// 右指针
    int k = 0;
    // 把较小的数先移到新数组中
    while (i <= mid && j <= high) {
        if (nums[i] < nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    // 把左边剩余的数移入数组
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    // 把右边边剩余的数移入数组
    while (j <= high) {
        temp[k++] = nums[j++];
    }
    // 把新数组中的数覆盖nums数组
    for (int k2 = 0; k2 < temp.length; k2++) {
        nums[k2 + low] = temp[k2];
    }
}

速学路径

http://blog.csdn.net/yinjiabin/article/details/8265827/

基数排序

从序列的个位开始排列，然后到十位开始排列，直到最高的位数

最好和最坏的情况都是O(d(n+rd))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public void radix_sort(int[] array){
    int max = array[0];
    for (int i = 0;i<array.length;i++){
        if (array[i] > max){
            max = array[i];
        }
    }
    int time = 0;
    while (max>0){
        max /= 10;
        time++;
    }
    int k = 0;
    int m = 0;
    int n = 1;
    int max_sd = 0;
    int[][] tempArr = new int[10][array.length];
    int[] order = new int[10];
    while (m<time){
        for (int i = 0;i<array.length;i++){
            int sd = (array[i] / n) % 10;
            tempArr[sd][order[sd]] = array[i];
            order[sd]++;
            if (sd>max_sd){
                max_sd = sd;
            }
        }
        for (int i = 0;i<10;i++){
            for (int j = 0;order[i] != 0 && j<order[i];j++){
                array[k++] = tempArr[i][j];
            }
            order[i]=0;
        }
        n *= 10;
        k = 0;
        m++;
    }
}

速学路径

http://blog.chinaunix.net/uid-26722078-id-3668671.html

http://www.cnblogs.com/kkun/archive/2011/11/23/2260275.html

各类算法比较