一、概论
对于数据的处理工作，排序是其最基本的运算之一。在当今的计算机系统中，花费在排序
上的时间占系统CPU运行时间的很大比重。有资料表明，在一些商用计算机上，在排序上
的CPU时间达到20％至60％。为了提高计算机的工作效率，人们提出了各种各样的排序
方法和算法。这些算法有力地发展、并充分地展示了算法设计的某些重要原则和高超技巧
。因此，对于计算专业人员来说掌握排序算法是十分重要的。
二、排序算法简介
本次课程中我们将介绍六种排序方法：插入排序，选择排序，冒泡排序，希尔排序，快速
排序及二路归并。
<1>直接选择排序(Selection Sort) ：简单的选择排序，它的比较次数一定：n(n-1)/2
。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数据可
以发现它耗时相差不多，相差的只是数据移动时间），可见对数据的有序性不敏感。它虽
然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排
序。
<2>直接插入排序(Insertion Sort) ：简单的插入排序，每次比较后最多移掉一个逆
序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进
行值交换，而在插入排序下是值移动，所以直接插入排序将要优于冒泡排序。直接插入法
也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在
最坏情况下，将需要n(n-1)/2次比较。
<3>冒泡排序(Bubble Sort) ：将相邻的两个数据元素按关键字进行比较，如果反序，
则交换。对于一个待排序的数据元素序列，经一趟排序后最大值数据元素移到最大位置，
其它值较大的数据元素向也最终位置移动，此过程为一次起泡。然后对下面的记录重复上
述过程直到过程中没有交换为止，则已完成对记录的排序。
<4>快速排序(Quick Sort) ：是冒泡排序的改进，它通过一次交换能消除多个逆序，
这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下，它的排序时间复杂度
为Ｏ(nlog2n)。即每次划分序列时，能均匀分成两个子串。但最差情况下它的时间复杂度
将是Ｏ(n^2)。即每次划分子串时，一串为空，另一串为m-1 （程序中的100K正序和逆序
就正是这样，如果程序中采用每次取序列中部数据作为划分点，那将在正序和逆时达到最
优）。从100K中正序的结果上看“快速排序”会比“冒泡排序”更慢，这主要是“冒泡排序”中
采用了提前结束排序的方法。有的书上这解释“快速排序” ，在理论上讲，如果每次能均匀
划分序列，它将是最快的排序算法，因此称它作快速排序。虽然很难均匀划分序列，但就
平均性能而言，它仍是基于关键字比较的内部排序算法中速度最快者。
<5>希尔排序(Shell Sort) ：增量的选择将影响希尔排序的效率。但是无论怎样选择增
量，最后一定要使增量为１，进行一次直接插入排序。但它相对于直接插入排序，由于在
子表中每进行一次比较，就可能移去整个经性表中的多个逆序，从而改善了整个排序性能
。希尔排序算是一种基于插入排序的算法，所以对数据有序敏感。
<6>归并排序(Merge Sort) ：归并排序是一种非就地排序，将需要与待排序序列一样
多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论
是在最好情况下还是在最坏情况下均是O(nlog2n) 。对数据的有序性不敏感。若数据节点
数据量大，那将不适合。但可改造成索引操作，效果将非常出色。
三、排序方法的选择
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要
(1)若n较小，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数；
但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排
序。
这两种都是稳定排序算法。
(2)若文件初始状态基本有序(指正序) ，则应选用直接插人、冒泡或随机的快速排序为宜(
这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定
。
(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并
排序序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分
布时，快速排序的平均时间最短；
堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是
不稳定的。
归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组
合，先获得一定长度的序列，然后再合并，在效率上将有所提高。
(4)特殊的箱排序、基数排序
它们都是一种稳定的排序算法，但有一定的局限性：
1>关键字可分解。
2>记录的关键字位数较少，如果密集更好
3>如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排
序。
四、AS中排列数组
1.申请一个长度为n的数组A ：
var n:Number = 400;
var A:Array = new Array(n);
for (i=0; i < n; i++) {
A[i] = i;
}
trace(A);
2.将长度为n的数组打乱次序：
for (i=0; i < n; i++) {
var ran = int(Math.random()*n);
var temp = A[i];
A[i] = A[ran];
A[ran] = temp;
}
trace(A)
3.将数组中的所有元素倒排序：
A.reverse();
trace(A)
五、AS实现排序算法：
在执行各各排序算法之前，已经默认存在一个乱序的数组 A[400] ，默认代码：
var n:Number = 400;
var A:Array = new Array(n);
for (i=0; i < n; i++) {
A[i] = i;
}
for (i=0; i < n; i++) {
var ran = int(Math.random()*n);
var temp = A[i];
A[i] = A[ran];
A[ran] = temp;
}
1.直接插入排序
for (i = 0; i < n; i++) {
var temp = A[i];
for (j = i; j > 0 && temp < A[j - 1]; j--) {
A[j] = A[j - 1];
A[j - 1] = temp;
}
}
2.直接选择排序
for (i = 0; i < n - 1; i++) {
var s:Number = i;
for (j = s + 1; j < n; j++) {
if (A[j] < A[s]) {
s = j;
}
}
var temp = A[i];
A[i] = A[s];
A[s] = temp;
}
3.冒泡排序
for (i = 0; i < n; i++) {
for (j = i; j < n; j++) {
if (A[i] > A[j]) {
var temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
4.希尔排序
var increment = 6;
while (increment > 1) {
increment = int(increment / 3 + 1);
Shellpass(increment);
}
function Shellpass(c) {
for (i = c; i < n; i++) {
if (A[i] < A[i - c]) {
var temp = A[i];
j = i - c;
do {
A[j + c] = A[j];
j = j - c;
} while (j > 0 && temp < A[j]);
A[j + c] = temp;
}
}
}
5.快速排序
function QuickSort(A, low, hig) {
var i = low, j = hig;
var mid = A[int((low + hig) / 2)];
do {
while (A[i] < mid) {
i++;
}
while (A[j] > mid) {
j--;
}
if (i <= j) {
var temp = A[i];
A[i] = A[j];
A[j] = temp;
i++;
j--;
}
} while (i <= j);
if (low < j) {
arguments.callee(A,low,j);
}
if (i < hig) {
arguments.callee(A,i,hig);
}
}
QuickSort(A,0,n - 1);
6.二路归并
var B:Array = new Array(A.length);
for (k = 1; k < n; k *= 2) {
MergePass(k);
}
function MergePass(len) {
for (i = 0; i + 2 * len < n; i = i + 2 * len) {
MergeA(i,i + len - 1,i + 2 * len - 1);
}
if (i + len < n) {
MergeA(i,i + len - 1,n - 1);
}
}
function MergeA(low, m, hig) {
var i = low, j = m + 1, z = 0;
while (i <= m && j <= hig) {
B[z++] = (A[i] <= A[j]) ? A[i++] : A[j++];
}
while (i <= m) {
B[z++] = A[i++];
}
while (j <= hig) {
B[z++] = A[j++];
}
for (z = 0, i = low; i <= hig; z++, i++) {
A[i] = B[z];
}
}
posted on 2009-06-14 01:21
noyear 阅读(54)
评论(0) 编辑 收藏 引用