数据结构(二叉树相关、满、完全二叉树、霍夫曼树、排序方法和时间复杂度、)笔记-day11

目录

前言

一、树(Tree)

1.1树及特征

1.2二叉树概念及性质

1.3二叉树存储结构及遍历

1.4链式存储编码

二、霍夫曼树(最优二叉树)

2.1权值及带权路径长度

2.2霍夫曼树特征及构建

三、算法

3.1算法问题规模

3.2时间复杂度、时间复杂度

3.3稳定性判断

四、排序方法总结

4.1冒泡排序

4.2选择排序

4.2.1直接选择排序

4.2.2简单选择排序

4.3插值排序

4.4快速排序（快排）

总结

前言

二叉树思想详解，链式二叉树代码具体实现；什么是满二叉树、完全二叉树及区别？、霍夫曼树（权带路径长度、霍夫曼树特征）排序方法及时间复杂度总结，今天重点是二叉树相关知识、排序方法总结及对应的时间复杂度、空间复杂度和稳定性判断总结。

一、树(Tree)

    特征：一对多，每个节点最多有一个前驱，但可以有多个后继（根节点无前驱，叶节点无后继）

1.1树及特征

1.  
   关于树的一些基本概念
2.  
   (1)度数：一个节点的子树的个数 //节点生儿子的个数
3.  
   (2)树度数：树中节点的最大度数 //生儿子最多的那个节点的度数，代表这颗树的度数
4.  
   (3)叶节点或终端节点: 度数为零的节点 //没有儿子的都是叶子
5.  
   (4)分支节点：度数不为零的节点 //除了叶子节点以外的都是分支节点
6.  
   (5)内部节点：除根节点以外的分支节点 //除了根节点 和 叶节点以外剩下的就是内部节点
7.  
   (6)节点层次: 根节点的层次为1，根节点子树的根为第2层，以此类推
8.  
   (7)树的深度或高度: 树中所有节点层次的最大值

1.2二叉树概念及性质

1.  
   二叉树概念：二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），
2.  
   或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。
3.  
   二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。
4.  
    
5.  
   二叉树：树的最大的度数为2,树的度数，不能超过2,同时二叉树严格区分左子和右子
6.  
    
7.  
   二叉树性质：
8.  
   (1)二叉树第k（k>=1) 层上的节点最多 2^(k-1) 个　//2的k-1次幂
9.  
   (2)深度为k（k>=1)的二叉树最多有 2^k - 1 个节点。//2的k次幂再-1 所有层最多节点的和
10.  
    //每一层的节点都达到最大值，此时的树节点最多；每层都是最多节点 累加求和，就是这颗树的节点数
11.  
    2*n = 2^(k) 2^(k-1) 2^(k-2) ....... 2^3 2^2 2^1
12.  
    n = 2^(k-1) 2^(k-2) 2^(k-3) ....... 2^2 2^1 2^0
13.  
    k k-1 k-2 3 2 1
14.  
     
15.  
    n = 2^k - 2^0 ---> 2^k - 1 //将上面的式子左右*2，再将上下两个式子相减
16.  
     
17.  
    (3)在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一
18.  
    任意一颗二叉树，度数为0节点的个数 都比度数为2节点的个数多一
19.  
     
20.  
    一个二叉树 所有节点的个数 n
21.  
    总节点个数 n = 度数为2的节点个数 度数为1的节点个数 度数为0的节点个数
22.  
    n = n2 n1 n0
23.  
     
24.  
    总节点个数n = 1(根) 所有的子节点的个数
25.  
     
26.  
    度数为2的节点个数为 n2个，那么度数为2的节点的子节点个数？？ 2*n2
27.  
    度数为1的节点个数为 n1个，那么度数为1的节点的子节点个数？？ n1
28.  
    度数为0的节点个数为 n0个，那么度数为0的节点的子节点个数？？ 0
29.  
    树总节点的个数 n
30.  
    n = n0 n1 n2;
31.  
    树总节点的个数 n＝根 所有的子节点
32.  
    n = 1 n2*2 n1;
33.  
    n = n0 n1 n2;
34.  
    //将两个式子相减
35.  
    0 = 1 2*n2 - n0 - n2;
36.  
    0 = 1 n2 - n0
37.  
    n0 = n2 1 ;
38.  
    总节点数为各类节点之和：n = n0 n1 n2
39.  
    总节点数为所有子节点数加一：n = n1 2*n2 1
40.  
    故得：n0 = n2 1
41.  
    (4)满二叉树和完全二叉树
42.  
    满二叉树： 深度为k（k>=1）时节点为2^k - 1(2的k次幂-1)
43.  
    完全二叉树:只有最下面两层有度数小于2的节点，且最下面层叶节点集中在最左边的若干位置上。
44.  
    //在满二叉树的最后一层，自右向左连续缺失若干个节点；保证最后一层剩余的节点都在左侧
45.  
     
46.  
    总结：
47.  
    (1) 深度为k的二叉树，最多有多少个节点 2^k - 1
48.  
    (2) 二叉树的第k层，最多有多少个节点 2^(k-1)
49.  
    (3) 度数为0的节点和度数为2的节点个数是什么关系 // n0 = n2 1;

1.3二叉树存储结构及遍历

1.  
   二叉树的存储结构(可以用数组 也可以用链表)//二叉树，用数组来表达，浪费存储空间
2.  
   (1)二叉树的顺序存储结构：完全二叉树节点的编号方法是从上到下，从左到右，根节点为1号节点。设完全二叉树的节点数为n，
3.  
   (2)节点编号（******重点）
4.  
   若根节点编号 1 　　　　　根节点左子节点编号：2 根节点右子节点编号： 3
5.  
   第n个节点的节点编号是n 左子节点编号：2*n 　　右子节点编号：2*n 1
6.  
    
7.  
   若根节点编号 0 根节点左子节点编号：1 　根节点右子节点编号： 2
8.  
   第n个节点的节点编号是n 左子节点编号：2*n 1　　　右子节点编号：2*n 2
9.  
    
10.  
    有n个节点的完全二叉树可以用有n 1个元素的数组进行顺序存储，节点号和数组下标对应，下标为零的元素不用。
11.  
    利用以上特性，可以从下标获得节点的逻辑关系。不完全二叉树通过添加虚节点构成完全二叉树，然后用数组存储／／浪费存储空间
12.  
     
13.  
    （4）二叉树的遍历（重点*****************）
14.  
    前序遍历 根 左 右
15.  
    中序遍历 左 根 右
16.  
    后序遍历 左 右 根
17.  
    所谓前序、中序、后序遍历都是根据根节点的位置来看的

1.4链式存储编码

1.  
   #include <stdio.h>
2.  
    
3.  
   typedef struct node_t
4.  
   {
5.  
   char data;//数据域
6.  
   struct node_t* lchild;//left 指向左子的指针
7.  
   struct node_t* rchild;//right 指向右子的指针
8.  
   }tree_node_t;
9.  
   //二叉树的遍历 tree_node_t* r 用来保存一颗树,根节点的首地址
10.  
    //前序
11.  
    void preorder(tree_node_t* r)
12.  
    {
13.  
    if(r == NULL)//递归的结束条件
14.  
    return;
15.  
    printf("%c",r->data);//根
16.  
    preorder(r->lchild);//左 因为继续将根左子,当做一棵新的树的根来看待,递归继续进行根 左 右 的方式遍历
17.  
    preorder(r->rchild);//右 和递归左同理
18.  
    }
19.  
    //中序
20.  
    void inorder(tree_node_t* r)
21.  
    {
22.  
    if(r == NULL)//递归结束条件
23.  
    return;
24.  
    inorder(r->lchild);//左
25.  
    printf("%c",r->data);//根
26.  
    inorder(r->rchild);//右
27.  
    }
28.  
    //后序
29.  
    void postorder(tree_node_t* r)
30.  
    {
31.  
    if(r == NULL)//递归结束条件
32.  
    return;
33.  
    postorder(r->lchild);
34.  
    postorder(r->rchild);
35.  
    printf("%c",r->data);
36.  
    }
37.  
     
38.  
    int main()
39.  
    {
40.  
    tree_node_t a = {'A',NULL,NULL};
41.  
    tree_node_t b = {'B',NULL,NULL};
42.  
    tree_node_t c = {'C',NULL,NULL};
43.  
    tree_node_t d = {'D',NULL,NULL};
44.  
    tree_node_t e = {'E',NULL,NULL};
45.  
    tree_node_t f = {'F',NULL,NULL};
46.  
    a.lchild = &b;
47.  
    a.rchild = &c;
48.  
    b.lchild = &d;
49.  
    c.lchild = &e;
50.  
    c.rchild = &f;
51.  
    printf("前序:");
52.  
    preorder(&a);
53.  
    printf("\n");
54.  
    printf("中序:");
55.  
    inorder(&a);
56.  
    printf("\n");
57.  
    printf("后序:");
58.  
    postorder(&a);
59.  
    printf("\n");
60.  
    }

 写一个创建二叉树的函数,二叉树的每个节点的数据域,来自于键盘输入

1.  
   //自己输入创建一棵树
2.  
   #include <stdio.h>
3.  
   #include <stdlib.h>
4.  
    
5.  
   typedef struct node_t
6.  
   {
7.  
   char data;//数据域
8.  
   struct node_t* lchild;//left 指向左子的指针
9.  
   struct node_t* rchild;//right 指向右子的指针
10.  
    }tree_node_t;
11.  
     
12.  
    //二叉树的遍历 tree_node_t* r 用来保存一颗树,根节点的首地址
13.  
    //前序
14.  
    void preorder(tree_node_t* r)
15.  
    {
16.  
    if(r == NULL)//递归的结束条件
17.  
    return;
18.  
    printf("%c",r->data);//根
19.  
    preorder(r->lchild);//左 因为继续将根左子,当做一棵新的树的根来看待,递归继续进行根 左 右 的方式遍历
20.  
    preorder(r->rchild);//右 和递归左同理
21.  
    }
22.  
    //中序
23.  
    void inorder(tree_node_t* r)
24.  
    {
25.  
    if(r == NULL)//递归结束条件
26.  
    return;
27.  
    inorder(r->lchild);//左
28.  
    printf("%c",r->data);//根
29.  
    inorder(r->rchild);//右
30.  
    }
31.  
    //后序
32.  
    void postorder(tree_node_t* r)
33.  
    {
34.  
    // if(r == NULL)//递归结束条件
35.  
    // return;
36.  
    if(r != NULL)
37.  
    {
38.  
    postorder(r->lchild);
39.  
    postorder(r->rchild);
40.  
    printf("%c",r->data);
41.  
    }
42.  
    }
43.  
    //写一个创建二叉树的函数,二叉树的每个节点的数据域,来自于键盘输入
44.  
    //函数的返回值是这棵树,根节点的首地址
45.  
    tree_node_t* createBinTree()
46.  
    {
47.  
    char ch;//用来保存输入字符,二叉树的数据域
48.  
    scanf("%c",&ch);//A
49.  
    if(ch == '#')//递归函数的结束条件
50.  
    {
51.  
    return NULL;
52.  
    }
53.  
     
54.  
    //malloc申请一个节点的空间
55.  
    tree_node_t* r = (tree_node_t*)malloc(sizeof(tree_node_t));
56.  
    if(r == NULL)
57.  
    {
58.  
    printf("r malloc failed!!\n");
59.  
    return NULL;
60.  
    }
61.  
    //申请空间后,立刻给成员变量赋值
62.  
    r->data = ch;
63.  
    r->lchild = createBinTree();
64.  
    r->rchild = createBinTree();
65.  
     
66.  
    return r;
67.  
    }
68.  
     
69.  
    int main()
70.  
    {
71.  
    tree_node_t* r = createBinTree();
72.  
    printf("前序:");
73.  
    preorder(r);
74.  
    printf("\n");
75.  
    printf("中序:");
76.  
    inorder(r);
77.  
    printf("\n");
78.  
    printf("后序:");
79.  
    postorder(r);
80.  
    printf("\n");
81.  
    }

1.  
   //二叉树，函数指针的应用
2.  
   #include <stdio.h>
3.  
   #include <stdlib.h>
4.  
    
5.  
   typedef struct node_t
6.  
   {
7.  
   char data;//数据域
8.  
   struct node_t* lchild;//left 指向左子的指针
9.  
   struct node_t* rchild;//right 指向右子的指针
10.  
    }tree_node_t;
11.  
     
12.  
    //二叉树的遍历 tree_node_t* r 用来保存一颗树,根节点的首地址
13.  
     
14.  
    //前序
15.  
    void preorder(tree_node_t* r)
16.  
    {
17.  
    if(r == NULL)//递归的结束条件
18.  
    return;
19.  
    printf("%c",r->data);//根
20.  
    preorder(r->lchild);//左 因为继续将根左子,当做一棵新的树的根来看待,递归继续进行根 左 右 的方式遍历
21.  
    preorder(r->rchild);//右 和递归左同理
22.  
    }
23.  
    //中序
24.  
    void inorder(tree_node_t* r)
25.  
    {
26.  
    if(r == NULL)//递归结束条件
27.  
    return;
28.  
    inorder(r->lchild);//左
29.  
    printf("%c",r->data);//根
30.  
    inorder(r->rchild);//右
31.  
    }
32.  
    //后序
33.  
    void postorder(tree_node_t* r)
34.  
    {
35.  
    // if(r == NULL)//递归结束条件
36.  
    // return;
37.  
    if(r != NULL)
38.  
    {
39.  
    postorder(r->lchild);
40.  
    postorder(r->rchild);
41.  
    printf("%c",r->data);
42.  
    }
43.  
    }
44.  
     
45.  
    //遍历二叉树
46.  
    //参数1 void(*p)(tree_node_t*) 是一个函数指针变量p
47.  
    //参数2 tree_node_t* r代表要打印的那棵树的根节点的首地址
48.  
    //参数3 char* s 打印提示
49.  
    void showBinTree(char* s,void (*p)(tree_node_t*), tree_node_t* r)
50.  
    {
51.  
    printf("%s",s);//前序 中序 后序
52.  
    (*p)(r);//通过函数指针,调用函数
53.  
    printf("\n");
54.  
    }
55.  
     
56.  
    //写一个创建二叉树的函数,二叉树的每个节点的数据域,来自于键盘输入
57.  
    //函数的返回值是这棵树,根节点的首地址
58.  
    tree_node_t* createBinTree()
59.  
    {
60.  
    char ch;//用来保存输入字符,二叉树的数据域
61.  
    scanf("%c",&ch);//A
62.  
    if(ch == '#')//递归函数的结束条件
63.  
    {
64.  
    return NULL;
65.  
    }
66.  
     
67.  
    //malloc申请一个节点的空间
68.  
    tree_node_t* r = (tree_node_t*)malloc(sizeof(tree_node_t));
69.  
    if(r == NULL)
70.  
    {
71.  
    printf("r malloc failed!!\n");
72.  
    return NULL;
73.  
    }
74.  
    //申请空间后,立刻给成员变量赋值
75.  
    r->data = ch;
76.  
    r->lchild = createBinTree();
77.  
    r->rchild = createBinTree();
78.  
     
79.  
    return r;
80.  
    }
81.  
    int main()
82.  
    {
83.  
    tree_node_t* r = createBinTree();
84.  
    showBinTree("前序:",preorder, r);
85.  
    showBinTree("中序:",inorder, r);
86.  
    showBinTree("后序:",postorder, r);
87.  
    }

二、霍夫曼树(最优二叉树)

2.1权值及带权路径长度

1.  
   　　霍夫曼树（Huffman Tree），又称最优二叉树，是一类 带权 路径长度 最短的树。
2.  
   假设有n个权值{w1,w2,…,wn}，如果构造一棵有n个叶子节点的二叉树，而这n个叶子节点的权值是{w1,w2,…,wn}，则所构造出的带权路径长度最小的二叉树就被称为霍夫曼树。
3.  
   树带权路径长度:树的带权路径长度指树中所有叶子节点到根节点的路径长度与该叶子节点权值的乘积之和，如果在一棵二叉树中共有n个叶子节点，用Wi表示第i个叶子节点的权值，Li表示第i个也叶子节点到根节点的路径长度，则该二叉树的带权路径长度 WPL=W1*L1 W2*L2 … Wn*Ln。

2.2霍夫曼树特征及构建

1.  
   霍夫曼树特征 ：
2.  
   (1)赫夫曼树的左右子树可以互换，因为这并不影响树的带权路径长度。
3.  
   (2)带权值的节点都是叶子节点，不带权值的节点都是某棵子二叉树的根节点。
4.  
   (3)权值越大的节点越靠近赫夫曼树的根节点，权值越小的节点越远离赫夫曼树的根节点。
5.  
   (4)赫夫曼树中只有叶子节点和度为2的节点，没有度为1的节点。
6.  
   只有度数0 和 度数为2的节点
7.  
   赫夫曼树的构建步骤如下：
8.  
   　　(1)将给定的n个权值看做n棵只有根节点（无左右孩子）的二叉树，组成一个集合HT，每棵树的权值为该节点的权值。对四个二叉树，按照权值进行排序,排完序之后，前两个就是最小的
9.  
   (2)从集合HT中选2棵权值最小的二叉树，组成一棵新的二叉树，其权值为这2棵二叉树的权值之和。
10.  
    (3)将步骤2中选出的2棵二叉树从集合HT中删去，同时将步骤2中新得到的二叉树加入到集合HT中。
11.  
    (4)重复步骤2和步骤3，直到集合HT中只含一棵树，这棵树便是赫夫曼树。
12.  
    Huffman编码 ：左0右1
13.  
    赫夫曼树的应用十分广泛，比如众所周知的在通信电文中的应用。
14.  
    在等传送电文时，我们希望电文的总长尽可能短，因此可以
15.  
    对每个字符设计长度不等的编码，让电文中出现较多的字符采用尽可能短的编码。
16.  
    为了保证在译码时不出现歧义，

三、算法

3.1算法问题规模

1.  
   所谓算法问题的规模，实际上就是对算法处理问题大小的一种抽象，我们一般习惯使用n、m等字符表示一个问题的规模。举一个比较实际的例子：例如一个排序算法是针对数组进行排序的，那么这个数组中的元素数量就可以认为是这个排序问题的规模；再比如说：使用二分搜索算法在一个ArrayList集合中查询一个指定元素的下标，那么这个集合的长度就可以看做是这个二分搜索
2.  
   问题的规模所以：算法的规模实际上就是这个算法解决的问题中，保存数据多少的一种描述
3.  
   int a[100]; //排序 问题规模n = 100
4.  
    
5.  
   算法的时间复杂度和空间复杂度
6.  
   俗话说：算法没有优劣之分，只有快慢之别
7.  
   不同的算法适用于不同的场景，算法之间本身没有好与坏的区别，有的只是在处理相同规模问题的时候，谁快谁慢
8.  
   哪一种算法占用辅助空间更少的区别算法的时间复杂度和空间复杂度是用来衡量一个算法快慢与否以及运行时占用辅助空间大小的一种计算标准，
9.  
   一般用O()表示
10.  
    这里需要特殊强调的是：算法的时间复杂度一般是无法精确计算的，因为一个算法在运行时消耗的时间是以毫秒为单位来统计的
11.  
    但是因为计算机硬件配置的不同，所以同一个算法在不同计算机上，既是计算的是同一组数据，那么使用的时间也是有很大差异的
12.  
    例如：同样是使用冒泡排序对10万个随机正整数进行排序操作，在一台单核CPU的计算机上和在一台i7多核CPU的计算机上进行计算
13.  
    其运算时间一定是具有很大差异的
14.  
    所以我们得出一个结论：算法的时间复杂度是不能精确计算的，所有算法的时间复杂度只不过是对算法运行时间和处理问题规模之间
15.  
    关系的一种估算描述

3.2时间复杂度、时间复杂度

1.  
   时间复杂度：
2.  
   时间复杂度是用来大致描述算法运行时间和算法处理问题规模之间关系的一种衡量标准
3.  
   一个算法的时间复杂度越高，那么也就说明这个算法在处理问题的时候所花费的时间也就越长
4.  
   但是正如前面我们说过的，一个算法的时间复杂程度并不能被精确计算出来，我们计算算法时间复杂程度，也只不过是粗略的估算
5.  
   那么，在一个算法的运算过程用时公式被计算出来之后，我们遵从如下“忽略”标准描述其时间复杂度：
6.  
    
7.  
   1.忽略公式中的常数项
8.  
   2.忽略公式中的低次幂项，仅保留公式中的最高次幂项
9.  
   3.忽略公式中最高次幂项的常数系数
10.  
    4.如果一个公式中所有的项都是常数项，那么这个算法的时间复杂度统一表示为O(1)
11.  
     
12.  
    下面我们来举几个相关的案例进行说明：
13.  
    例1：算法1的运算过程用时公式是：2*n2 5*n 6，则这个算法的时间复杂度是O(n2)
14.  
    例2：算法2的运算过程用时公式是：nlogn 5n 2，则这个算法的时间复杂度是O(nlogn)
15.  
    例3：算法3的运算过程用时公式是：2n 7，则这个算法的时间复杂度是O(n)
16.  
    例4：元素交换算法只有3个步骤，其运算过程用时公式为：1 1 1，则其时间复杂度是O(1)
17.  
     
18.  
    在排序算法中，常见的时间复杂度有3种，分别是：O(n2)、O(nlogn)、O(n)
19.  
    其中logn表示以2为底n的对数，这个值到底是怎么计算出来的，在快速排序算法中我们会详细进行分析
20.  
    上述的3种时间复杂度之间的大小关系是：O(n2)(冒泡) > O(nlogn)(快排) > O(n)（顺序查找）
21.  
    //二分是 O(logn) 快排(nlogn)
22.  
    也就是说，时间复杂度为O(n2)的排序算法运行效率最低，也就是最慢；时间复杂度为O(n)的排序算法运行效率最高，也就是最快
23.  
     
24.  
    时间复杂度：
25.  
     
26.  
    空间复杂度是用来衡量一个算法在运行过程当中，在除了保存原始数据的空间之外，还需要额外消耗多少空间的一种衡量标准
27.  
    举个例子：冒泡排序在执行过程中，只需要消耗一个临时变量，用来交换两个反序的元素即可，所以冒泡排序的空间复杂度就是O(1)
28.  
    空间复杂度和时间复杂度一样，也是用来描述算法问题规模和运算时消耗额外空间之间关系的一种表达式，并不是用来详细计算数值的公式
29.  
    排序算法中空间复杂度常见的也是有3种：O(1)、O(n)、O(logn)
30.  
    而空间复杂度和时间复杂度相似的是，空间复杂度越高，就表示这个算法在运行过程中所需要消耗的额外空间也就越多
31.  
    从这个角度来讲，上面的三种空间复杂度之间的关系可以看做：O(n) > O(logn) > O(1)
32.  
    也就是说，在空间复杂度层面来讲，O(1)是最小的空间复杂度

3.3稳定性判断

1.  
   排序算法的稳定性：
2.  
   排序算法的稳定性指的是，在一个排序算法处理的数组或者集合中，如果存在取值相同的元素，
3.  
   那么在排序完成前后，这些取值相同的元素之间的相对顺序有没有发生变化
4.  
   如果排序之后，取值相同元素之间的相对顺序没有发生变化，那么这个排序算法就是稳定的
5.  
   如果排序之后，取值相同元素之间的相对顺序发生了变化，那么这个排序算法就是不稳定的
6.  
    
7.  
   　　　　具体案例我们可以看如下图片：12 3 34a 1 423 34b
8.  
    
9.  
   　　　　//不稳定排序
10.  
    如果你排序结束后 34b 在 34a 的前面，说明相同数据被交换了位置，此时称为不稳定排序
11.  
    1 3 12 34b 34a 423
12.  
     
13.  
    //稳定排序
14.  
    如果你排序结束后 34b 在 34a 的前面，说明相同数据没有交换位置，此时称为不稳定排序
15.  
    1 3 12 34a 34b 423
16.  
    影响排序的效率：（1）交换次数 （2）移动次数

四、排序方法总结

4.1冒泡排序

1.  
   void bubbleSort(int *p, int n)
2.  
   {
3.  
   int i,j;
4.  
   int temp;
5.  
   for(i = 0; i < n-1; i )
6.  
   {
7.  
   for(j = 0; j < n-1-i; j )
8.  
   {
9.  
   if(p[j] > p[j 1])
10.  
    {
11.  
    temp = p[j];
12.  
    p[j] = p[j 1];
13.  
    p[j 1] = temp;
14.  
    }
15.  
    }
16.  
    }
17.  
    }

4.2选择排序

1.  
   　　选择排序的原理与冒泡排序相比更加容易理解：选定一个标准位，将待排序序列中的元素与标准位元素逐一比较，反序则互换
2.  
   其中所谓的标准位实际上也是数组中的一个下标位，在选定了这个下标位之后，在一轮排序中这个标准位将不再移动，
3.  
   然后将待排序序列——也就是这个标准位之后所有元素组成的序列——中的元素逐个和标准位上的值进行比较
4.  
   如果某一个待排序序列上的值比标准位上的值更小（升序排序）或者更大（降序排序），那么就将这个元素和标准位上的元素进行互换即可
5.  
   标准位的选择一般选取待排序序列的第一个下标作为标准位使用

4.2.1直接选择排序

1.  
   void selectSort(int* p, int n)
2.  
   {
3.  
   int i,j;
4.  
   for(i = 0; i < n-1; i )//外循环i代表的是每次选择的基准位置，<n-1是因为最后剩下一个默认就是最大了
5.  
   {
6.  
   //内循环，需要拿基准为止p[i]与p[i]之后-最后每一个都比较一次
7.  
   //因为是p[i]之后的所以j = i 1 j < n
8.  
   for(j = i 1; j < n; j )
9.  
   {
10.  
    if(p[i] > p[j])
11.  
    {
12.  
    int temp = p[i];
13.  
    p[i] = p[j];
14.  
    p[j] = temp;
15.  
    }
16.  
    }
17.  
    }
18.  
    }

4.2.2简单选择排序

1.  
   void selectSort2(int *p, int n)
2.  
   {
3.  
   int i,j;
4.  
   int min;
5.  
   for(i = 0; i < n-1; i )
6.  
   {
7.  
   min = i;//先将基准位置保存到min中
8.  
   for(j = i 1; j < n; j )
9.  
   {
10.  
    if(p[min] > p[j])
11.  
    {
12.  
    min = j;//将最小值的下标记录下来
13.  
    }
14.  
    }
15.  
    if(min != i)//如果最小值的下标和原来的不相等，说明遇到比基准值小的，需要交换位置
16.  
    {
17.  
    int temp = p[min];
18.  
    p[min] = p[i];
19.  
    p[i] = temp;
20.  
    }
21.  
    }
22.  
    }

4.3插值排序

1.  
   插值排序：插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，
2.  
   就是第一个元素。比较是从有序序列的末尾开 始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它
3.  
   大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的，那么插入元
4.  
   素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序
5.  
   后的顺序，所以插入排序是稳 定的。
6.  
    
7.  
   排序思想，来源于打扑克 打牌 抓牌 斗地主
8.  
   1 6
9.  
   int a[] = {6,3,'J',10,7,'K',2};
10.  
    抓牌思想 最开是默认你的手里已经有了一张牌，然后开始一张一张的抓牌
11.  
    在抓牌的过程中，每抓一张牌，要将牌插入在适当位置上，保证自己手里的牌
12.  
     
13.  
    始终是有序的
14.  
    默认手里面已经有了一张6
15.  
    6
16.  
    抓了一张牌,拿3和6比，如果小，交换位置
17.  
    3 6
18.  
    继续抓一张牌 'J',因为'J'比你手中最大的牌都要大，所以不用交换
19.  
    3 6 'J'
20.  
    继续抓一张牌 10
21.  
    3 6 10 'J'
22.  
    继续抓一张牌 7
23.  
    3 6 7 10 'J'
24.  
    继续抓一张牌 'K'
25.  
    3 6 7 10 'J' 'K'
26.  
    继续抓一张牌 '2'
27.  
    2 3 6 7 10 'J' 'K'

1.  
   //思考:为什么i从1开始
2.  
   // i = 0 就是手里默认已经有了那张牌 i = 1是因为，默认你的手里已经有了一张牌，已经是有序序列了，抓的牌从1开始
3.  
   for(i = 1; i < n; i )//循环变量i代表你每次抓那张牌
4.  
   {
5.  
   //外循环，每循环一次，代表你抓了一张牌，我们抓完牌后，
6.  
   //需要对手里的牌进行排序
7.  
   //从当前刚抓的第i张排开始，两两相比较，向前比较
8.  
   for(j = i; j > 0; j--)
9.  
   {
10.  
    if(p[j] < p[j-1])
11.  
    {
12.  
    int temp = p[j];
13.  
    p[j] = [j-1];
14.  
    p[j-1] = temp;
15.  
    }
16.  
    else //因为手里的牌始终是有序的，抓的牌如果比手里的牌大，没必要继续向前比较
17.  
    {
18.  
    break;
19.  
    }
20.  
    }
21.  
    }
22.  
    void insertSort(int *p, int n)
23.  
    {
24.  
    int i,j;
25.  
    int temp;
26.  
    for(i = 1; i < n; i )
27.  
    {
28.  
     
29.  
    for(j = i; j > 0; j--)
30.  
    {
31.  
    if(p[j] < p[j-1])
32.  
     
33.  
    {
34.  
    temp = p[j];
35.  
    p[j] = p[j-1];
36.  
    p[j-1] = temp;
37.  
    }
38.  
    else
39.  
    {
40.  
    break;
41.  
    }
42.  
    }
43.  
    }
44.  
    }

4.4快速排序（快排）

1.  
   ///快排初次理解代码-------先找到枢轴/
2.  
   #include <stdio.h>
3.  
   void quickSort(int* p, int low, int high)
4.  
   {
5.  
   //1.拿数组最左边的元素当做镖旗
6.  
   int flag = p[low];
7.  
   //2.循环进行右 左的扫描，最终显示flag左侧都比flag小
8.  
   //flag右侧都比flag大
9.  
   while(low < high)// low == high 循环结束
10.  
    {
11.  
    //从右向左扫描，只要p[high] >= flag,high--,
12.  
    //因为p[high] >= flag 本就应该在flag的右边，不需要移动到左边
13.  
    while(p[high] >= flag && low < high)
14.  
    {
15.  
    high--;//high--，high的值已经发生了变化，我们需要立即做出判断，让最外面的循环while(low < high)立即结束
16.  
    }
17.  
    //上面的循环结束后，说明我们遇到了 p[high] < flag的数，需要
18.  
    //将其从右边移动到左边，进行赋值操作
19.  
    if(low < high)
20.  
    {
21.  
    p[low] = p[high];
22.  
    //改变扫描方向,变为从左向右扫描
23.  
    low ;//改变扫描方向后，没必要再次拿刚移动过来的数与flag比较,所以low
24.  
    }
25.  
    //从左向右开始进行扫描,只要p[low] <= flag,low
26.  
    //因为p[low] <= flag,本就应该在flag的左边，不需要移动到右边
27.  
    while(p[low] <= flag && low < high)
28.  
    {
29.  
    low ;
30.  
    }
31.  
    //上面的循环结束后，说明我们遇到了，p[low] > flag的数，需要
32.  
    //将其从左边移动到右边，进行赋值操作
33.  
    if(low < high)
34.  
    {
35.  
    p[high] = p[low];
36.  
    //赋值之后，改变扫描方向
37.  
    high--;//改变扫描方向后没必要对刚移动过来的数再次与flag比较，所以high--
38.  
    }
39.  
    //继续从右向左扫描，和上面的代码重复
40.  
    }
41.  
    //循环结束时low和high相等，此时的low或high的值被称为枢轴
42.  
    p[low] = flag;//循环结束后，将镖旗放在枢轴的位置上
43.  
    printf("数轴是%d\n",low);
44.  
    }
45.  
     
46.  
    int main(int argc, const char *argv[])
47.  
    {
48.  
    int a[8] = {32, 2, 54, 6, 78, 23, 17, 76};
49.  
    quickSort(a,0,7);
50.  
    return 0;
51.  
    }

1.  
   ///快排最终的代码/
2.  
   #include <stdio.h>
3.  
    
4.  
   void quickSort(int* p, int low, int high)
5.  
   {
6.  
   //1.拿数组最左边的元素当做镖旗
7.  
   int flag = p[low];
8.  
   int i = low;//i代表low
9.  
   int j = high;//j代表high
10.  
    //2.循环进行右 左的扫描，最终显示flag左侧都比flag小
11.  
    //flag右侧都比flag大
12.  
    while(i < j)// low == high 循环结束
13.  
    {
14.  
    //从右向左扫描，只要p[high] >= flag,high--,
15.  
    //因为p[high] >= flag 本就应该在flag的右边，不需要移动到左边
16.  
    while(p[j] >= flag && i < j)//连续遇到3个>flag的数
17.  
    {
18.  
    j--;//high--，high的值已经发生了变化，我们需要立即做出判断，让最外面的循环while(low < high)立即结束
19.  
    }
20.  
    //上面的循环结束后，说明我们遇到了 p[high] < flag的数，需要
21.  
    //将其从右边移动到左边，进行赋值操作
22.  
    if(i < j)
23.  
    {
24.  
    p[i] = p[j];
25.  
    //改变扫描方向,变为从左向右扫描
26.  
    i ;//改变扫描方向后，没必要再次拿刚移动过来的数与flag比较,所以low
27.  
    }
28.  
    //从左向右开始进行扫描,只要p[low] <= flag,low
29.  
    //因为p[low] <= flag,本就应该在flag的左边，不需要移动到右边
30.  
    while(p[i] <= flag && i < j)
31.  
    {
32.  
    i ;
33.  
    }
34.  
    //上面的循环结束后，说明我们遇到了，p[low] > flag的数，需要
35.  
    //将其从左边移动到右边，进行赋值操作
36.  
    if(i < j)
37.  
    {
38.  
    p[j] = p[i];
39.  
    //赋值之后，改变扫描方向
40.  
    j--;//改变扫描方向后没必要对刚移动过来的数再次与flag比较，所以high--
41.  
    }
42.  
    //继续从右向左扫描，和上面的代码重复
43.  
    }
44.  
    //循环结束时low和high相等，此时的low或high的值被称为枢轴
45.  
    p[i] = flag;//循环结束后，将镖旗放在枢轴的位置上
46.  
    // printf("数轴是%d\n",i);
47.  
    //我们要递归，对枢轴的左侧和数轴的右侧进行同样的思想进行排序
48.  
    //注意递归是有结束条件的
49.  
    if(low < i-1)
50.  
    {
51.  
    quickSort(p,low,i-1);//对枢轴左半部分继续递归
52.  
    }
53.  
    if(i 1 < high)
54.  
    {
55.  
    quickSort(p,i 1,high);//对枢轴右半部分继续递归
56.  
    }
57.  
    }
58.  
     
59.  
    void showArray(int* p, int n)
60.  
    {
61.  
    int i;
62.  
    for(i = 0; i < n; i )
63.  
    {
64.  
    printf("%d ",p[i]);
65.  
    }
66.  
    printf("\n");
67.  
    }
68.  
     
69.  
    int main(int argc, const char *argv[])
70.  
    {
71.  
    int a[8] = {32, 2, 54, 6, 78, 23, 17, 76};
72.  
    showArray(a,8);
73.  
    quickSort(a,0,7);
74.  
    showArray(a,8);
75.  
    return 0;
76.  
    }

1.  
   排序方法的总结:
2.  
   序号 排序算法名称 时间复杂度 空间复杂度 排序算法稳定性
3.  
    
4.  
   1 冒泡排序 O(n^2) O(1) 稳定排序
5.  
   2 选择排序 O(n^2) O(1) 不稳定排序
6.  
   3 插值排序 O(n^2) O(1) 稳定排序
7.  
   4 希尔排序 O(n^k)(1.3 <= k <= 2) O(1) 不稳定排序
8.  
   5 归并排序 O(nlogn) O(n) 稳定排序
9.  
   6 快速排序 O(nlogn) O(logn) 不稳定排序
10.  
    7 堆排序 O(nlogn) O(1) 不稳定排序
11.  
    8 桶排序 O(n m) (m为排序元素最大值)O(m) 稳定排序
12.  
    //希尔排序是对插值排序的升级
13.  
    二分法时间复杂度 O(logn)
14.  
     
15.  
    口诀：
16.  
    时间复杂度：冒泡、选择、插值、希尔是　O(n^2)；并归、快排、堆nlogn　桶是ｎ＋ｍ。
17.  
    空间复杂度：并归ｎ、快排logn、桶ｍ、其他都是O(1)
18.  
    稳定性：冒泡、插值、并归还有桶　稳

总结

这里对文章进行总结：二叉树思想详解，链式二叉树代码具体实现；满二叉树、完全二叉树及区别、霍夫曼树（权带路径长度、霍夫曼树特征）排序方法及稳定性判断以及时间、空间复杂度总结，今天的重点知识是二叉树相关知识、排序方法总结及对应的时间复杂度、空间复杂度和稳定性判断总结。

这篇好文章是转载于：学新通技术网