排序算法的性能分析（精选9篇）
排序算法的性能分析 第1篇
排序是计算机科学研究领域的一个基本课题, 是指将无序的数据元素, 通过一定的方法按关键字顺序排列的过程。若整个排序过程不需要访问外存就能完成的排序问题称为内排序, 反之为外排序。内排序的方法繁多, 按所用策略不同, 可分为插入排序、选择排序、交换排序、归并排序和分配排序。 因此, 研究比较各种排序算法的性能可对于实际应用选择起到理论指导的作用。对数据结构中常用的7种 (直接插入、希尔、冒泡、快速、简单选择、 堆和归并) 内排序进行讨论, 介绍了每种排序算法的基本思想, 从时间复杂度、空间复杂度、比较次数、移动次数和稳定性对各种算法进行了分析和比较。 以期为读者在实际应用中提供依据, 结合具体问题设计正确而高效的排序程序。
2 排序算法性能评价的因素
一个问题可用不同的算法解决, 而一个算法性能的优劣将影响解决问题的效率。通常, 评价一个算法性能的好坏主要从时间复杂度和空间复杂度来考虑。对于排序算法, 主要采用插入、交换和选择等方法, 涉及到比较和移动等基本操作, 因此, 评价排序算法, 考虑从各种算法在处理不同规模数据问题时, 所消耗的时间、空间复杂度、比较次数、移动次数以及稳定性等方面来分析。
3 内部排序算法的比较与分析
3.1 基本思想
(1) 直接插入 排序
算法思想: 将一个待排序的记录插入到已排好序的有序表中的适当位置, 从而得到一个新的、记录数增1的有序表。
(2) 希尔排序
算法思想: 希尔排序是对直接插入 排序改进 后提出的 ,又称“缩小增量排序”。先将整个待排记录序列分割成为若干子序列分别进行直接插入排序, 待整个序列中的记录“基本有序”时, 再对全体记录进行一次直接插入排序。
(3) 冒泡排序
算法思想: 对待排序的记录关键字进行两两比较, 若两个记录是反序的, 则进行交换, 直到无反序的记录为止。
(4) 快速排序
算法思想: 是对冒泡排序的一种改进。通过一趟排序将待排记录分割成独立的两部分, 其中一部分记录的关键字均比另一部分记录的关键字小, 则可分别对这两部分记录进行排序, 已达到整个序列有序。
(5) 简单选择排 序
算法思想: 每一趟排序是通过进行n-i次关键字的比较,从n-i+1个待排序记录中选出关键字最小的记录后和第i个记录进行交换, 直到待排序的数据元素有序为止。
(6) 堆排序
算法思想: 堆排序是一种树形选择排序。首先需要将待排序记录按排序关键字建成一个小 (或大) 顶堆, 即子结点的关键字总是小于 (或者大于) 它的父节点。然后输出堆顶的元素, 把剩余n-1个元素的序列重新调整成一个堆, 重复此过程, 直到待排序的数据元素有序为止。
(7) 归并排序
算法思想:“归并”是将两个或两个以上的有序表合并成一个新的有序表。若待排序记录有n个, 则可看成是n个有序的子序列, 每个子序列的长度为1, 然后两两归并, 得到个长度为2或1的有序子序列; 再两两归并, ......, 如此重复, 直至得到一个长度为n的有序序列为止。
3.2 算法比较
表1从理论角度上对常用排序算法进行了比较, 分别给出了不同算法的时间复杂度、空间复杂度、稳定性和复杂性的分析。
3.3 性能分析
使用课题组设计开发的数据结构内部排序算法分析与比较系统对各种不同的排序算法进行了定量的性能分析。考虑从各种排序算法在处理不同规模数据问题时, 所消耗的时间、空间复杂度、比较次数、移动次数以及稳定性等方面来分析。
3.3.1 实验数据
(1) 待排序数据 元素有一个数据 项 , 且为整型 , 由随机数产生器生成。
(2) 考虑到能灵 活有效地 对每种算法 处理大、 中、小型规模数据排序的性能比较, 问题规模n由用户交互输入。
(3) 考虑实验 结果的有效 性 , 课题组采用 多次平行实验测定结果的平均值作为算法分析的依据。
3.3.2 实验结果
为了更好地研究和比较各种排序算法, 分析每种算法的时间复杂度与待排序数据规模的关系, 评估不同算法在处理同一数据问题的效率, 课题组开发设计了基于VC++6.0的内部排序算法的比较与分析系统, 在同样的计算机软硬件环境下, 对给定长度 (100,1000,10000) 的待排序数据进行排序测试, 然后统计每种算法的执行时间, 比较次数、移动次数。
采取了10组不同规模的随机数进行排序实验, 将所统计的每种算法的执行时间、比较次数、移动次数进行平均, 得到更有代表性的实验结果, 如表2 (排序时间单位: 秒) 所示。
3.3.3 结果分析
通过以上实验统计结果, 可以得出以下结论:
(1) 每种算法的执 行时间、比 较次数及 移动次数与 问题规模n有关。当数据规模较小时, 各种排序算法的性能差距不是很显著, 考虑减少移动操作次数, 用简单选择排序较好。但随着排序数据逐渐增长, 算法性能的优劣就明显了, 其中快速排序、堆排序和归并排序性能较优。
(2) 在数据规 模相同的 情况下 , 从平均时 间性能来 看 ,快速排序性能最优, 冒泡排序最差, 其他排序算法都介于之间; 但若待排序数据基本有序时, 快速排序就退化为冒泡排序了。
(3) 就复杂性而言 , 直接插入 排序最简 单 , 当序列中 的记录“基本有序”且排序记录较少时, 它是最佳的排序方法。希尔排序最复杂, 由于比较和移动次数取决于步长因子的选择。
(4) 从稳定性 来比较 , 冒泡排序 、插入排 序和归并 排序是稳定的, 而选择排序、快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。
4 结语
排序算法的性能分析与比较是一个比较复杂的问题, 从空间复杂度、时间复杂度、比较次数、移动次数、 运行时间等方面来看, 没有哪一种是绝对最优的。有的适用于问题规模n较大的情况, 有的适用于n较小的情况。在实际应用中,应根据经验和实际情况合理选择算法, 甚至可以将多种方法融合。
摘要：通过分析直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序等常用的内部排序算法的思想,统计各种算法的时间、空间复杂性、比较次数、移动次数以及稳定性,以期能够掌握这些算法及其特点,在实际应用中能够结合具体问题设计出正确而高效率的数据排序程序。
排序算法的性能分析 第2篇
在IT届有一道百算不厌其烦的题，俗称排序，不管是你参加BAT等高端笔试，亦或是藏匿于街头小巷的草根笔试，都会经常见到这样一道百年难得一解的问题。
今天LZ有幸与各位分享一下算法届的草根明星，排序届的领衔大神——插入排序以及归并排序。最后，在头脑风暴下，LZ又有幸认识了一位新朋友，名叫并行归并排序。接下来，咱们就一一认识一下，并且在最后来一次“算林大会”吧。
插入排序简介
插入排序，算林称最亲民的排序算法，插入排序采用最简单的插入方式对一个整数数组进行排序。它循环数组中从第二个开始的所有元素，并且将每一个循环到的元素插入到相应的位置，从而实现排序的目的。
插入排序的代码展示
使用Java代码描述插入排序，可以用以下的代码。
package algorithm;
/**
* @author zuoxiaolong
*
*/
public abstract class InsertSort {
public static void sort(int[] numbers){
for (int i = 1; i < numbers.length; i++) {
int currentNumber = numbers[i];
int j = i - 1;
while (j >= 0 numbers[j] > currentNumber) {
numbers[j + 1] = numbers[j];
j--;
}
numbers[j + 1] = currentNumber;
}
}
}
复制代码
这个算法从数组的第二个元素开始循环，将选中的元素与之前的元素一一比较，如果选中的元素小于之前的元素，则将之前的元素后移，最后再将选中的元素放在合适的位置。在这个算法执行的过程中，总是保持着索引i之前的数组是升序排列的。
插入排序理解起来比较简单，因此LZ就不过多的解释它的实现原理了，尚未理解的猿友可以自行研究。
插入排序的性能分析
接下来，咱们来简单分析一下插入排序的性能。首先，插入排序当中有两个循环，假设数组的大小为n，则第一个循环是n－1次，第二个while循环在最坏的情况下是1到n－1次。因此插入排序的时间复杂度大约为如下形式。
1+2+3+4+...＋n－1 ＝ n（n－1）/ 2 ＝ O（n2）
时间复杂度为输入规模的2次函数，可见插入排序的时间复杂度是比较高的。这是原理上的简单分析，最后在“算林大会”中，各位可以清楚的看到插入排序随着输入规模的增长，时间会指数倍的上升。
归并排序简介
归并排序，算林届的新秀，引领着分治法的潮流。归并排序将排序问题拆分，比如分成两个较小的数组，然后对拆分后的数组分别进行排序，最后再将排序后的较小数组进行合并。
这种思想是一种算法设计的思想，很多问题都可以采用这种方式解决。映射到编程领域，其实就是递归的思想。因此在归并排序的算法中，将会出现递归调用。
归并排序的代码展示
归并排序主要由两个方法组成，一个是用于合并两个已经排序的数组的方法，一个则是递归方法，用于将问题无限拆分。接下来咱们一起看看归并排序的Java代码展示，如下所示。
package algorithm;
/**
* @author zuoxiaolong
*
*/
public abstract class MergeSort {
public static void sort(int[] numbers){
sort(numbers, 0, numbers.length);
}
public static void sort(int[] numbers,int pos,int end){
if ((end - pos) > 1) {
int ffset = (end + pos) / 2;
sort(numbers, pos, offset);
sort(numbers, offset, end);
merge(numbers, pos, offset, end);
}
}
public static void merge(int[] numbers,int pos,int offset,int end){
int[] array1 = new int[offset - pos];
int[] array2 = new int[end - offset];
System.arraycopy(numbers, pos, array1, 0, array1.length);
System.arraycopy(numbers, offset, array2, 0, array2.length);
for (int i = pos,j=0,k=0; i < end ; i++) {
if (j == array1.length) {
System.arraycopy(array2, k, numbers, i, array2.length - k);
break;
}
if (k == array2.length) {
System.arraycopy(array1, j, numbers, i, array1.length - j);
break;
}
if (array1[j] <= array2[k]) {
numbers[i] = array1[j++];
} else {
numbers[i] = array2[k++];
}
}
}
}
可以看到，归并排序将一个长度为n的数组平均分为两个n/2的数组分别进行处理，因此，在sort方法中又调用了两次sort方法自身。当数组大小为1时，则认为该数组为已经为排好序的数组。因此在sort方法中，需要end与pos相差大于2时，才需要进一步拆分，这也是递归的终止条件。
此外，在代码中，使用了Java提供的arraycory函数进行数组复制，这种直接复制内存区域的方式，将会比循环赋值的方式速度更快。有些算法实现会给merge方法中的两个临时数组设置哨兵，目的是为了防止merge中for循环的前两个if判断。为了方便理解，LZ这里没有设置哨兵，当某一个数组的元素消耗完时，将直接使用arraycopy方法把另外一个数组copy到numbers当中。
归并排序的性能分析
与插入排序一样，咱们来简单分析一下归并排序的时间复杂度。咱们假设数组的大小为n，sort方法的时间复杂度为f（end－pos）。简单的分析merge方法的复杂度，不难发现为（end－pos）＊2，这个结果的前提是咱们认为arraycopy方法的复杂度为length参数。
基于以上的假设，由于end－pos的初始值为n，因此归并排序的复杂度大约为如下形式。
2＊f（n/2） ＋ 2＊n ＝ 2＊（2＊f（n/4）＋2＊（n/2）） ＋ 2＊n＝4＊f（n/4） ＋ 2＊n ＋ 2＊n ＝ n ＊f（1） ＋ 2＊n ＋...＋2＊n
其中f（1）的时间复杂度为常量，假设f（1）＝c，而2＊n将有log2n个。因此咱们得到归并排序的最终时间复杂度为如下形式。
cn ＋ 2n＊log2n ＝ O（n＊log2n）
归并排序的时间复杂度与插入排序相比，已经降低了很多，这一点在数组的输入规模较大时将会非常明显，因为log函数的增加速度将远远低于n的增加速度。
并行归并排序简介
并行归并排序是LZ在学习归并排序时意淫出来的，最近LZ正在研究Java的并发编程，恰好归并排序的子问题有一定的并行度与独立性，因此LZ版的并发归并排序就这样诞生了。事后，LZ也人肉过并行归并排序这个家伙，发现早已众所周知，不过在不知道的情况下自己能够想到是不是也应该窃喜一下呢。
并行归并排序与普通的归并排序没有多大区别，只是利用现在计算机多核的优势，在有可能的情况下，让两个或多个子问题的处理一起进行。这样一来，在效率上，并行归并排序将会比归并排序更胜一筹。
并行归并排序的代码展示
并行归并排序主要对sort方法进行了修改，基础的merge方法与普通的归并排序是一样的。因此在进行并行归并排序时，引用了归并排序的一些方法，具体的代码如下所示。
package algorithm;
import java.util.concurrent.CountDownLatch;
/**
* @author zuoxiaolong
*
*/
public abstract class MergeParallelSort {
private static final int maxAsynDepth = (int)(Math.log(Runtime.getRuntime.availableProcessors())/Math.log(2));
public static void sort(int[] numbers) {
sort(numbers, maxAsynDepth);
}
public static void sort(int[] numbers,Integer asynDepth) {
sortParallel(numbers, 0, numbers.length, asynDepth > maxAsynDepth ? maxAsynDepth : asynDepth, 1);
}
public static void sortParallel(final int[] numbers,final int pos,final int end,final int asynDepth,final int depth){
if ((end - pos) > 1) {
final CountDownLatch mergeSignal = new CountDownLatch(2);
final int ffset = (end + pos) / 2;
Thread thread1 = new SortThread(depth, asynDepth, numbers, mergeSignal, pos, offset);
Thread thread2 = new SortThread(depth, asynDepth, numbers, mergeSignal, offset, end);
thread1.start();
thread2.start();
try {
mergeSignal.await();
} catch (InterruptedException e) {}
MergeSort.merge(numbers, pos, offset, end);
}
}
static class SortThread extends Thread {
private int depth;
private int asynDepth;
private int[] numbers;
private CountDownLatch mergeSignal;
private int pos;
private int end;
/**
* @param depth
* @param asynDepth
* @param numbers
* @param mergeSignal
* @param pos
* @param end
*/
public SortThread(int depth, int asynDepth, int[] numbers, CountDownLatch mergeSignal, int pos, int end) {
super();
this.depth = depth;
this.asynDepth = asynDepth;
this.numbers = numbers;
this.mergeSignal = mergeSignal;
this.pos = pos;
this.end = end;
}
@Override
public void run() {
if (depth < asynDepth) {
sortParallel(numbers,pos,end,asynDepth,(depth + 1));
} else {
MergeSort.sort(numbers, pos, end);
}
mergeSignal.countDown();
}
}
}
在这段代码中，有几点是比较特殊的，LZ简单的说明一下，
1，分解后的问题采用了并行的方式处理，并且咱们设定了一个参数asynDepth去控制并行的深度，通常情况下，深度为(log2CPU核数)即可。
2，当子问题不进行并行处理时，并行归并排序调用了普通归并排序的方法，比如MergeSort.sort和MergeSort.merge。
3，因为合并操作依赖于两个子问题的完成，因此咱们设定了一个合并信号（mergeSignal），当信号发出时，才进行合并操作。
并行归并排序在原理上与普通的归并排序是一样的，只是对于子问题的处理采用了一定程度上的并行，因此如果猿友们理解归并排序，那么并行归并排序并不难理解。
并行归并排序的性能分析
并行归并排序只是将普通归并排序中一些可并行的操作进行了并行处理，因此在总体的时间复杂度上并没有质的变化，都是O（n＊log2n）。
由于并行归并排序将某些排序操作并行操作，因此在性能上一定是快于普通归并排序算法的。不过这也不是一定的，当数组规模太小时，并行带来的性能提高可能会小于线程创建和销毁的开销，此时并行归并排序的性能可能会低于普通归并排序。
算林大会
接下来，就是一周一度的算林大会了，本次算林大会主要由以上三种算法参加，胜者将会成为本周度最受欢迎算法。接下来是算林大会的代码，请各位猿友过目。
package algorithm;
import java.io.File;
import java.lang.reflect.Method;
import java.util.Random;
/**
* @author zuoxiaolong
*
*/
public class SortTests {
public static void main(String[] args) {
testAllSortIsCorrect();
testComputeTime(“MergeParallelSort”, 40000, 5);
testComputeTime(“MergeSort”, 40000, 5);
testComputeTime(“InsertSort”, 400, 5);
}
public static void testAllSortIsCorrect() {
File classpath = new File(SortTests.class.getResource(“”).getFile());
File[] classesFiles = classpath.listFiles();
for (int i = 0; i < classesFiles.length; i++) {
if (classesFiles[i].getName().endsWith(“Sort.class”)) {
System.out.println(“---测试” + classesFiles[i].getName() + “是否有效---”);
testSortIsCorrect(classesFiles[i].getName().split(“.”)[0]);
}
}
}
public static void testSortIsCorrect(String className){
for (int i = 1; i < 50; i++) {
int[] numbers = getRandomIntegerArray(1000 * i);
invoke(numbers, className);
for (int j = 1; j < numbers.length; j++) {
if (numbers[j] < numbers[j-1]) {
throw new RuntimeException(className + “ sort is error because ” + numbers[j] + “<” + numbers[j-1]);
}
}
}
System.out.println(“---” + className + “经测试有效---”);
}
public static void testComputeTime(String className,int initNumber,int times,Object... arguments) {
long[] timeArray = new long[times];
for (int i = initNumber,j = 0; j < times; i = i * 10,j++) {
timeArray[j] = computeTime(i, className, arguments);
}
System.out.print(className + “时间增加比例：”);
for (int i = 1; i < timeArray.length ; i++) {
System.out.print((float)timeArray[i]/timeArray[i - 1]);
if (i < timeArray.length - 1) {
System.out.print(“,”);
}
}
System.out.println();
}
public static long computeTime(int length,String className,Object... arguments){
int[] numbers = getRandomIntegerArray(length);
long start = System.currentTimeMillis();
System.out.print(“开始计算长度为”+numbers.length+“方法为”+className+“参数为[”);
for (int i = 0; i < arguments.length; i++) {
System.out.print(arguments[i]);
if (i < arguments.length - 1) {
System.out.print(“,”);
}
}
System.out.print(“]，时间为”);
invoke(numbers, className, arguments);
long time = System.currentTimeMillis()-start;
System.out.println(time + “ms”);
return time;
}
public static int[] getRandomIntegerArray(int length){
int[] numbers = new int[length];
for (int i = 0; i < numbers.length; i++) {
numbers[i] = new Random().nextInt(length);
}
return numbers;
}
public static void invoke(int[] numbers,String className,Object... arguments){
try {
Class
Class
parameterTypes[0] = int[].class;
for (int i = 0; i < arguments.length; i++) {
parameterTypes[i + 1] = arguments[i].getClass();
}
Method method = clazz.getDeclaredMethod(“sort”, parameterTypes);
Object[] parameters = new Object[parameterTypes.length];
parameters[0] = numbers;
for (int i = 0; i < arguments.length; i++) {
parameters[i + 1] = arguments[i];
}
method.invoke(null, parameters);
} catch (Exception e) {
throw new RuntimeException(e);
}
}
}
以上代码testAllSortIsCorrect方法首先验证了三种算法的正确性，也就是说经过sort方法后，数组是否已经升序排列。需要一提的是，由于插入排序的性能太低，因此插入排序测试的最大规模为400万，而归并排序测试的最大规模为4亿。
接下来，大家就一起看看运行结果吧。以下是在LZ的mac pro上的运行结果，硬件配置为16G内存，4核i7。这种配置下，异步深度（asynDepth）默认为log24=2。
---测试InsertSort.class是否有效---
---InsertSort经测试有效---
---测试MergeParallelSort.class是否有效---
---MergeParallelSort经测试有效---
---测试MergeSort.class是否有效---
---MergeSort经测试有效---
开始计算长度为40000方法为MergeParallelSort参数为[]，时间为6ms
开始计算长度为400000方法为MergeParallelSort参数为[]，时间为44ms
开始计算长度为4000000方法为MergeParallelSort参数为[]，时间为390ms
开始计算长度为40000000方法为MergeParallelSort参数为[]，时间为3872ms
开始计算长度为400000000方法为MergeParallelSort参数为[]，时间为47168ms
MergeParallelSort时间增加比例：7.3333335,8.863636,9.9282055,12.181818
开始计算长度为40000方法为MergeSort参数为[]，时间为7ms
开始计算长度为400000方法为MergeSort参数为[]，时间为81ms
开始计算长度为4000000方法为MergeSort参数为[]，时间为839ms
开始计算长度为40000000方法为MergeSort参数为[]，时间为9517ms
开始计算长度为400000000方法为MergeSort参数为[]，时间为104760ms
MergeSort时间增加比例：11.571428,10.358025,11.343266,11.00767
开始计算长度为400方法为InsertSort参数为[]，时间为0ms
开始计算长度为4000方法为InsertSort参数为[]，时间为3ms
开始计算长度为40000方法为InsertSort参数为[]，时间为245ms
开始计算长度为400000方法为InsertSort参数为[]，时间为23509ms
开始计算长度为4000000方法为InsertSort参数为[]，时间为3309180ms
InsertSort时间增加比例：Infinity,81.666664,95.9551,140.76227
复制代码
首先可以看到，三种算法都是运行正确的。接下来，咱们可以对比一下三种算法的性能。
根据输出结果，规模为400万时的区别是最明显与直观的。并行归并排序仅需要390ms就完成了400万规模的排序，而普通的归并排序则需要839ms才可以，至于插入排序，简直是不可理喻，竟然需要300多万ms，大约50分钟。
咱们再来看三者的时间增长趋势。两种归并排序基本上与规模的增长趋势相似，每当规模增加10倍时，时间也基本上增加10倍，而插入排序则几乎是以100倍的速度在增加，刚好是数组规模增长速度的平方。其中的Infinity是因为当数组规模为400时，毫秒级别的计时为0ms，因此当除数为0时，结果就为Infinity。
基于趣味的改进冒泡排序算法的探讨 第3篇
关键词：冒泡排序；趣味；改进；交换次数；有序表
中图分类号：TP301.6
在众多的排序方法中，冒泡排序算法由于其简洁的思想及其稳定性而得到广泛的应用。本文主要对传统的冒泡排序算法的基本原理进行了介绍和分析，综合趣味和性能两方面提出了改进算法，提高了算法的效率和实用性。
1 传统的冒泡排序算法
以升序排序为例，传统冒泡排序算法的基本思想是，依次比较待排序数据中的两个相邻的数，如逆序，则进行交换，将小的调到前头，直到最后两个数进行过比较为止。上述过程称为第一趟排序，其结果是让最大的数“沉淀”到最后的位置。然后再进行下一趟排序，直至整个数据序列有序为止。由于整个排序过程，总是将较大的数据向下“沉”，而较小的数据向上“浮”，如同水中的气泡逐步冒出水面一样，“冒泡排序”因此得名[1]。如果待排序数据序列中包含n个数据，最终使整个序列有序需要经过n-1趟排序来完成。
2 冒泡排序算法的分析与改进
2.1 从趣味上改进冒泡排序算法
传统的冒泡排序算法很生硬地将一些数据的两两比较提出来，没有给数据赋予具体的情景和角色，人们只能靠反复加强记忆来想象两两比较的过程和数据交换的过程，这样使得冒泡排序很枯燥抽象。目前许多改进的冒泡排序算法都是从算法的性能上进行优化，没有在趣味上进行探索的，这不利于算法的普及和扩展。为了解决这个问题，下面我们针对趣味性方面对传统的冒泡排序算法进行改进。趣味冒泡排序算法的思想是：以升序排序为例，把等待排序的数据列表看成用隔离墙分成有序和无序的两个子表；从远离有序表的一端开始，对无序表中的数据进行两两比较，如逆序，就交换，等所有元素比较完毕，最小的元素就移到了無序表靠隔离墙的那端，然后隔离墙向无序表方向移动一个位置；这样就完成了一趟冒泡排序过程。给定含n个元素的一个表，需要进行n-1趟冒泡排序的过程[2]。图2显示了趣味冒泡排序的原理。图3显示了含5个元素的数组趣味冒泡排序的过程。
2.2 从性能上改进冒泡排序算法
以升序排序为例，传统的冒泡排序算法中，一般是以大数往后沉的方式来实现，很多情况下都有几趟排序是不会有任何的操作，这种做法会出现大量的无效操作，造成资源的浪费。为了避免这种情况，可以使用一个标记变量来解决，即当排序不发生任何数据交换时，则终止排序。这样的解决办法既避免了无效的重复排序，又避免了有限资源的浪费。
在上面趣味冒泡排序算法中，k就是用来标记交换次数的标记变量。这样在趣味冒泡排序算法基础上从性能上改进冒泡排序算法，只需增加一条语句“if（k==0）break；”即可。用C语言描述基于趣味的改进的冒泡排序算法如图5所示。
目前从性能上改进冒泡排序算法，除了增加标记交换次数的变量，还有双向冒泡排序[3]、交替排序法[4]等。这些改进的冒泡排序算法都可以结合趣味性，形成更形象生动、性能更优的算法。
2.3 改进前后冒泡排序算法有限性分析验证
引入10个待排序的数据：1，20，100，-2，15，8，-100，56，43，12，使用传统冒泡排序算法，需要9趟排序才能得到有序的列表，使用趣味冒泡排序算法，需要8趟就能得到有序列表，使用趣味改进的冒泡排序算法仅需要7趟就能得到有序列表。可见本文提出的改进的算法可以提高算法执行效率，是有效的。
3 结束语
本文对传统的冒泡排序算法进行了分析，发现传统的冒泡排序方法可能会产生一些不必要的操作，而且在趣味性方面也欠缺。在此基础上，本文提出了基于趣味的改进冒泡排序算法，提高了算法的执行效率和实用性。
参考文献：
[1]宋美英.基于C语言的冒泡排序算法探讨[J].现代计算机，2011（12）：48-49.
[2]葛日波.C语言程序设计[M].北京：北京邮电大学出版社，2008：126-127.
[3]淦艳等.冒泡排序算法及其改进算法的实验分析[J].重庆三峡学院学报，2011（03）：53-57.
[4]蓝超.冒泡排序算法的优化[J].兵工自动化，2006（25）：50-52.
作者简介：李秋（1979-），女，讲师，硕士，研究方向：计算机网络编程。
选择排序算法的分析与改进 第4篇
关键词：选择排序,双向排序,效率,时间复杂度
1传统的选择排序算法
传统的选择排序算法有两个很好的性质,即:
(1)运行时间对原始输入数据不敏感:每一次选择都是独立的,不受前一次选择的影响也不对后一次的选择提供相关信息。
(2)数据的交换次数是所有排序算法中最小的:传统算法的交换次数是线性的。
1.1传统选择排序思路
以从小到大排序为例:
第一步:在1~n个数中找到最小数,与第1个数交换,前1个数已排好;
……
第k步:在k~n个数中找到最小数,与第k个数交换,前k个数已排好;
第n-1步:在n-1到n个数中找到最小数,然后与第n-1个数交换,排序结束。
1.2算法分析
时间复杂度:通过对上面代码的分析,研究排序的轨迹,可以知道对每一个i从0到n-1,都有1次交换和n-1-i次比较,所以总共有n次交换和(n-1)+(n-2)+(n-3)+…+2+1+0=n(n-1)/2~n2/2次比较,因此时间复杂度为O(n2)。
2改进的选择排序算法
针对传统排序算法中的每一次选择,可以发现每一次选择只能确定一个优先级最高的元素的位置,而实际上在一次选择的循环中,不仅仅可以确定优先级最高的元素位置,同时也可以确定优先级最低的元素位置。
由此可得出改进后的选择排序算法:数组的中间部分为待排序部分,两边均为已排序部分,每一次选择从待排序部分选择优先级最高和最低的两个元素的位置,分别将该两个元素与待排序部分的首部和尾部进行交换(交换的顺序需要特别考虑),由此即实现了双向排序。这样与传统的选择排序相比,比较次数减少了近1/2。
2.1算法思路
第一步:从1~n个数中同时找到最小数和最大数,将它们分别与第1个数和第n个数交换;
……
第k步:从k~n-k+1个数中同时找到最小数和最大数,将它们分别与第k个数和第n-k+1个数交换;
第n/2步:从n/2~(n/2)+1个数中同时找到最小数和最大数,将它们分别与第n/2个数和第(n/2)+1个数交换,排序结束。
例如对实验数据[10 3 4 7 1 2]的排序过程如下:
第一步:1[3472]10:6个数中1最小,10最大,分别与第1个数和第6个数交换。
第二步:1 2[4 3]7 10:4个数中2最小,7最大,分别与第2个数和第5个数交换。
第三步:1 2 3 4 7 10:2个数中3最小,4最大,分别与第3个数和第4个数交换。
2.2算法分析
时间复杂度:从改进后的算法中,仍研究排序的轨迹,可知交换次数没有改变,仍为n,但比较的次数减少了一半,为n(n-1)/4,提高了效率,但是由于在同一个数量级,时间复杂度仍为O(n2)。
3算法之再改进
在算法2的基础上再对算法进行改进:由传统的选择排序算法的两个性质可得,可以对算法进行改进,增强其对原始输入数据敏感性。在最优的情况下,即输入数据有序,选择排序仍需要进行相同数量级的比较,这大大降低了选择排序的效率。再改进的选择排序算法结合冒泡排序的思路,在每一次选择交换之前,对待排序部分进行预判:若待排序部分已有序,则结束排序。
预判操作为:比较前一个元素和后一个元素的优先级,如果待排序部分中前一个元素的优先级均高(低)于后一个元素,则认为待排序部分有序。由此分析可知,改进后的选择排序最优时间复杂度为O(n)。
例如对实验数据[9 3 5 6 8 1]进行排序的过程:
第一步:1[3 5 6 8]9:预判待排序部分为乱序,进行选择排序。6个数中1最小,9最大,分别与第1个数和第6个数交换。
第二步:预判待排序部分为有序,排序结束。
由此可见,再改进的选择排序算法对原始输入数据的敏感性已得到大幅提升。
3.1算法分析
时间复杂度:该算法与改进后的算法相比,最好情况下的时间复杂度为O(n),最坏情况下为O(n2)。
4代码实现
本文中就不再实现传统的选择排序算法代码,以下为再改进后的选择排序算法代码实现:
5三种选择排序的比较
对三种选择排序的时间复杂度进行比较:
(1)传统选择排序:最好情况时间复杂度:O(n2),最坏情况时间复杂度:O(n2)。
(2)改进选择排序:最好情况时间复杂度:O(n2),最坏情况时间复杂度:O(n2)。
(3)再改进选择排序:最好情况时间复杂度:O(n2),最坏情况时间复杂度:O(n)。
6结语
文章采用双向排序的方法对传统的选择排序算法进行了效率上的提高,并且结合冒泡排序的思路,对选择排序的最好的情况下的时间复杂度进行了优化,均c/c++语言实现了上述算法,通过大量的实验数据证明上述算法的正确性和可行性。
参考文献
[1]Robert,S,&Kevin,W(2013),Algorithms[M].北京:人民邮电出版社出版发行,2010.
[2]严蔚敏,陈文博.数据结构及应用算法教程[M].北京:清华大学出版社,2011.
几种排序算法的分析与比较 第5篇
排序是计算机科学、数学、人工智能、日常工作生活、商业服务等领域最常用的一种知识, 一个排序算法 (Sorting algorithm) 是一种能将一串数据依照特定排序方式对它的数据位置进行确定的一种算法。最常用到的排序方式是数值顺序以及字典顺序。由于排序运算的广泛性和重要性, 人们在长期的实践中不断开发出各种各样的排序算法, 它们有着各自的特点、各自的适用范围, 并在各种的应用领域发挥着作用。通过对这些排序算法的基本原理引入, 分别从它们的时间复杂度、空间复杂度和它们的稳定性进行分析和比较, 突出各自的特点, 为选择在不同的领域排序算法的选择提供了的依据, 使开发的程序更加适合实际应用和更好发挥作用。
2、对排序算法分析的理论依据
我们就某一实际问题在选用排序算法来进行解决时, 需要考虑的几个因素一般从以下几个方面综合进行, 排序算法本身的复杂性, 不同算法的时间复杂度、空间复杂度和算法的稳定性四个方面。
不同的排序方法其算法的复杂性也不同, 一般而言, 算法越简单其程序的执行效率也就越低, 算法复杂的排序那么它的执行效率就要高一些。对用户来说, 都希望排序算法的效率要高一些, 而对开发者来说大都喜欢采用比较简单的和运行比较稳定的方法来解决问题。
时间复杂度:算法中基本操作重复执行的次数是问题规模n的某个函数, 用T (n) 表示, 若有某个辅助函数f (n) , 使得当n趋近于无穷大时, T (n) /f (n) 的极限值为不等于零的常数, 则称f (n) 是T (n) 的同数量级函数。记作T (n) =O (f (n) ) , 称O (f (n) ) 为算法的时间复杂度[1]。
空间复杂度与时间复杂度类似, 空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:S (n) =O (f (n) ) 。
排序算法的稳定性:假定在待排序的记录序列中, 存在多个具有相同的关键字的记录, 若经过排序, 这些记录的相对次序保持不变, 即在原序列中, ri=rj, 且ri在rj之前, 而在排序后的序列中, r仍在rj之前, 则称这种排序算法是稳定的;否则称为不稳定的。
3、几种常用的排序算法思想及特点
排序方法为外排序和内排序, 这里分析的是几种常用的内部排序方法。
3.1 冒泡排序:
思想:两两比较相邻待排序数据元素的大小, 发现两个数据元素的次序相反时即进行交换, 每进行一轮比较, 可得出一个最值, 直到所有记录都已排好序为止。
特点:平均时间复杂度为O (n2) ;空间复杂性为O (1) ;稳定性为稳定。
3.2 简单选择排序
思想:与冒泡法相类似, 每一趟在n-i+1 (i=12, …, n-1) 个记录中选取关键字最小的记录作为有序序列列中第i个记录。直到全部待排序的记录排完。
特点:平均时间复杂度为O (n2) ;空间复杂性为O (1) ;稳定性为不稳定。
3.3 堆排序 (Heap Sort)
思想:是指利用堆积树 (堆) 这种数据结构所设计的一种排序算法。堆积树是一个近似完全二叉树的结构, 并同时满足堆积属性:即子结点的键值或索引总是小于 (或者大于) 它的父节点。
特点:平均时间复杂度为O (nlogn) ;空间复杂性为O (1) ;稳定性为不稳定。
3.4 直接插入排序 (Insertion Sort)
思想:将一个记录插入到已排好序的有序表中, 从而得到一个新的、记录数增1的有序表。
特点:平均时间复杂度为O (n2) ;空间复杂性为O (1) ;稳定性为稳定。
3.5 希尔排序
思想:希尔排序 (Shell Sort) 是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序, 因DL.Shell于1959年提出而得名。先将整个待排记录列分割成为若干子序列分别进行直接插入排序, 待整个序列中的记录“基本有序”时, 再对全体记录进行一次直接插入排序。
特点:平均时间复杂度为O (n3/2) ;空间复杂性为O (1) ;稳定性为不稳定。
3.6 快速排序 (Quick Sort)
思想:通过一趟排序将要排序的数据分割成独立的两部分, 其中一部分的所有数据都比另外一部分的所有数据都要小, 然后再按此方法对这两部分数据分别进行快速排序, 整个排序过程可以递归进行, 以此达到整个数据变成有序序列。
特点:平均时间复杂度为O (nlog n) ;空间复杂性为O (log n) ;稳定性为不稳定。
3.7 归并排序
思想:先简单地将待排序序列划分为两个子序列, 然后分别对每个子序列递归排序, 最后将排好的子序列合并。
特点:平均时间复杂度为O (nlog n) ;空间复杂性为O (n) ;稳定性为稳定。
4、各种排序算法的实验时间对照
为了更加直观观察不同算法的时间代价, 本实验设计方法采用C++来实现以上各种算法, 利用随机函数rand () 给数组赋值, rand是一个产生 (0至36635) 范围均匀分布随机数的函数。先调用QueryPerformanceFrequency () 函数获得计算机内部计时器的时钟频率, 接着在执行不同排序算法之前和执行完之后分别调用QueryPerformanceCounter () , 利用两次获得的计数之差和时钟频率, 就可以计算出事件经历的精确时间。事先应保证在同级待排数组中的元素值是相同的, 排序过程中的机器环境不变, 多运行几次取平均值最佳。本程序的测试硬件环境为:CPU为Intel (R) Celeron (R) E3400 2.6GHz, 内存2.0GB DDR3;软件环境为:VC6.0和WinXP。对不同规模的数组在各种排序算法中所进行的时间代价如表1所示, 表1所得数据是在不同算法下相同数组规模的待排数据在程序运行5次所花时间得到的平均值。由于冒泡排序、选择排序和插入排序在大规模数据下花费的时间呈指数级增长, 故在106和107数量级下未进行测验。
通过表1所得的数据进行分析可以得出以下几点:
1) 在待排数据量少的情况下 (数组规模为102以内) , 不同排序算法所花的时间差不多, 没有特别明显的优势。
2) 对于同一种排序算法, 随着待排数据数量的增加, 所花费的时间也相应的增加, 其中前三种每增加一个10倍数据, 所需时间增加102倍数据, 后面四种排序算法每增加一个10倍数据, 所需时间增加也为10倍级数。
3) 随着待排数据的增加, 前三种排序算法速度显得越来越慢, 特别明显, 后面四种算法虽然感觉时间也在增加, 但并不是特别明显。
4) 前三种排序算法的时间复杂度是一个级别的, 后三种排序算法又是另一个级别的。
5、结论
前面通过对各自排序算法的思想、特点及排序过程的理论分析, 结合表1的实验数据, 不难发现, 它们的平均时间复杂度O (nlog n) 要比O (n2) 快, 但是算法本身复杂度相对来说要复杂些, 时间复杂度是考查排序算法性能的一个重要指标, 当然, 在实际生活中, 对于选择哪种排序算法, 我们还要考虑它的空间复杂度和稳定性。一般来说, 我们在选择一种排序算法时应从以下几个方面来进行考虑:
1) 在少规模数 (104以内) 的情况下, 我们一般考虑算法相对较简单的冒泡、选择或插入排序。
2) 在大规模数 (105以上) 的情况下, 我们应考虑算法较为复杂的堆排序、希尔排序、快速排序和归并排序。
3) 对于一些实际情况的排序, 如果需要考虑算法的稳定性, 对于第1点的少规模数来说, 冒泡排序和插入排序是稳定的, 而选择排序是不稳定的。对于第2点的大规模数来说, 归并排序是稳定的, 而堆排序、希尔排序和快速排序是不稳定的。
4) 排序算法所花的辅助空间情况来考虑, 归并排序为O (n) , 快速排序为O (logn) , 其它均为O (1) 。
5) 对于不同的程序设计者来说, 根据个人喜好、客户特点、系统环境等实际情况来进行选择不同的排序算法。
参考文献
[1]许卓群, 杨冬青, 唐世渭, 等数据结构与算法[M].北京:高等教育出版社, 2005.
[2]严蔚敏, 吴伟民.数据结构[M].北京:清华大学出版社:2007.
[3]曹衍龙, 林瑞仲, 徐慧.C语言实例解析[M].北京:人民邮电出版社, 2007:94-117.
[4]唐艳琴:李清:李卫卫.排序算法探讨[J].现代计算机.2010.12:64-66
希尔排序算法实现与分析 第6篇
1.1 基本思想
希尔排序方法又称为缩小增量排序，其基本思想是将待排序的记录划分成几组，从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。
1.2 步骤
假设待排序的记录为n个，先取整数step
1.3 算法
1.4 实例
假设给定关键字{44 55 12 42 94 18 6 67}，因为关键字有8个，第一次步长step=┏8/2┑=4，其希尔排序的过程如下所示：
初始关键字：44 55 12 42 94 18 06 67
第一趟排序结果：44 18 6 42 94 55 12 67
第二趟排序结果：6 18 44 42 12 55 94 67
当step=2时，在此意义下还未有序，如44与12就不满足小的在前大的在后序列，因此在step=2下再排列一次。
因此第二趟最终排序结果：6 18 12 42 44 45 55 94 67
再对第二趟排序：6 18 12 42 4445 55 94 67step=1
第三趟排序结果：6 12 18 424445 55 67 94
到此，所有关键字从小到大有序，整个排序也就完成了。
2 算法分析
(1)希尔排序算法中for(i=1;i<=n-step;i++)循环语句中的循环条件i<=n-step用得比较好，它表明了在特定步长下，关键字需要比较交换n-step次，开始步长大，比较次数少，后来随着步长缩小，关键字的比较次数就增多了。
(2)希尔排序算法中的
while(flag=1)语句也是用得很好，在上面例子中第二趟排序时6 18 44 42 12 55 94 67，如果没有这个循环语句再做循环判断，在step=2排序结束后就倍减步长，那么这组关键字排序不会成功。因此只有在step=2时把44与12交换后再排列一次，关键字才能排列有序。
(3)希尔排序的步长step=┏n/2┑是首先由希尔本人提出来的，但如何选择增量序列才能产生最好的排序效果，至今还没有解决。但排序的时间性能确实优于直接插入排序。这是因为在希尔排序开始时增量较大，分组较多，每组的记录数目少，各组内直接插入较快，后来增量step逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按step作为距离排过序，使关键字较接近于有序状态，所以新的一趟排序过程较快。而直接插入排序最好情况是正序时，其时间复杂度O(n)，最坏情况是O(n2)，当n比较小时，n与n2差别不大，因此，希尔排序改进了直接插入排序。
参考文献
[1]严蔚敏.数据结构(C语言版)[M].清华大学出版社,2006.
[2]李春葆.数据结构(C语言版)习题与解析[M].清华大学出版社,2000.
[3]徐孝凯.数据结构简明教程[M].清华大学出版社,1997.
几种典型内部排序算法性能分析 第7篇
关键词：排序算法,性能,复杂度
1 绪论
近几年互联网的发展速度越来越快,涉及的领域越来越广,同时对计算机的性能要求也越来越高,基于目前硬件存储性能的限制,科研人员一直致力于计算机性能的优化,在目前的众多方法中,排序算法的优化及选择是研究的重点,排序算法的性能优劣直接影响到程序执行的性能。排序算法目前广泛应用于各个行业领域,例如网站搜索的排序,推荐的先后等等,重要性不言而喻。排序算法是依照一种规则对数据位置进行确定的算法,正是由于排序算法的重要性,人们对排序算法的研究从未停止,先后发明了适合于各种情况的排序算法。本文主要通过对几种典型的排序算法进行算法性能分析,通过算法执行的时间效率、空间效率以及算法稳定性对几种算法进行比较[1]。
2 排序算法
排序算法数据处理规模的不同导致算法使用处理器的不同,一般将排序算法分为内部排序和外部排序。内部排序是指算法的整个处理过程完全在计算机内存中进行的排序算法,这是基于算法的数据估摸相对比较小,计算机内存能够满足计算机读取存储的需求,本文重点讨论的是内部排序中的冒泡排序、选择排序、插入排序、归并排序四种排序算法。外部排序一般需要处理的数据比较大,计算机内存无法满足待排序对象的一次存储,待排序记录需要在计算机内部存储器以及外部存储器之间进行切换来满足数据量的要求,进而实现对整个文件的排序[2]。
2.1 冒泡排序
冒泡排序的基本思想是:通过不断比较相邻两个数的大小,并进行相应的调整使得最后所有数据达到有序,之所以称为冒泡排序是由于每一趟排序只比较出一个最大或最小的数出来,类似于冒泡。
具体排序过程如下:
1)在进行首次排序过程时将第一个数与第二个数比较,小数在前大数在后,之后是第二个数据和第三个数据按照相同的方式进行比较,同时按照小数在前大数在后的规则进行调整次序,不断进行比较交换调整直至最后两个数比较完毕最大的数据在最后一个,此时第一趟比较结束。
2)之后进行第二次排序,从第一个数据按照第一趟排序的规则依次比较排序直至倒数第二个数比较完毕,此时第二大的数据在倒数第二的位置。
3)之后按照相同的规则进行比较直到最后只剩下一个数据,此时排序完成。
冒泡排序算法的程序如下所示:
如果冒泡排序初始的数据所有的记录按照关键字有序的序列的话此时是最好的情况,只需进行一次冒泡,进行n-1次比较便可完成排序,由于所有记录均是关键字有序所以不需要进行移动,时间复杂度O(n);如果初始的正好相反所有的记录按照关键字有序的序列的话此时是最坏的情况需进行n-1趟冒泡,比较的次数n(n-1)/2,移动的次数是3n(n-1)/2,时间复杂度O(n2)。冒泡排序的空间复杂度并不随着处理数据量n的大小而改变,为O(1)。
2.2 选择排序
选择排序的基本思想是:选择排序的主要排序方式是通过选择进行完成的。在初始待排序的数据中找到最小的数据,并把它和初始数据中第一个位置的数据进行交换,同时在剩余的所有数据中按照相同的方法找到最小的数据与初始数据中第二个位置的数据进行比较,按照这种方式对余下的数据进行排序直到所有的数据排序完成,算法结束。
具体的排序过程如下所示:
1)在第一次排序过程中,从所有的m个数sort[0]-sort[m-1]中找到最小的数sort[i],并将sort[i]于sort[1]进行交换。
2)在第二次排序过程中,从剩余的sort[1]-sort[m-1]中再次找到最小的数sort[i],并将sort[i]于sort[2]进行交换。
3)在第j次排序过程中,从剩余的sort[j-1]-sort[m-1]中再次找到最小的数sort[i],并将sort[i]于sort[j-1]进行交换。
4)直到所有数据均有序,算法结束。
选择排序算法的程序如下所示:
通过选择排序的代码可以看出,选择排序的执行过程是两个for循环的查找过程,第一个过程是查找最小元素,第二个过程是m次循环过程,所以时间复杂度是O(n2),所需进行的关键字间的比较次数是n(n-1)/2,移动记录的次数,最小值为0,最大值为3(n-1)。选择排序的空间复杂度并不随着处理数据量n的大小而改变,为O(1)。
2.3 插入排序
这里以希尔插入排序为例,希尔插入排序是对线性插入排序的一种改进,又称为缩小增量排序。希尔排序的基本思想是:对于一个记录数是m的待排序数据,首先选择一个增量dis1<m,并将所有的距离是dis1的数据放在同一个组中,在组中通过插入排序使组内有序,之后取第二个增量dis2并且使得dis2小于dis1,同样进行分组和插入排序,直到距离disi=1排序结束,此时所有的记录进行直接插入排序,排序完成。希尔排序的一个重点是距离增量的选取,目前比较常用的是通过二分法进行增量的选取。
具体的排序过程如下所示:
1)首先选取距离增量dis1,距离增量的初值小于记录数,之后以距离增量作为数据之间的距离,使得相同距离增量的数据分为同一组,并进行直接插入排序。
2)在上面排序结果的基础之后选择距离增量dis2,dis2增量的选取可以参照经典的二分法,向下取整二分dis1,按照步骤1的方式进行组内插入排序。
3)按照相同的距离增量选择原则进行排序直到距离增量为取值为1,此时相当于对一组数据进行直接插入排序,排序完成数据有序,算法结束。
希尔排序算法的程序如下所示:
希尔排序是直接插入排序的改进,在性能上要优于直接插入排序。在希尔排序算法中如果初始的数据所有的记录按照关键字有序的序列的话此时是最好的情况,移动的次数为0,比较的次数在n~n2之间;如果初始的数据所有的记录按照关键字逆序的序列的话此时是最坏的情况,移动次数和比较次数接近n2,但是在平均情况下希尔排序的比较次数和移动次数好于直接插入排序,为O(n1.3)左右。选择排序的空间复杂度并不随着处理数据量n的大小而改变,为O(1)。
2.4 归并排序
归并排序采用的是分治思想,是将两个或多个有序序列合并成一个有序序列的过程。
具体的排序过程如下所示:
1)初始时,将每个记录看成一个单独的有序序列,则n个待排序记录就是n个长度为1的有序子序列;
2)对所有有序子序列进行两两归并,得到n/2个长度为2或1的有序子序列;
3)重复步骤2,直到得到长度为n的有序序列为止。
具有n个待排序记录的归并次数是㏒2n,而一趟归并的时间复杂度为O(n),则整个归并排序的时间复杂度无论是最好还是最坏情况均为O(n㏒2n)。在排序过程中,使用了辅助向量DR,大小与待排序记录空间相同,则空间复杂度为O(n)。归并排序是稳定的,归并排序的排序的空间复杂度和处理数据的规模n相关,为O(n)。
3 实验验证
为了对比四种排序算法的性能,论文通过C++实现了一个验证程序。通过对比排序算法的交换次数、比较次数、移动次数以及排序时间来进一步分析算法性能。通过rand()函数模拟产生1000、4000、7000、10000、15000、30000不同规模的数据。
待排序数量是1K,4K,7K,10K,15K,30K时四种算法执行过程对应的交换次数如表1所示。
(单位:次)
从表中可以看出插入排序以及归并排序并不进行交换,冒泡排序的交换次数规模是最大的,选择排序交换次数和算法数据规模基本相当。
待排序数量是1K,4K,7K,10K,15K,30K时四种算法执行过程进行的比较次数如表2所示。
(单位:次)
从表2中可以看出冒泡排序以及选择排序的比较次数基本相同,插入排序以及归并排序的比较次数基本是比较少的。
待排序数量是1K,4K,7K,10K,15K,30K时四种算法执行过程进行的移动次数如表3所示。
(单位:次)
从表3中可以看出冒泡排序以及选择排序并不进行移动,插入排序的移动次数规模是最大的,并且随着数据规模的增大增长速度也在变快,归并排序的移动次数相对较小。
待排序数量是1K,4K,7K,10K,15K,30K时四种算法执行过程进行的时间对比如表4所示。
从表4中可以看出当数据规模小于15K的时候,四种算法的耗时相对比较平稳,选择排序与插入排序耗时差别不大,冒泡排序相对较多,归并排序耗时相对其他三种算法不是一个数量级,数据规模大于15K时,归并排序的耗时基本变化不大,冒泡排序、选择排序以及插入排序的耗时成指数增长。
4 性能分析
通过上述对冒泡排序、选择排序、插入排序以及归并排序算法的实验性能对比,并通过分析,列出表4.1中的性能对比。
其中整体来说在数据量比较大时归并算法的时间复杂度最低,但是以牺牲空间复杂度为代价的,插入排序和冒泡排序在数据初始正序时的时间复杂度较小,平均情况下插入排序和归并排序的时间复杂度较小,综上分析可以看出选择排序不稳定,冒泡排序、插入排序以及归并排序是稳定的。冒泡排序以及选择排序适合于数据量比较小的情况,归并排序适合数据量比较大的情况。
5 结论
不同排序算法性能各有优劣,在选择排序算法时要综合排序算法的时间复杂度、空间复杂度、稳定性、适合的数据规模等各种因素。通过本文可以得出在数据量较大时选择归并排序,数据量较小时可以选择选择排序,数据大部分有序时可以选择插入排序。
由于本文只对冒泡排序、选择排序、插入排序以及归并排序四种典型的排序算法进行分析讨论,从而有一定的局限性,后续应对更多排序算法的性能进行分析比较。
参考文献
[1]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997:263-289.
排序算法的性能分析 第8篇
排序是计算机科学中的一项复杂而重要的技术, 其功能是对一个数据元素集合或序列重新排列成一个按关键字有序的序列。冒泡排序是比较典型且常用的排序算法, 其基本思想是:对于无序序列, 两两比较相邻数据的关键字, 若反序则进行交换, 直到没有反序为止。在传统的冒泡排序算法中, 不管排序过程中序列的变化情况, 对n个元素排序一律进行n-1轮比较, 第i轮中进行n-i次两两比较找出目前最大 (或最小) 的一个元素。这样比较有时效率较低, 可以通过一定的方法减少关键字的比较次数, 从而提高该算法的执行效率。如何解决这一问题呢?可以充分利用每一轮比较中是否有数据交换的信息, 以及数据交换发生时的位置信息, 来改进和优化常规的冒泡排序算法。
2、算法设计和分析
2.1 算法描述和步骤
算法描述:将待排序的数据放在数组a (1…n) 中, n个元素依次垂直排列, 每个元素看作是重量为其值a (i) 的气泡。根据轻气泡不能在重气泡之下的原则, 从上往下扫描数组a:凡扫描到违反本原则的重气泡, 就使其向下沉。如此反复进行, 直到最后任何两个气泡都是轻者在上, 重者在下为止。
实现步骤:不失一般性, 我们假定数组按照从小到大进行升序排序。
(1) 初始:a数组的n个元素为无序区, 每轮都是自上而下进行扫描。
(2) 第一轮扫描:依次比较相邻的两个元素, 若发现值大者在上、值小者在下, 则交换两者的位置;经过n-1次相邻的两两比较后, 第一轮扫描完毕时"最重"的气泡就"沉底"到该区间的最下面, 即值最大的元素放到最后一个位置a (n) , 值较小的元素逐渐向上"漂浮"。
(3) 第二轮扫描:除去已排好序的最大元素, 对剩下的n-1个元素采用上述方法继续比较, 经过n-2次相邻的两两比较后, 值次大的元素放到了倒数第二个位置a (n-1) 。
(4) 依此类推……, 在第i轮的比较中, 要经过n-次相邻的两两比较, 找出第i大的元素;n个元素一共经过n-1轮扫描, 最后剩下一个元素已在其正确位置, 扫描区域最终为有序区。
2.2 算法设计
以上算法要注意的是, 每轮扫描都是从无序区自上面至该区间底部进行。第i轮扫描前, a (1…n-i) 和a (n-i+1…n) 分别为当前的无序区和有序区;第i轮扫描时, 将当前的最大值元素"沉"到该区中的底部位置a (n-i) 上, 使得a (n-i…n) 变为新的有序区。
下面用Visual Basic语言设计实现了冒泡排序的算法, 用排序子程序过程Sort来实现。其中a为待排序的数组, n为该数组的上界。
2.3 算法分析
冒泡排序算法的时间复杂度主要依赖于关键字的比较次数和数组元素的交换次数。
最好时间复杂度:如果初始序列是正序的, Sort还是需要进行n-1轮扫描, 但没有元素移动, 所需的关键字比较次数C和元素移动次数M均达到最小值:Cmin=n (n-1) /2, Mmin=0, 所以其最好的时间复杂度为O (n2) 。
最坏时间复杂度:如果初始序列是反序的, 需要进行n-1轮扫描。每轮扫描时关键字的比较次数为n-次 (1≤i≤n-1) , 且每次比较都必须移动数据3次来达到交换元素位置。在这种情况下, 比较和移动次数均达到最大值:Cmax=n (n-1) /2, Mmax=3n (n-1) /2, 所以其最坏的时间复杂度为O (n2) 。
平均时间复杂度:假设输入序列的关键字的分布是均匀等可能的。考虑互逆的2个输入序列L1= (k1, k2, …, kn) 和L2= (kn, kn-1, …, k1) 。如果ki>kj, 且ki在表中排在kj前面, 则在冒泡排序时必须要将kj换到ki前面, 即kj向前浮的过程中必定要穿过1次ki, 这个过程要调用1次两数对调 (即3次交换) 。对于任意的2个元素ki和kj, 假设ki>kj, 或者在L1中ki排在kj前面, 或者在L2中ki排在kj前面, 两者必居其一。因此对于任意2个元素ki和kj, 在对L1和L2排序时, 需要将2个元素对调1次。n个元素中任取2个元素有Cn2种取法, 因此对于2个互逆序列进行排序, 需调用Cn2=n (n-1) /2次两数对调, 平均每个序列要调用n (n-1) /4次两数对调, 平均移动次数为3n (n-1) /4。一个元素比它前一个元素的值小的概率情况决定了交换的次数, 不考虑数组中元素的组合情况, 每轮比较的次数为n-i, 平均情况下, 冒泡排序的时间复杂度为n (n-1) /2=O (n2) 。
算法的空间复杂度:交换时只用到一个临时工作单元, 所以其空间复杂度为O (1) 。
算法稳定性:排序过程中, 等值元素的相对位置保持不变, 是就地排序, 所以它是稳定排序法。
3、三种优化算法
3.1 设置标志变量
在排序算法Sort中, 若形参数组a有10个元素, 其对应的数据值分别为{14, 50, 98, 70, 47, 65, 88, 10, 64, 81}, 则代码执行时每轮比较后, a数组的各元素结果如图1所示。从图中可以看出, 第7轮、第8轮和第9轮比较后的10个数的顺序没有发生变化。如果在某一轮排序中没有发生数组元素位置的交换, 则说明待排序的数组中所有元素均满足轻者在上 (左) , 重者在下 (右) 的原则, 因此冒泡排序过程可在此轮排序后终止。
为此, 可以对上面的程序进行改进。引入一个Boolean类型标志变量Flag, 在每轮排序开始前, 先将其置为False;若排序过程中发生了交换, 则将其置为True。每轮排序结束时检查Flag标志, 若未曾发生交换则排序结束, 不需要再进行下一轮排序。
具体做法为在程序的第⑸行的前面增加Flag=False语句, 在第⑻行的前面增加Flag=True语句, 在第⑽行的前面增加If Flag=False Then Exit Sub语句, 这样就可以提前终止算法, 此处将该改进算法记为Sort1。
如果初始序列是正序的, Sort1算法只需要进行1轮扫描即可完成排序, 所需的关键字比较次数C和元素移动次数M均达到最小值:Cmin=n-1, Mmin=0, 所以其最好的时间复杂度为O (n) 。其它的时间复杂度与Sort算法是相同的。
3.2 记住最近的交换位置
若数组a的初始值顺序为{50, 10, 14, 64, 47, 65, 70, 8188, 98}, 用改进的Sort1算法进行排序, 两轮扫描就可将所有元素按升序排列, 第3轮两两比较时已无逆序元素, 根据Flag标志值退出过程。这3轮扫描中关键字的比较次数总计为9+8+7=24次。但实际上后面的5个元素从来没有发生过交换, 因为它们已是升序且大于其前面的元素, 因而后面5个元素之间及其与前面元素的两两比较是没有实际意义的。
可以在每轮扫描中, 设置变量Exchange记住最近一次交换发生的位置, 以免重复比较。Exchange之后的所有元素均已排好序, 下一轮扫描开始时a (1…Exchange-1) 是无序区、a (Exchange…n) 是有序区。这样一轮扫描可以使当前有序区扩展多个元素, 即较大缩小无序区的范围, 而非递减1, 以此减少两两比较的次数和排序轮数。其优化的算法Sort2代码段简写如下:
如果最近发生交换的位置在第j个和第j+1个元素之间时, 则从第j+1个元素到最后一个元素已按关键字排列好了顺序。将最近交换的位置j保存到标志变量Exchange中, 以后只需要对前面j个元素进行两两比较。
Sort2算法由于扫描范围相对少了许多, 所以可以有效的减少关键字的比较次数, 优化后效率能够提高。但是不能优化最坏情况下冒泡排序算法的效率, 在最坏情况下Sort2算法的时间复杂度还是
3.3 双向冒泡排序
冒泡排序具有不对称性, 若初始数据序列是正序的, 一轮扫描即可完成排序;若初始数据序列是反序的, 则需要进行n-1轮扫描排序。在从上 (左) 往下 (右) 扫描并且要求排序结果为升序的前提下, 若数据值最大的元素位于a (1) 的位置, 其余的元素均已排好序, 那么进行一轮扫描后数据也完成了排序, 例如序列{9810, 14, 47, 50, 64, 65, 70, 81, 88}就只需一轮扫描;但当数据值最小的元素位于a (n) 的位置, 其余的元素均已排好序时, 那么仍然需要做n-1轮扫描才能完成排序, 例如序列{14, 47, 50, 64, 65, 70, 81, 88, 98, 10}需要九轮扫描完成。
造成不对称性的原因在于每轮扫描只能使最小的元素向上"漂浮"一个位置, 位于最底端的最小元素上浮到顶端需要n-1轮扫描。为了改进冒泡排序算法的不对称性, 可以在排序过程中交替改变扫描方向。即先从上扫描到下、再从下扫到上, 来回地进行扫描, 这样就得到双向冒泡排序算法Sort3。
具体的做法是:利用每次扫描后得到的最后一次交换发生的位置, 从该位置改变扫描方向, 依次往复……。每个来回都是让当前区间最大的元素沉底、最小的元素浮顶, 不断地缩小需要排序的区间, 当区间中只剩下一个元素时排序结束。
Sort3算法不但继承了Sort2算法的优点, 也解决了算法的不对称性问题。由于Sort3算法一次循环中正向起泡时找最大数、反向起泡时找最小数, 所以改进优化后效率更高。
4、结束语
标志变量法可以解决某一轮扫描时, 没有任何数据发生交换而表明排序完毕;每轮扫描中记住最后一次交换数据的位置, 可使当前有序区扩充多个记录, 从而减少多余不需要的比较;交替改变扫描方向, 可有效改进冒泡排序算法的不对称性。这三种改进优化算法, 对减少扫描和提高执行效率是有所帮助的。但算法的改进和完善是无止境的, 可以不断发掘冒泡排序的内涵, 使其性能和效率能够进一步地提升。
参考文献
[1]严蔚敏, 吴伟民.数据结构:C语言版[M].北京:清华大学出版社, 1997
[2]周培德.算法设计与分析[M].北京:机械工业出版社, 1992
[3]陈忠坚.冒泡排序在VB程序中的实现[J].科技信息, 2010 (19) :76, 83
排序算法的性能分析 第9篇
排序问题是组合优化问题中重要问题之一。该问题在计算机控制,硬件设置,生产管理等方面有着广泛的应用[1]。其目标是在已知机器数量和工件个数的情况下,使全部工件都加工完的时间达到最小这一目标寻求最优排列。平行机排序问题中的工件集合通常表示为L={J1,J2,…,Jn},机器表示为M1,M2,…,Mn.按照决策者对工件信息的掌握程度,排序问题可以分为离线问题和在线问题两类。在安排工件前如果所有工件的信息都已知,这类排序问题称为离线排序问题。在线排序是:工件一个一个地释放,在安排完当前已知工件前,决策者不知道后面工件的任何信息,只有安排完当前工件后才能知道后面是否还有新的工件到来,且一个工件一旦被安排下来就不能再做更改,而排序问题大都是NP困难问题,所以一般讨论近似算法。在对工件进行排序时产生了很多种不同的是算法,Graham[2,3]提出的列表算法(List Scheduling,简记为LS)是一个最简单的算法,并证明了LS算法的竞争比是2-1/m,该算法是按照工件出现顺序依次安排工件,每次都是将当前工件安排到使其最早加工完蹬机器上加工。在Graham的在线模型里,假设所有工件的到达时间为零,这种模型也称为经典在线模型,当机器台数不大于4时LS算法也是最佳在线算法[4]。Li和Huang[5]通过假设每个工件都有一个达到时间对Graham的在线模型做了推广。一个工件Jj的信息由二元组(rj,pj)表示,这里rj表示Jj的释放时间(release time),pj表示Jj的加工时间。这种模型称为工件有到达时间的在线排序问题,或称为订单在线排序问题。
在经典在线模型中,当机器台数m=2或3时,LS算法的性能比不能再改进,也就是说LS算法是最好可能的在线算法。这就使得人们考虑是否可以知道部分信息以改进算法的性能比。这就是所谓的半在线排序问题。最早研究半在线排序问题的是Liu等[6]。对于假定所有工件都是按照加工长度从大到小的顺序出现且到达时间都为零的模型,Seiden[7]等首先证明了LS算法的竞争比为4/3-1/3 m,当m=2时,他们证明了LS算法是最好可能的在线算法。Cheng[8]等给出了m=3时的最好可能的在线算法,当m≥4时,他们给出了一个5/4-竞争比的在线算法。更多有关半在线的问题参见文献[9]、文献[10]等。
以上经典的半在线模型都假设工件在零时刻都到达,实际情况中所有工件同时到达是不可能的,因而需要考虑工件的到达时间参数。本文引入工件的到达时间参数,讨论工件到达时间序列满足单调不减且加工时间序列满足单调不增的半在线排序问题,首次对此问题的LS算法进行了理论分析,详细证明了,3/2-1/2 m是LS算法的最坏性能比的上界,为工件加工优化组合的研究提供理论基础。
2 LS算法及本文中所用的符号
对工件序列L={J1,J2,…,Jn},本文总是用rj和pj分别表示工件Jj(j=1,2,…,n)的到达时间和加工时间且满足:r1≤r2≤…≤rn,p1≥p2≥…≥pn.
下面给出LS算法:
Step1:设Jn是到达时间为rn和加工时间为pn的新来的工件。设Li(1≤i≤m)是机器Mi上在工件Jn被安排之前的最后完工时间。重新排序机器序列使满足L1≤L2≤…≤Lm.
Step2:将Jn工件安排机器M1上。
下面给出本文后面所用的一些记号:
(1)空闲区间(a,b):设(a1,b2),…,(ap,bp)是工件序列L在LS算法中所有的空闲区间,(a,b)是其中之一,满足
(2)U,U*:U为LS算法中所有空闲时间长度之和,即;U*为一个最优算法中所有空闲时间之和;
(3)JA(i,j):在算法A中,机器Mi上加工的第j个工件;
(4)S(A,JA(i,j)):工件JA(i,j)在算法A中的起始加工时间;
(5)li:LS算法中Mi上安排的工件个数;
(6)Bi(i=1,…,m):设Bi={JLS(i,j)|S(LS,JLS(i,j))≤b≤S(LS,JLS(i,j))+pLS(i,j)},即LS算法安排集合Bi中的工件JLS(i,j),在b时刻前开始加工,但在b时刻后加工完。显然|Bi|≤1;
(7)Δi(i=1,2,…,m)及Δ:当时,令Δi=0。当时,令。最后令:Δ=max{Δ1,…,Δm};
(8)ΔAij:在算法A中,Mi上加工的第j-1和第j(j2)个工件之间的空闲长度,即
3 主要结论及其证明
定理1对于任意工件序列L={J1,J2,…,Jn},下式成立:
证明假设式(1)不成立,那么存在工件序列L(即反例L)使得式(1)不成立。下面设L={J1,J2,…,Jn}是一个反例且L中工件的个数是所有反例中最少的,称这样的反例为最小反例。记工件Jn到达前机器M1,M2,…,Mm的完工时间为L1,L2,…,Lm且满足L1≤L2≤…≤Lm,那么对于最小反例L,易知有CLSmax(L)=L1+pn.
情况1:当LS算法中没有空闲区间时,显然,所以有:
由此可得:
由LS算法规则易知LS算法中每台机器仅加工完一个工件,所以CLSmax(L)=CmaxOPT(L),矛盾。
情况2:LS算法中至少有一个空闲区间。
由Δi的定义可知,对任何算法ρ,机器Mi上LS算法中安排在b时刻之后加工而在算法ρ中可前移到b之前加工的工作量最多为Δi,因此任一最优算法在M1,M2,…,Mm上安排在时刻b前的工作量比LS算法安排在b时刻前的工作量最多增多,所以有
不妨设机器Mr(1≤r≤m)在算法LS中在(a,b)上空闲,则有:
由区间(a,b)的定义可知存在工件Jx(1≤x≤n)满足rx=S(LS,Jx)=b且LS算法把Jx可安排在Mr上,由不等式可知,
所以有:
由L是(1)的反例可得:
当Δ=0时,有2(Δ+pn)>CmaxOPT(L),由定理1证明可知CLSmax(L)=CmaxOPT(L),也矛盾。
当Δ>0时,设机器Ms满足:
由LS算法规则容易得到:
引理1当Δ>0时,若Jt满足SLS(s,k)+pt≤b,则pLS(s,k)≤pt,这里的s和k由式(5)定义。
Jt满足S(LS,Jt)+pt≤b,若,则由引理1得
由此得以下两个推论:
推论1当Δ>0时,每台机器在b时刻前至多加工完两个工件。
推论2若机器Mi,Mt(1≤t≤m)满足:,即Mi加工完JLS(i,1)的时间不小于Mt加工完JLS(t,2)的时间,则Mi在b时刻前至多加工完JLS(i,1)这一个工件。
引理2对于最小反例L,在LS算法中对机器M1,M2,…,Mm重新编号,使之满足,则有
Ⅰ.当时,有
Ⅱ.当时,存在ω(1≤ω≤m),使得.
证明显然成立,由r1≤r2≤…≤rn可知,,有
由ΔAij(1≤i≤m)的定义易知:
当S(A,JA(i,2))=rA(i,2)时,有
当S(A,JA(i,2))>rA(i,2)时,ΔAi2=0,得:
对任意的i,j∈{1,2,…,m},若rOPT(j,1)+pOPT(j,1)≤rOPT(i,1),那么将JOPT(j,1)安排到JOPT(i,1)前加工,显然这种调动不会使CmaxOPT(L)增加,所以不妨设在最优算法中满足:
下面开始证明结论Ⅰ:因为。所以,
情况1:。此种情况由(9),(10),(12)可知
情况2:若满足Δa2LS>0。设,若所有,则有
若存在i,j(1≤i≤m;j∈{1,2}),满足JOPT(i,j)≠JLS(i,j),分以下两步讨论:
(1)首先证明存在排序σ使下式成立:
若。如果Ji=JOPT(k,3)(1≤k≤m),那么Ji与Δk1OPT,Δk2OPT无关,只需把Ji插入到工件JOPT(i,1)之前加工,此时排列A*,显然,且Δk1OPT+Δk2OPT=ΔAk1+ΔAk2.如果Ji=JOPT(k,2)(1≤k≤m),显然此时有:,所以有ΔK2OPT=0。因为JOPT(i.1)∈{J1,J2,…Jm}且,所以
下面将JOPT(u,1)与Ji对调,记对调后的排列为A*,则有:
由(13)可知,,所以。所以有:
当rOPT(u,1)+pOPT(u,1)>ri+pi时,易得(15)≥pipOPT(u,1)≥0。否则由(13)得rOPT(u,1)+pOPT(u,1)>rOPT(u,2),所以也有(15)≥rOPT(u,1)-ri≥0。即[(Δi1OPT+Δi2OPT)+(Δk1OPT+Δk2OPT)]-[(Δi1A*+Δi2A*)+(Δk1A*+Δk2A*)]≥0总是成立。
通过这种方式对调,即可最后得到新的排序A,满足:
进一步考虑排序A,若。又因为,设Jt=JA(q,r)(1≤q≤m),显然r≥3,即Jt和Δξq1、Δξq2无关,又因为Δξq1+Δξq2=ΔAq1+ΔAq2,所以[(ΔAS1+ΔAS2)+(ΔAq1+ΔAq2)]-[(ΔξS1+ΔξS2)+(Δξq1+Δξq2)]≥0,通过这种方式调换,即可得排列σ满足:
综上(16)和(17)即得(14)。
(2)对M1,M2,…,Mm重新编号,使得在前面得到的排序σ中满足
因为,所以不妨设Jσ(m,1)=JLS(j,1);Jσ(s,1)=JLS(m,1)(1≤s,j≤m),由假设有.所以得
下面将工件Jσ(m,1)与Jσ(s,1)(即工件JLS(j,1)与JLS(m,1))对调,记对调之后的排列为τ,则有
下式是对调后空闲的变化:
下面分两种情况讨论(18):
(1).这时有:,所以得,
(2)这时有:,所以有。进而由(18)得:
即这种调换不会使排列σ的空闲时间增加。
若,依次观察工件Jσ(m-1,1),…,Jσ(1,1)找出满足Jσ(j,1)≠JLS(j,1)(1≤j≤m-1)的工件,再类似对其进行上述的调换,这种调换不会增加每台机器前两个空闲的总和。通过多次这种类似调换方式,即可最后得到一个排序τ′满足:
Ⅱ.当时,由LS算法规则可知从某台机器Mw开始,使得当Mw加工完工件JLS(w,1)时,Me加工完工件.又因为,所以有:
(1)对任意q∈{w,…,m},当Mq加工完时,Me加工完工件,所以有
(2),即对于M1,…,Mw-1中任意两台机器而言,不存在某一台机器加工完第一个工件所耗的时间比另一台机器加工完其前两个工件所耗的时间更长的情况。所以,按Ⅰ的方法,即得:
下面完成定理1的证明。
情形Ⅰ:当时,设
这里li是LS算法中机器Mi上加工工件的个数。由引理2可知,此时有,再由推论1可知每台机器在b时刻前至多加工完两个工件,所以,
当Δ>0时,设s与k满足(5),由引理1可知,当k≥2时有:
由ΔAij的定义可知此时S(LS,JLS(s,k))=S(LS,JLS(s,k-1))+pLS(s,k-1)成立,所以有
当Ms在b时刻前仅加工完工件JLS(s,1)时,k=2。因为S(LS,JLS(s,k))+pLS(s,k)>b,所以,所以Δs*=Δs3LS=0。而当Ms在b时刻前加工完两个工件JLS(s,1),JLS(s,2)时,k=3,由(21)、(23)可知此时有Δs*=Δs3LS=0,所以有:.再由(22)得,
设.由L是最小反例得2(Δ*+pn)>COPTmax(L),结合(4)即可得出
(1)当Δ*=0时,由情况1的证明可知此时COPTmax(L)=CLSmax(L),矛盾。
(2)当Δ*>0时,设在机器Mu(u∈{1,2,…,m})上有
这样Mu在b时刻前加工完两个工件JLS(u,1),JLS(u,2).由式(8)即得pLS(u,1)≥pLS(u,2)>Δ,所以有.所以有,这与(24)矛盾。
情形Ⅱ:当时,先对机器M1,…,Mm排序,使之满足,由引理2可知此时有:(这里w的取法与引理2中Ⅱ的取法一样)。令
这里li表示算法LS在机器Mi上安排的工件的个数。由推论1可知Mw,…,Mm在b时刻前至多加工完一个工件,同时M1,…,Mw-1在b时刻前至多加工完两个工件。因而有:
由1的证明易知,此时同样有Δ*s=0,所以,再由(26)、(27)易知,.
设Δ*=Δ*u=max{Δ*1,Δ*2,…,Δ*m},类似于情形I同样可得2min{Δ,Δ*}+2pn>COPTmax(L)。
(1)当Δ*=0时,2pn>COPTmax(L),由情形I的证明可知COPTmax(L)=CLSmax(L),矛盾。
(2)当Δ*>0时,分以下两种情况讨论:
(1)若Mu在b时刻前加工完两个工件JLS(u,1),JLS(u,2),则Δ*u=ΔLSu3.由情形I的证明同样可得出此时有,这与(24)矛盾。
(2)若Mu在b时刻前仅加工完一个工件JLS(u,1),则Δ*u=ΔLSu2.
因为有w≤u≤m,且存在Me(1≤e≤w-1),使得下式成立:
所以有:
这样有,也与(24)矛盾。
综上所述,对任意的工件序列L,有(1)成立。这样定理1得证。
4 结束语
本文考虑了工件J1,J2,…,Jn在到达时间非递减,加工时间非递增的情况下首次详细地证明了LS算法的最坏性能比不大于3/2-1/2 m,然而此上界并不是该模型最坏性能比的理想上界,其最坏性能比应该还可以减小。我们猜想LS算法的最坏性能比的紧界为4/3-1/3 m,这是很值得研究的问题。从本文的证明可以看出工件有到达时间参数的排序模型比没有到达时间参数的排序模型要复杂得多。本文的理论结果有助于对LS算法性能的进一步分析,证明方法上为进一步设计更好的算法提供了方法和理论基础。
摘要：对于在m台平行机上工件有单调非减的到达时间和单调非增的加工时间的半在线排序问题进行了研究,其目标函数是要令所有机器中最大完工时间达到最小。对任意半在线工件序列和任意m台机器,证明了3/2-1/2 m为LS算法的最坏性能比的上界。
关键词：到达时间非递减,加工时间非递增,半在线,LS算法,最坏性能比
参考文献
[1]何勇,杨启帆,谈之奕.平行机半在线排序问题研究[J].高校应用数学学报,2003,18(1):105~114.
[2]Graham R L.Bounds on multiprocessing timing anomalies[J].SIAM J.Appl.Math.,1969,17(2):416~429.
[3]Graham R L.Bounds for certain multiprocessing finishing anomalies[J].The Bell System Technical Journal,1966,45:1563~1581.
[4]Faigle U,Kern W,Turan G.On the performance of online algorithms for partition problems[J].Acta Cybernetica,1989,9:107~119.
[5]Li R,Huang H C.On-line scheduling for jobs with arbitrary release times[J].Computing,2004,73(7):79~97.
[6]Liu W P,Sidney J B,Vliet A.Ordinal algorithm for parallel machine scheduling[J].Operations Research Letters,1996,18(3):223~232.
[7]Seiden S,et al.Semi-online scheduling with decreasing job sizes[J].Operations Research Letters,2000,27(10):215~222.
[8]Cheng T C E,Kellerer H,Kotov V.Algorithms better than LPT for semi-online scheduling with decreasing processing times[J].Operations Research Letters,2012,40(5):349~352.
[9]Li R H,Cheng X Y,Zhou Y X.On-line scheduling for jobs with non-decreasing release times and similar lengths on parallel machines[J].Optimization-A Journal of Mathematical Programming and Operations Research,2014,63(6):867~882.
