浙江财经学院数据结构排序实验(3)

template

void SelectionSort(ElemType data[], int n) {

int i, j, min;

for (i = 0; i < n; i++){ min = i;

for (j = i + 1; j < n; j++){ if ( data[j] < data[min]) min = j; }

Swap(data[i],data[min]); } }

//Main.cpp

#include #include #include #include \#include \#include \#include \

#define N 100000000 void main() {

int n=100000;

int *a=new int[N]; //堆分配大规模内存 int *b=new int[N]; //堆分配大规模内存

clock_t zjcrstart, zjcrfinish,mpstart, mpfinish,ksstart, ksfinish,jdxzstart,jdxzfinish; 记录排序前后的时间。clock_t是\机器钟\类型

double zjcrduration,mpduration,ksduration,jdxzduration; //排序花费的时间

//产生随机数种子

srand( (unsigned)time( NULL )+ 110104200145 ); for (int k=1; k<=10; k++) { //产生十组随机数 for (int i=0; i

11

// { b[i]=a[i]=rand(); //产生N个随机数, a数组用于排序，b数组用于保留原始数据 } zjcrstart = clock(); //记录排序开始时的机器时间 //以下调用第一个排序算法，对N个数排序 cout<<\ for(int j=0;j

12

a[w]=b[w]; } ksstart = clock(); //记录排序开始时的机器时间 // 调用排序算法…… QuickSort(a,n); ksfinish = clock(); //记录排序结束时的机器时间 ksduration = (double)(ksfinish - ksstart); //单位为毫秒 cout<<\快速排序花费的时间 = \//输出排序花费的时间 //简单选择排序 for (int e=0; e

以a[10]={1,9,3,7,25,48,21,5,8,10}为例 直接插入排序 冒泡排序 快速排序 简单选择排序 比较次数 13 9 3 45 移动次数 28 0 4 30

13

经过比较发现，当规模不断增加时，各种算法之间的差别是很大的。这六种算法中，快速排序比较和移动的次数是最少的,也是最快的一种排序方法。直接选择排序虽然交换次数很少，但比较次数较多.

以n=100000为例：

14

当数据规模很大时，冒泡排序花费的时间最多，快速排序花费的最少。

15