第9章排序 91概述 1、排序 ●排序是计算机程序设计中的一种重要操作,它的功能是将一个 数据元素(或记录)的任意序列,重新排列成一个按关键字有 序序列。 ●假设含n个记录的序列为:·其相应的关键字序列为 ●{R1,R2,……,Rn}(9.1) {K1,K 2 njs 需确定1,2,…,n的一种排列P1,P2,…,Pn,使其相 应的关键字满足如下的非递减(或非递增)关系 Kp1≤Kp2≤…Kpn,即使(91)式的序列成为一个按关键字 有序的序列{Rp1,Rp2,……,Rpn},这样一种操作称为排序。 北京邮电大学自动化学院北京邮电大学自动化学院 1 第9章 排序 ⚫ 9.1 概述 ⚫ 1、排序 ⚫ 排序是计算机程序设计中的一种重要操作，它的功能是将一个 数据元素（或记录）的任意序列，重新排列成一个按关键字有 序序列。 ⚫ 其相应的关键字序列为 ⚫ {K1，K2，……，K n }， ⚫ 假设含n个记录的序列为： ⚫ {R1，R2，……，R n } (9.1） ⚫ 需确定1，2，……， n的一种排列P1，P2，……，P n，使其相 应的关键字满足如下的非递减（或非递增）关系 KP1KP2……KP n，即使（9.1）式的序列成为一个按关键字 有序的序列{RP1，RP2，……，RPn}，这样一种操作称为排序