排序——排序的基本概念

一、排序概念

排序是将一组数据按递增或递减的顺序排列。排序是最一种最基础的、最常用的算法。

二、排序的分类

在计算机中，由于数据形式、数量和保存形式不同，对数据进行排序的方法也不同。按照排序过程中数据保存形式的不同，可以分外内部排序和外部排序

1、内部排序

整个排序过程不需要访问外存便能完成，则称为内部排序，内部排序的过程是一个逐步扩大记录的有序序长度的过程。

2、外部排序

使用内部排序时，所有待处理的数据都已调入到计算机内存中，在排序操作时可以直接访问使用。但是计算机内存容量有限，当大批量的数据进行排序时，不 可能一次将数据全部装入内存，即待排序的数据记录存储在外存中（如硬盘，磁带，闪存等）。这时，可以从外存中读取一部分数据到内存，排序完成后，再存储到 外存中，然后再从外存中读取下一部分数据到内存中进行处理。这样将待排序数据在内存和外存之间进行多次数据交换，达到排序整个数据的目的就是”外部排序 “。

 

注意：外部排序最常用的算法时多路并归排序，即将源文件分解成能够一次性装入内存的部分，分别将每一部分调入内存完成排序。然后对已经排序的子文件进行并归排序。

 

http://my.oschina.net/u/2294938/blog/686225