五大排序（一）

排序的功能：用户提出要求，电脑根据用户要求把那些记录排列出来，给用户带来放方便。

排序的基本操作：1、比较关键字的大小；2、将记录从一个位置移动到另一个位置。理解“基本”一词。后面详讲关键字。

内部排序：要排序的数据都在内存中，称为内部排序。五大排序都是内部排序。

外部排序：要排序的数据一部分在内存上，一部分在外存上。需要清楚的时，CPU不能直接访问外存，什么意思呢？也就是说，对外部的数据进行排列的时候，也是先把它们调到内存中，但是，它们的顺序却是整个（包括内存和外存）数据的序列。

五（八）大排序的总纲图：

常见八排序就是五大排序，只不过，有些排序升级了，这种升级针对的是处理不同情况的升级，并不是之前的版本不如升级版（看情况）。例如：原先一个排序方法，在数据少时，非常的使用，但是，在处理大量数据时就不行了，于是，我们针对这种情况，我们找到一个更好的方法，当然，这种的好只能在处理大量是数据时体现，在处理少量数据时，他就不如之前的方法好。

1、直接插入排序

待排序的数据，我们把它分成两类，一类是按要求拍好了的，一类没有排好；初始排好类中只有一个数据，然后，我们按一定的次序从没有排好的类中拿出一个数据，让这个数据和排好类中的数据比较大小，找到合适的位置后，就进行位置的改变；依次类推，知道没排好的类中没有数据为止。

2、希尔排序

你想一下，一组从小到大排好的数据，你再用直接插入排序把它从大到小的排一次，是十分的麻烦：每排一个数据，这个数据就会插入在排好类中的最头，那么之前排好类中的数据就要都移动（或采取别的麻烦的方法来达到效果）；希尔排序就很好的解决了这种麻烦，希尔排序的就是先把一定间隔的数据组成一组，这样把所有数据组成了多组，然后在这一组中采用直接插入排序方法排序，每组内排好后，再把一定间隔的数据组成一组……注意：一定的间隔的含义是间隔越来越小，直到间隔为1，也就是所有数据组成一组为止，间隔必须为奇数，因为我要保证间隔最后为1。

3、简单选择排序

把要排序的数据分成两类，一类是排好类，另一类是待排类，初始时，我们默认排好类中没有排好的数据，我们从待排类中按一定的顺序选择一个数据，这个数据在待排类中是通过比较得出来的，然后把它放入排好类中，再从待排类中选择一个数据，这个数据在待排类中是通过比较得出来的，以此类推，知道待排类中没有数据为止。这个和直接插入法的区别是：直接插入法，从待排类中选择的数据，没有在待排类中比较，而是，让他和排好类中的数据进行比较；简单选择排序，从待排类中选择的数据，是经过在待排类中比较得来的，不用再在排好类中比较了。

4、堆排序

中心思想：我们把存放在内存中数据，把数据形成完全二叉树的形式，这个完全二叉树的特点：双亲大于孩子（大顶堆）或孩子大于双亲（小顶堆），递归思想的定义。然后，我们把根和最后（根中序号最大）的一个结点进行交换，并且把除最后的那个结点外的所有结点在排成一个堆，然后，再交换，以此类推。代码的实现思想：建立符合要求的完全二叉树，然后，交换结点，再建立符合要求的完全二叉树。代码的实现采用了递归的思想，所以，一定要找到规律。

下接：五大排序（二）