内排序 笔记

内排序：指在排序期间数据对象全部存放在内存的排序。

外排序：指在排序期间全部对象太多，不能同时存放在内存中，必须根据排序过程的要求，不断在内，外存间移动的排序。

根据排序元素所在位置的不同,排序分: 内排序和外排序。

内排序：在排序过程中，所有元素调到内存中进行的排序，称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。按所用策略不同，内排序又可分为插入排序、选择排序、交换排序、归并排序及基数排序等几大类。

外排序：在数据量大的情况下，只能分块排序，但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率

 排序，就是对一个序列中的记录来进行的一种操作。

序列：我们前面介绍过的线性表。

而表中的元素呢，在我们这里称为记录。它是排序的基本单位。

在排序问题中，我们很多情况下是针对那种能够唯一标示这个记录的关键码来进行的。但是在有一些情况下，我们可能是要对若干个域，或者是说有重复的这些域，来进行排序。

啊例如，我们对姓名来排序的话，可能就有重名的情况。那我们的排序问题呢，就是根据这个排序码，我们来对这个序列，进行操作，然后形成一个不降的这么一个序列，或者是一个不增的一个序列。整个排序我们如果是规模比较小的情况下，我们可以认为是在内存完成的。

 因为它是线性表，所以我们可以看作是在数组里面来进行的。特别是我们的输入是放在数组里面，输出也放在数组里面。

排序的稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

进行严格的形式证明

排序算法衡量标准

时间：记录的比较和移动次数

空间：主要是指我们为了完成这个排序方法，所需要的辅助空间。例如，如果我们要对n个元素的数组进行排序。那如果我需要给出一个，同样具有n个这样的元素大小的辅助空间，那它就是O n的一个空间代价。那如果我只需要用到一个临时变量来临时的存放这个大排数组里面的某一个记录，那它就是O 1的空间。 另外还要考虑，算法本身的繁杂程度。因为排序是在计算机里面反复使用的这么一个基础算法。那也就是说，算法本身它是不是易于编写，是不是可读，可维护等等，也是非常重要的。

插入排序 ：直接插入和shell 希尔排序 n的平方 基本有序的情况下，最有利

延伸 shell 排序 二分法 增量为数组长度的一半，进行排序，时间复杂度越来越接近于n

算法改进 采用除以3的增量，2的k次方减1，达到n的1.5次方

2的p次方乘上3的q次方 可以达到n*log（2）n

选择排序 ：直接选择排序 堆排序

直接选择排序：不稳定 n的平方

算法的稳定性定义为,对于待排序列中相同项的原来次序不能被算法改变则称该算法稳定.

比如待排序列为:(2) 3 6 [2] 4 5 ,,,序列中的(2)排在[2]前面,不能因为算法把[2]排到(2)前面.

直接选择排序算法,不稳定性,举个简单的例子,就知道它是否稳定..例如:(7) 2 5 9 3 4 [7] 1...当我们利用直接选择排序算法进行排序时候,(7)和1调换,(7)就跑到了[7]的后面了,原来的次序改变了,这样就不稳定了.

堆排序

 堆排序呢，它的建堆过程是θ（n）的。那我们删除堆顶呢，如果堆里面有n个元素，它就是logn的。如果是i个元素呢，应该是logi的。 那我们整个这个排序的过程是一次建堆，然后有啊n-1次删除堆顶的操作。那我们总的时间代价呢是n logn的。空间代价主要是用在我们进行这个元素的交换或者是移动的时候，那种辅助的空间。那这个辅助空间的代价是θ（1）的。

交换排序：冒泡排序和快速排序

冒泡 n的平方 空间n

快速排序，中值，递归

基于分治法：快速和归并

n*log n  log n

算法优化方案：轴值的选择，消除递归，用栈和队列

分配和基数排序