文档介绍：维普资讯
韫. 成都科技大学学报总羹峙
娅.
占一口
排序研究及其在水利水电工程中的应用
摘要本文研究了安数序列‘讣的有序段曲分布规律,提出了分鄹适用于单牟碱
排序和矩阵排序的高速稳定的研殷聚台洼稻两殷聚合矩阵排序怯. 理论分析和实际运
行结果表明:
们在电力系统负荷舒析和可靠牲舒析中的初步盥用效果都很好.
关键词:生单序排序;矩阵排序水电工:
前言
,其中数快
速排序法的平均排序速度最快. 约为堆排序法等的两倍。但是, 在最坏情况下的运行时
间却为≈。最近. 一些排序方法大大提高了初始序列有序性强的排序速度.
但对有序性差的初始序列排序递度反面比快速排序法有所下降”。现有的矩薄排序
,运行时阊为
本文提出了分别适用于单序列排序和矩阵排序的离速、稳定的两段聚合法和两段聚
合矩阵排序法。两段聚合法的基本工作量:最小为≈一平均为.—.。
.
, 最大为≈十.。
.翮。两段聚合矩阵排序法的基本工作基: 最小为一, ¨一.“
.:
. 最大为十. 所需内存.。它们在水利水电工程中的应用
效果很好。
实数序列的局部有序性研究
任何一个实数序列Ⅱ都会出现局部上升或局部下降的情况。着以单调上升斌
单调下降的分段规则划分“, Ⅲ得到的有序段有如下两个重要特性
.Ⅱ的鳇数最小为最多为,平均为/;.段中元素个数最少为,
均为。为了更充分地利用序列的局部有序性. 本文将以单调上升和单调下降的联合分
段规则划分Ⅱ. 可以证明略以下有序段定理和推论:
定理: 设Ⅱ。的任一元素Ⅱ· : ⋯, 取任意一个实数的概率相同
, 为
车文日
车扳皲碗士研究生
维普资讯
。.的有序段数为的事件数, 为Ⅱ共有段且最后一个有序段只有一个元
素韵事件数, 则。.的有序段数为的概率为;
”/
其中”为偶数时, , ⋯, ./; ”为奇数时, , ⋯, ”/;

·
”一, ≥
”一一/ , ≥
一

”, ≥
一十一.
推论: 的有序段段数的数学期望值为:
, 咖,
‘一
且·÷÷
式中丑· ——表示将括号内的数取整数。
、推论: 的最后一个有序段只有一个元素的概率为

十一一’”. .

,

、

且÷
实际上, 即使”不太大. ”也分别很近似于”/ /
。
分段方法同部有序性利用得更充分
. 段数更少, 排序更省时间。上述结论是分析多队列
快速排序法、两段聚合法和两段聚合矩阵排序法的重要理论依据
。
维普资讯
两段聚合法
. 算法
, 若要由小到大排序则再倒个序。
算法分三步: .扫描; .第一轮两段聚合; .其余各轮两段聚合。.
.
. 扫描
, . : ’
,
对, . ⋯, 做【一
若口≥口. . 则,一. 否