信息学奥赛初赛――排序 －1 － 排序 一、排序的概念 将一组无序的数据元素（或记录）序列，按关键字递减（或递增）的顺序重新排列成一个有序序列的过程称排序。 设有 N个记录的序列｛R1，R1，„，RN｝，其相应的关键字为｛K1，K2，„，KN｝ 确定一种排列 p1,p2,„,pn，使其相应的关键字满足如下的递减（或递增）关系： Kp1≤Kp2≤„≤Kpn 一般排序都是基于数组存储的方式。 排序过程中，若只使用计算机的内存存放待排序的记录，称内部排序。若数据量很大，在排序过程中，记录要在内、外存储器之间移动，称外部排序。 二、插入排序 1、直接插入排序(Insertion Sort) 开始时，认为序列中第一个元素已排好序，将第二个元素与第一个元素进行比较，若顺序不对，则交换这两个元素的位置（否则不交换），这样第二个元素就插入到已排序序列中。依次类推，对第 I个元素排序时，其前面的 I－1个元素已排成有序序列，将第 I个元素依次与前面的 I－1个元素逐一比较，找出一个合适的位置 J（1≤J≤I－1），并将第 J到第 I－1的元素都后移一个位置，将第 I个元素放到第 J个位置上。依次直到 N个元素完成。 例、用直接插入法对下列数据排序：7，5，4，9，1，6，3，2 排序过程如下： 初始序列 [7] 5 4 9 1 6 3 2 第一次排序 [5 7] 4 9 1 6 3 2 第二次排序 [4 5 7] 9 1 6 3 2 第三次排序 [4 5 7 9] 1 6 3 2 第四次排序 [1 4 5 7 9] 6 3 2 第五次排序 [1 4 5 6 7 9] 3 2 第六次排序 [1 3 4 5 6 7 9] 2 第七次排序 [1 2 3 4 5 6 7 9] 算法如下： VOID－InsertSort begin For I:=1 to n do Begin S:=x[I+1]; j:=i; while (j>=0) and (s
