算法与数据结构 --- 排序 --- 交换排序 与 选择排序

第一部分 --- 交换排序 之 冒泡排序

1.在给待排序序列排序之前我们需要先设定一个 “ 序 ” --- 即我们是从小到大排还是从大到小排，而所谓的逆序是一个状态，当当前前序列是有序的，且有序状态与我们规定的“ 序 ”完全相反时，我们就称这个序列的有序状态为逆序

比如我们规定序为：从小到大，此时我们的待排序序列是有序的，且有序状态为从大到小，所以此时待排序序列的有序状态为逆序

2.处于逆序状态的前提是本身有序！！

1.对于冒泡排序，每一趟排序都能够使得当前无序序列中的最大值被交换到序列的最后面（很容易证明，且在序为从小到大排的前提下）

2.当有n个元素需要排序的话，我们需要进行 n -1趟冒泡排序，每进行一次都能使得有序序列中增加一个有序元素

3.设当前比较趟数为m，则这一趟需要的最小比较次数 = n - m （n是待排序的元素总数）

1.使用冒泡排序算法时，我们创建的存储元素的有序表的大小可以为 n +1即要存储的元素总个数 + 1，这样的好处是我们可以将下标为0的位置设置为一个哨兵岗，在冒泡排序交换元素的时候，将被交换的元素临时存在哨兵岗，同时我们可以从下标为1的位置开始存储元素，存够n个元素刚好到下标为n的位置，这样子更方便我们对元素进行操作和读取，

1.如果某一趟冒泡排序在比较完后，元素的交换次数为0的话（即没有fa's） --- 则只有一种可能能够解释这种情况，那就是这一趟冒泡排序排的序列已经是有序的了，不需要交换元素

2.设n个元素进行了m 趟冒泡排序，此时n个元素从后往前数m个得到的这一段都是我们排好的有序序列，而从前往后数n - m个都是没有排好的无序元素（假定）

此时进行 m +1 趟冒泡排序，如果这一趟冒泡排序的元素交换次数为0（即没有发生交换的话），则表示从前往后数到 n - m -1这一段假定无序序列本身是有序的，不需要再进行排序，则我们此时可以停止冒泡排序了。

 

1.关于移动次数那里，我们每一次交换元素都进行了三次移动，假设A和B进行交换：

第一次移动：将B移动到临时储存处；第二次移动：将A移动到B位置；第三次移动：将B从临时储存处移动到A位置。完成了三次移动之后我们才完成了交换

---

第二部分 --- 交换排序 之 快速排序

 

1.快速排序一般都以第一个元素作为中间元素（也可以是最后一个元素或者任意一个元素）（中间元素的左右子表也一样，都是以第一个元素作为中间元素），当子表中只剩下一个元素时），就停止快速排序

 

1.目的：将比界点大的元素搬到界点的前面，比界点小的元素搬到界点的后面

1.使用 low ，high交替搬运法 --- 选中第一个元素作为中间元素，并用low指针指向第一个元素，high指针指向最后一个元素。

2.先将选中的中间元素搬运到界点处，此时相当于low处为空，我们从high往前找有没有比界点小的元素，有的话就将小的元素搬运到 此时为空的 low 处，搬完后执行第三步

3.搬运完毕后high指向的位置就变为了空，此时我们就从low处往后找有没有比界点大的元素，找到了就往空的high处搬，搬完后如果high指针不等于low指针的话，那就继续执行第二步；如果high指针等于low指针的话，那就将界点搬到 low 和 high 共同指向的位置，然后停止搬运

4.执行完上面三步后我们就对给定的序列完成了一次快速排序

 

1.这一行代码就是在调用函数将给定序列排序为以中间元素（为给定序列的第一个元素）为界点，界点的左边都是大于（小于）界点的元素，右边都是小于（大于）界点的元素的序列，同时将排好序后的序列中的界点的下标返回。

1.上面这个是中间元素的左边大于中间元素，右边小于中间元素

2.函数返回的界点的下标 - 1就是界点左序列的high，+1就是界点有序列的low

3.得到了左序列的high和右序列的low后，分别对左右序列再一次递归调用快速排序

1.只要是用递归实现的算法都需要系统自动调用系统栈来存取递归过程中的数据

2.如果用非递归的方式来实现递归算法的话，也需要我们自己创建栈来存取数据

 

 

1.自然排序就是：待排序序列越有序，排序速度越快

2.非自然排序就是越无序，排序速度越快

---

第三部分 --- 选择排序  --- 简单选择排序

 

1.进行比较，将小的元素的位置进行记录，然后再进行比较，直到找到最小的元素，找到后根据记录的位置进行交换，然后减一个元素，在少一个元素的子序列中继续比较。

1.对于简单选择排序而言，无论待排序序列是有序的还是无序的，我们都会从第一个元素开始，一个元素一个元素依次和没有排好序的元素进行比较

---

第四部分---- 选择排序 --- 堆排序

1.完全二叉树中，设任意结点为第 i 个结点，则这个结点的左孩子是第 2i 个结点，右孩子是第 2i + 1个结点（这个完全二叉树的结点的排序按照从上到下，从左往右，从1开始排序，且在给完全二叉树添加结点的时候，如果有左孩子空着那就优先填加到左孩子处）

1.左边的任意一个结点中存储的元素值都大于它的左右孩子结点中存储的元素值，所以是大根堆，右边则相反，是小根堆

1.将一个堆转化为完全二叉树后，树的根结点就是所有结点中的最大（最小）值 --- 由堆的定义可以推出这个结论

2.将完全二叉树的根结点（最大 / 最小值）输出后，将剩下的元素组成一个新的堆，并再次输出这个堆的根结点，输出之后再重新组成堆，直到所有元素都输出之后，我们就能够得到一个有序序列，结束排序操作

 

1.大根堆的再组成和小根堆的再组成的唯一区别就是：用最后一个元素替代后，原根结点的左右子树进行比较，并将替换元素与比较后的较大者进行交换

1.首先根据序列生成一个完全二叉树，如果树中有一个元素存储的结点位置不对导致完全二叉树局部不符合大根堆的定义（此处以大根堆为例），我们就需要重新调整这个元素的位置，使得局部重新符合大根堆的定义，这个调整位置的过程就称为筛选

2.我们将被调整的元素与它所在的结点的的左右孩子存储的元素之间的较大值进行比较，如果它小于这个较大值的话，我们就要交换被调整元素和较大值元素的存储位置

交换之后，再将被调整结点与它所处的新结点位置处的左右孩子存储的元素的较大值进行比较，如果还小就继续交换和比较，如果比较大值大的话，就停止筛选，此时完全二叉树局部符合大根堆的定义。

1.关于我们如何从得到的完全二叉树中的计算出从那个结点开始进行筛查操作前，我们需要知道几个前提：

一.在完全二叉树中，给每个结点按照从左往右，从上到下，从1开始编号，已知孩子结点的编号为n，则其双亲结点的编号K等于 （n / 2）--- 用整数存储--- 如果是左孩子的话有 n = 2k，所以计算没问题，如果是右孩子的话：n = 2k + 1,用2除后得到k + 0.5，由于用整型变量存储数据，所以小数部分的 0.5 被舍去，计算依然没有问题

二.最后一个叶子结点后面没有结点了，与最后一个叶子结点同一层的结点只能是叶子结点，如果不是的话就会导致：我们给定的叶子结点并不是最后一个结点，并且还可能导致树不是完全二叉树

2.综上我们就可以得到结论：最后一个叶子结点的双亲结点就是我们进行筛查的起点，完全二叉树的根结点就是我们进行筛查的终点

首先：由于最后一个结点后面没有叶子结点，所以最后一个叶子结点的双亲结点的后面的结点必然没有叶子结点，然后与最后一个叶子结点同一层的结点均为叶子结点

而叶子结点本身是符合堆的定义的，不需要进行筛查，所以，我们筛查的起点就是最后一个叶子结点的双亲结点

1.当一个完全二叉树中的所有结点都符合相同的堆的定义的时候，这个完全二叉树就符合对应的堆的定义了，如果有一个结点不符合的话，这个完全二叉树就不符合堆的定义

如果想要符合的话，我们就需要对这个结点进行筛选操作，使得这个结点符合对应堆的定义