直接插入排序、希尔排序 与 简单选择排序、堆排序 | 排序(一)
本章会分两篇文章讲解常见的8种排序方法,可以点个关注、加个收藏,进个人空间继续看下一部分的内容哦!后期会在这篇文章开头加上第二部分的链接。
排序
概念分类:
稳定排序 与 不稳定排序
- 指 一个序列中,有两个键值一样的元素AB。假设A排在B前,经过稳定排序后,A仍然在B前面。而不稳定排序可能会改变AB的前后顺序。
内排序 与 外排序
- 内排序指在本身序列上排序,需要的辅助空间为O(1);外排序则需要更多的辅助空间。
方法分类:
插入类排序:
- 直接插入排序
- 希尔排序
选择类排序
- 简单选择排序
- 堆排序
交换类排序
- 冒泡排序
- 快速排序
其他类排序
- 归并排序
- 基数排序
直接插入排序
思想:
- 创建一个新容器,用来存放排好序的序列。
- 每取一个元素插入该容器中,就要使容器里的序列仍然有序。
插入规则:
假设要插入A元素
- 容器里没有元素,直接插入。
- 容器中有元素,则从序列中第一个元素开始遍历。
- 如存在第一个比A大的元素B,则把A插入到B的前一位。插入方法:把从B开始的元素依次往后挪一位(从序列最末端开始移),把A放在B原来的位置上。
- 如不存在比A大的元素,则把A插入在序列的最末端。
希尔排序
思想:
- 直接插入排序中,如果待插入元素的初始位置与排好序后的位置相差较大,则会出现位置挪动次数较多,耗时较长。如 把 2 插入到 1 2 3 5 6 4 7 8 9 中,需要把 3 5 6 4 7 8 9都挪动一下位置。
- 多次分不同的组进行直接插入排序。每次分组的元素相差距离由大到小,可以保持每组内的直接插入排序效率不低。
插入规则:
如待排序的序列长度为n。
序列为{57,68,59,52,72,28,96,33,24,19},n = 10.
- 取一个小于 n 的整数 d1,作为第一次分组中,每隔d1距离的元素为一组。每组组内进行直接插入排序(组内元素在整个序列的位置相对不变)。
假设取d1为 n/2 = 5。
则{57,68,59,52,72,28,96,33,24,19}
57 与 28为一组
68 与 96为一组
52 与 33为一组
72 与 19为一组
每组组内排序完后
{28,68,33,24,19,57,96,59,52,72}
2.再取一个比d1小的整数d2,作为第二次分组中,每隔d2距离的元素为一组。每组组内进行直接插入排序。
假设取 d2 = d1 / 2 = 2
则{28,68,33,24,19,57,96,59,52,72}
28、33、19、96、52为一组
68、24、57、59、72为一组
组内排序完后
{19,24,28,57,33,59,52,68,96,72}
3.再取一个比d2小的整数d3,作为第二次分组中,每隔d3距离的元素为一组。每组组内进行直接插入排序
假设取d3 = d2 / 2 = 1
当d == 1时就是直接插入排序了,但此时的直接插入排序效率不低。
所以规则是从比n小的数开始取d,一直取到d == 1,进行分组的直接插入排序。
直接选择排序
思想:
- 非常暴力,容易想到。
- 既然要排序,那每次选出一个最小的放在序列的开头就可以了。
- 即,在 n个元素的序列中,遍历一遍选出最小的与第一个位置的元素交换。
- 然后除去第一个位置,在n - 1个元素的序列中,选出最小的与该序列的第一个位置的元素交换。
一直到只剩下最后一个元素。
堆排序
堆的概念:
如果你看过这篇文章二叉树。
那么你就会知道,在完全二叉树中,编号为 i 的结点的左儿子编号是2*i,右儿子编号是2*i + 1。
如果把一个待排序的序列,按照编号按层次遍历组成完全二叉树。
当满足下面其中一个关系时,这棵树 就称为 堆 。
- 父结点的值 < 左儿子的值 &&** 父结点的值 < 右儿子**的值, 称为 小顶堆
-
父结点的值 >** 左儿子**的值 && 父结点的值 > 右儿子的值, 称为 大顶堆
即:大顶堆中,父亲大于所有儿子。小顶堆中父亲小于所有儿子。
看到这如果觉得有些眼熟的,可以拿 堆的定义 与 查找二叉树 进行比较(点这里复习查找二叉树)。
堆排序的思想:
根据堆的性质(根结点要么是最大要么是最小的),来不断取走根,并对剩下的元素维护成堆。
在堆中,除了初建堆的成本多一点外,每次取走根后进行的维护成本低。
堆排序的步骤:
- 把序列建立大顶堆(从小到大排序为建立小顶堆,从大到小为大顶堆)
- 把根取走,作为排好序后的第一个元素。剩下元素进行 **堆的维护 **。
- 再把根取走,作为排好序后的第二个元素。剩下元素进行 **堆的维护 **。
- 反复此步骤,直到堆的元素全部取完。
从上面可以看出,对于堆来说,
最重要的一点!!!!—— 初建堆(堆的维护)
初建堆:实际上是把一个序列建立完全二叉树, 再进行堆的维护。
堆的维护:
如序列:{1,3,4,5,72,6,8,0},我们要建立大顶堆。
先建立二叉树:
从编号最大的非叶子结点开始调整(结点 : 5)
- 如果当前它比左右孩子都大,则不动。(如果是建立小顶堆,则是判断是否更小)
- 如果有孩子比它大,那么把最大的孩子与它交换,如果还有孩子比它大,则继续,直到它比左右孩子都大(或者成为叶子结点)。
如结点5与8结点交换。
再从编号第二大的非叶子结点开始调整(结点:4)
一直到根结点。
当根被取走后,如何维护堆呢?
当根被取走后,把编号最大的结点放在根的位置(是叶子结点),然后,直接对这个结点(现在是根结点了)进行堆的调整。因为除了该结点外的其他结点都满足堆的性质。