排序算法 冒泡 选择 插入 堆 归并 快速 图解 记录
排序算法
一些算法记录
复杂度 和时间度这种衡量，只能说适用的场景不同，没有优劣之分
最好自己动手手动排一下。
不想排的话，推荐 ==算法动画图解== 这个app 就是收费而已
冒泡排序``
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| 5 | 9 | 3 | 1 | 2 | 8 | 4 | 7 | 6 |
将天平放在 右端， 比较7 和6，
7大于6 ，交换 。小于等于不交换。
交换后，移动天平，前进1格。
1 2 3 4 5 6 7 8 9 5 9 3 1 2 8 4 6 7 4 和6比 。不交换
一直到最左端 两个比较。完成后，最小的被移到最左端了。标志 一号位置为已排序.
1 2 3 4 5 6 7 8 9 15 9 3 2 4 8 6 7 重复同样的操作 。与上次不同的是 不需要再到一号位置停止了，因为一号位置是最小的了。所以到二号位置停止。
依次停止，最后一定是只比较8和9号位置。
完成
选择性排序
线性搜索 数列找到最小值，==交换==，放到最左端，如果已经在最左，则无操作。
1 2 3 4 5 6 7 8 9 1 8 重复操作，搜索==剩下的== 。从剩下的开始搜索。如 第二次时，剩下最小放到第二号位置。
完成。
插入排序
首先，1号位置 当作已排序，取出尚未操作的左端数字。与已操作的数字进行比较。如 5 3 比较
1 2 3 4 5 6 7 8 9 5 4 7 2 8 6 9 1 3 5 3 比较，交换
1 2 3 4 5 6 7 8 9 3 5 4 7 2 8 6 9 1 然后选出三号位置的4 与 3 5两个（前面） 比较。 ==插在前面比4小，后面比4大的地方== ，==一位一位的与前面比==， 也就是3 和5 之间，5向后移一位
1 2 3 4 5 6 7 8 9 3 4 5 7 2 8 6 9 1 重复 插入比较动作，剩下已排序 元素右移一个单位，因为，你插入到队伍中，肯定要有人腾出位置，后面的人跟着腾出位置，直到你原来的位置。也就是只有已排序的移动 而已。
重复动作。 直到最后一个元素9号位置的元素被操作了，就完成 了。
堆排序
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| 5 | 2 | 7 | 3 | 6 | 1 | 4 |
堆是一种结构。像树。
首先 。得先数字==存储到堆里==，按==降序==构建堆。？？？
降堆是：父结点比子结点大。左孩子比右孩子大。
依次从数列中取出，作为新的子结点，先==左孩子再右孩子==，然后==与父结点比较，一直没有父结点大于它 ，停止。== 总之， 大的往上移动。
一棵二叉树
堆
降堆 好处是 ，取出数据时 按从大到小取出，取出来 相反排序就相当于是完成 了排序 。
只需要取出根结点。取出的时候，叶子结点的右孩子（没有就取左），填到根结点上，然后与 自己（根）的==孩子结点==比，大的则交换，一直交换到没有比它大的。这样保证每次取出来的都是根结点是最大的，而且有序的。其实堆是也用数列来储存的
| A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|
| 7 | 6 | 5 | 2 | 3 | 1 | 4 |
对应起来就是这个样子
最大的肯定是A， A与G 比 ，G是数列最后一个元素。交换。
这样，A 是4 ，G 是7 。然后，重新构建堆。保持降序的结构。
然后还是 A 与==G-1==(因为G和后面的排好了)也就是A 位置与 F位置交换。再重新构建堆
重复步骤。完成
注意是 从数列的角度来取的。而不是堆视图，乱 。取出后，可以去除堆视图中相应的元素，以便学习观察。或者数列中标灰。
归并排序
首先将数列分两半，分到第三层
怎么有点像二叉树从最底层开始。两个两个比 ，比完交换完，移动到上一层。
当图形内一个组 多于一个数字时，比较这两个组 里分别开头的数字。 4 和3 比，大的就先往上层移，排在开头。所以是选3 再 4 。剩下的依次对比。6 和7 比。
递归地重复合并操作。直到所有的数字在同一个组中。
关键点：分成了两个，一层层上来，只需要对比对应位置的就行了。
归并
快速排序
交换次数少。某些情况下。，
第一个操作对象 是 数列中所有 的数字，随机选择一个数字作为pivot .
为了方便，取 最右边 。
A B C D E F G H J 3 5 8 1 2 9 4 7 6 L R P 最左标记为L ,最右为R
原理：使用标记递归重复操作。
L 向右前进，当对位置的数字==大于==p位置的数字时，停止移动 。
如到8 。然后，R 向左移，一直到==小于==p的数字停止。如到4
然后==交换L和R位置的数字==
A B C D E F G H J 3 5 4 1 2 9 8 7 6 L R P 如此 ，L 继续移动 ，到9 时，停止，轮到R移动了，R 移动到F位置，也就是9 。L与R 在同一个位置了，所以R 只能停止，然后LR位置 与P交换。
A B C D E F G H J 3 5 4 1 2 ==6== 8 7 ==9== LR P LR相遇，算完成一次排序。这样下来，左则收集的数字小于F位置，右则的数字大于F位置，即小于6 大于 6
因此，下一次排序不需要 整个数列了，排的是 ==A到E位置==的数字，
在程序上，这种操作可以用递归来实现。一种子集关系嘛，
对子集进行 重复上面 一 二步骤操作。：建立L R P
A B C D E F G H J 3 5 4 1 2 6 8 7 9 L R P 一直到 建立LRP时，发现只有一个数字，则算是到底了。
A B C D E F G H J 1 5 4 3 2 6 8 7 9 LR P
如左边子集只剩1了，分配LR时 L等于R了，所到底了，
关键在于 ：递归子集，
==主要是记录一下，还是找相关书看一下好。==
