一、插入排序。
一）直接插入排序。
第一步，取第一个数57，因为只有唯一的数，不用排序，取68与其比较，68>57,所以68插入在57后面。
第二步，取59,57>59>68，将59插入。
可以看到插入排序适合链表结构。
二）希尔排序。
最后一步得到了一个基本有序的序列，再进行插入排序，可以看到，希尔排序的每一步都要用到插入排序。
二、 选择排序。
一）直接选择排序。
第一步：在序列中选择一个最小的——52，与第一个交换[52，68，59，57]，需要比较n-1次。
第二步：在剩余的[68，59，57]中再选择最小的，把最小的数与之交换，需要比较n-2次。
时间复杂度为1+2+3+……n-1=n(n-1)/2
二）堆排序。
第一步建立完全二叉树，将数据依次填入。
第二步 n/2=3 找到第三个节点56，比其子节点84小，将86与54位置对调。
第三步 n/2 -1 =2 节点，找到79 ，比两个叶子节点都要大，不做调整。
第四步 n/2 -2=1 节点，找到46，比两个叶子都要小，选择大的84对调，对调完成后发现46形成的新二叉树不是堆，在进一步将46与56对调。
最后得到的堆为[84,79,56,38,40,46]
排序操作。将第一个节点与最后一个节点对调，得到[84],断开最后一个节点，对调后如果不是堆要重新调整，如本题46<[79,56]，将46与79对调，直到是一个堆。
下一步继续将79与40对调，断开79链接，形成新的堆……最终得到一个有序序列。
三、 交换排序。
一）冒泡排序。
求一个从小到大的序列。
二）快速排序。
首先选出一个关键字，将所有元素与该关键字对比，小的放在关键字之前，大的放在之后，关键字放中间。
然后再用同样的方法对两个小的序列再进行排序，直到为一。
一趟排序之后效果如图：
四、 归并排序。
哈希表。一、基本概念。
二、处理冲突的方法。
一）线性探查法。
记录关键码为（3,8,12,17），存储空间为10，散列函数为hash = key %5
例题：求平均长度。
因此：平均查找长度为2
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...