数据结构各种排序算法的时间性能

}

s[p]=s[r]; p++; this->SortNum++; break; } r--; this->SortNum++; } for(i=p;ikey) { s[r]=s[p]; r--; this->SortNum++; break; } p++; this->SortNum++; } }

s[p]=key;

return p;

(7)基本操作

AList(int size=DefaultListSize) { maxSize = size; listSize = fence = 0;

listArray = new Elem[maxSize]; }

~AList() { delete [] listArray; }

<1>清空。释放数组，将数组大小和栅栏置0. void clear() {

delete [] listArray; listSize = fence = 0;

listArray = new Elem[maxSize]; }

<2>将栅栏赋初值0，放在开头。 void setStart() { fence = 0; }

<3>将栅栏指向数组最后。 void setEnd() { fence = listSize; }

<4>获得当前的位置。用栅栏的指向即可直接获得。 void prev() { if (fence != 0) fence--; }

<5>获得最大值的大小，由栅栏可直接获得。 void next() { if (fence <= listSize) fence++; }

<6>返回当前位置左边的长度。直接返回栅栏的值获得。 int leftLength() const { return fence; }

<7>返回当前位置右边的长度。用最大长度减去当前栅栏的值。 int rightLength() const

{ return listSize - fence; }

<8>设置当前位置，将值直接赋予栅栏。 bool setPos(int pos) {

if ((pos >= 0) && (pos <= listSize)) fence = pos;

return (pos >= 0) && (pos <= listSize); }

<9>返回当前的值。

bool getValue(Elem& it) const {

if (rightLength() == 0) return false; else {

it = listArray[fence]; return true; } }

（4）算法的时空分析

<1>插入排序：直接插入排序算法必须进行n-1趟。最好情况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)，移动元素次数是2(n-1)。因此最好情况下的时间复杂度就是O(n)。最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为O(n2)。

<2>冒泡排序：当原始数据正向有序时，冒泡排序出现最好情况。此时，只需

进行一趟排序，作n-1次关键字比较，因此最好情况下的时间复杂度是O(n)。当原始数据反向有序时，冒泡排序出现最坏情况。此时，需进行n-1趟排序，第i趟作(n-i)次关键字间的比较，并且需执行(n-i)次元素交换，所以，比较次数为：因此,最坏情况下的时间复杂度为O(n2)

<3>快速排序：如果每一次分划操作后，左、右两个子序列的长度基本相等，则快速排序的效率最高，其最好情况时间复杂度为O(nlog2n)；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，此时，快速排序效率最低，其最坏情况时间复杂度为O(n2)。如果选择左边第一个元素为主元，则快速排序的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况时间复杂度为O(nlog2n)。

<4>堆排序：堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O(nlogn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时间复杂度O(nlogn)。

<5>归并排序：在最佳、平均、最差情况下，时间复杂度为?(n log n)，不足的就是需要两倍的空间代价，当输入的待排序数据存储在链表中时，归并排序是一个很好的选择.

（5）函数的调用关系图

主程序

用户输入排序的元素个数n 产生n个随机数 对随机数进行排序 输出 （6）输入和输出的格式

输入 请输入排序规模：//提示输入

等待输入

输出 插入排序算法对n个随机数排序时间为 插入排序算法对n个随机数交换次数为

冒泡排序算法对n个随机数排序时间为

冒泡排序算法对n个随机数交换次数为

堆排序算法对n个随机数排序时间为 堆排序算法对n个随机数交换次数为

合并排序算法对n个随机数排序时间为 合并排序算法对n个随机数交换次数为

快速排序算法对n个随机数排序时间为

快速排序算法对n个随机数交换次数为

排序后，前50个有序元素为：

四、用户使用说明（可选）

1、本程序的运行环境为DOS操作系统，执行文件为conversion.exe 2、运行程序时

输入 请输入排序规模：//提示输入

等待输入

输出 插入排序算法对n个随机数排序时间为 插入排序算法对n个随机数交换次数为

冒泡排序算法对n个随机数排序时间为 冒泡排序算法对n个随机数交换次数为

堆排序算法对n个随机数排序时间为 堆排序算法对n个随机数交换次数为

合并排序算法对n个随机数排序时间为 合并排序算法对n个随机数交换次数为

快速排序算法对n个随机数排序时间为

快速排序算法对n个随机数交换次数为

排序后，前50个有序元素为：