1．实验要求

【实验目的】

学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

【实验内容】

使用简单数组实现下面各种排序算法，并进行比较。

排序算法：

1、插入排序

2、希尔排序

3、冒泡排序

4、快速排序

5、简单选择排序

6、堆排序（选作）

7、归并排序（选作）

8、基数排序（选作）

9、其他

要求：

1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度

编写测试main()函数测试线性表的正确性。

2. 程序分析

2.1 存储结构

存储结构：数组

2.2 关键算法分析

//插入排序

void InsertSort(int r[], int n)

{

int count1=0,count2=0;

for (int i=2; i＜n; i++)

{

r[0]=r[i]; //设置哨兵

for (int j=i-1; r[0]＜r[j]; j--) //寻找插入位置

r[j+1]=r[j]; //记录后移

r[j+1]=r[0];

count1++;

count2++;

}

for(int k=1;k＜n;k++)

cout＜＜r[k]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

}

//希尔排序

void ShellSort(int r[], int n)

{

int i;

int d;

int j;

int count1=0,count2=0;

for (d=n/2; d＞=1; d=d/2) //以增量为d进行直接插入排序

{

for (i=d+1; i＜n; i++)

{

r[0]=r[i]; //暂存被插入记录

for (j=i-d; j＞0 && r[0]＜r[j]; j=j-d)

r[j+d]=r[j]; //记录后移d个位置

r[j+d]=r[0];

count1++;

count2=count2+d;

}

count1++;

}

for(i=1;i＜n;i++)

cout＜＜r[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

}

//起泡排序

void BubbleSort(int r[], int n)

{

int temp;

int exchange;

int bound;

int count1=0,count2=0;

exchange=n-1; //第一趟起泡排序的范围是r[1]到r[n]

while (exchange) //仅当上一趟排序有记录交换才进行本趟排序

{

bound=exchange;

exchange=0;

for(int j=0;j＜bound;j++) //一趟起泡排序

{

count1++; //接下来有一次比较

if(r[j]＞r[j+1])

{

temp=r[j]; //交换r[j]和r[j+1]

r[j]=r[j+1];

r[j+1]=temp;

exchange=j; //记录每一次发生记录交换的位置

count2=count2+3; //移动了3次

}

}

}

for(int i=1;i＜n;i++)

cout＜＜r[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

}

//快速排序一次划分

int Partition(int r[], int first, int end,int &count1,int &count2)

{

int i=first; //初始化

int j=end;

int temp;

while (i＜j)

{

while (i＜j && r[i]＜= r[j])

{

j--; //右侧扫描

count1++;

}

count1++;

if (i＜j)

{

temp=r[i]; //将较小记录交换到前面

r[i]=r[j];

r[j]=temp;

i++;

count2=count2+3;

}

while (i＜j && r[i]＜= r[j])

{

i++; //左侧扫描

count1++;

}

count1++;

if (i＜j)

{

temp=r[j];

r[j]=r[i];

r[i]=temp; //将较大记录交换到后面

j--;

count2=count2+3;

}

}

return i; //i为轴值记录的最终位置

}

//快速排序

void QuickSort(int r[], int first, int end,int &count1,int &count2)

{

if (first＜end)

{ //递归结束

int pivot=Partition(r, first, end,count1,count2); //一次划分

QuickSort(r, first, pivot-1,count1,count2);//递归地对左侧子序列进行快速排序

QuickSort(r, pivot+1, end,count1,count2); //递归地对右侧子序列进行快速排序

}

}

//简单选择排序

void SelectSort(int r[ ], int n)

{

int i;

int j;

int index;

int temp;

int count1=0,count2=0;

for (i=0; i＜n-1; i++) //对n个记录进行n-1趟简单选择排序

{

index=i;

for(j=i+1;j＜n;j++) //在无序区中选取最小记录

{

count1++; //比较次数加一

if(r[j]＜r[index]) //如果该元素比现在第i个位置的元素小

index=j;

}

count1++; //在判断不满足循环条件j＜n时，比较了一次

if(index!=i)

{

temp=r[i]; //将无序区的最小记录与第i个位置上的记录交换

r[i]=r[index];

r[index]=temp;

count2=count2+3; //移动次数加3

}

}

for(i=1;i＜n;i++)

cout＜＜r[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

}

//筛选法调整堆

void Sift(int r[],int k,int m,int &count1,int &count2) //s，t分别为比较和移动次数

{

int i;

int j;

int temp;

i=k;

j=2*i+1; //置i为要筛的结点，j为i的左孩子

while(j＜=m) //筛选还没有进行到叶子

{

if(j＜m && r[j]＜r[j+1]) j++; //比较i的左右孩子，j为较大者

count1=count1+2; //该语句之前和之后分别有一次比较

if(r[i]＞r[j])

break; //根结点已经大于左右孩子中的较大者

else

{

temp=r[i];

r[i]=r[j];

r[j]=temp; //将根结点与结点j交换

i=j;

j=2*i+1; //下一个被筛结点位于原来结点j的位置

count2=count2+3; //移动次数加3

}

}

}

//堆排序

void HeapSort(int r[],int n)

{

int count1=0,count2=0; //计数器，计比较和移动次数

int i;

int temp;

for(i=n/2;i＞=0;i--) //初始建堆，从最后一个非终端结点至根结点

Sift(r,i,n,count1,count2) ;

for(i=n-1; i＞0; i--) //重复执行移走堆顶及重建堆的操作

{

temp=r[i]; //将堆顶元素与最后一个元素交换

r[i]=r[0];

r[0]=temp; //完成一趟排序，输出记录的次序状态

Sift(r,0,i-1,count1,count2); //重建堆

}

for(i=1;i＜n;i++)

cout＜＜r[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

}

//一次归并

void Merge(int r[], int r1[], int s, int m, int t)

{

int i=s;

int j=m+1;

int k=s;

while (i＜=m && j＜=t)

{

if (r[i]＜=r[j])

r1[k++]=r[i++]; //取r[i]和r[j]中较小者放入r1[k]

else

r1[k++]=r[j++];

}

if (i＜=m)

while (i＜=m) //若第一个子序列没处理完，则进行收尾处理

r1[k++]=r[i++];

else

while (j＜=t) //若第二个子序列没处理完，则进行收尾处理

r1[k++]=r[j++];

}

//一趟归并

void MergePass(int r[ ], int r1[ ], int n, int h)

{

int i=0;

int k;

while (i＜=n-2*h) //待归并记录至少有两个长度为h的子序列

{

Merge(r, r1, i, i+h-1, i+2*h-1);

i+=2*h;

}

if (i＜n-h)

Merge(r, r1, i, i+h-1, n); //待归并序列中有一个长度小于h

else for (k=i; k＜=n; k++) //待归并序列中只剩一个子序列

r1[k]=r[k];

}

//归并排序

void MergeSort(int r[ ], int r1[ ], int n )

{

int h=1;

int i;

while (h＜n)

{

MergePass(r, r1, n-1, h); //归并

h=2*h;

MergePass(r1, r, n-1, h);

h=2*h;

}

for(i=1;i＜n;i++)

cout＜＜r[i]＜＜" ";

cout＜＜endl;

}

void Newarray(int a[],int b[],int c[])

{

cout＜＜"新随机数组：";

c[0]=0;

a[0]=0;

b[0]=0;

for(int s=1;s＜11;s++)

{

a[s]=s;

b[s]=20-s;

c[s]=rand()%50+1;

cout＜＜c[s]＜＜" ";

}

cout＜＜endl;

}

2.3 其他

3. 程序运行结果

void main()

{

srand(time(NULL));

const int num=11; //赋值

int a[num];

int b[num];

int c[num];

int c1[num];

c[0]=0;

a[0]=0;

b[0]=0;

Newarray(a,b,c);

cout＜＜"顺序数组：";

for(int j=1;j＜num;j++)

cout＜＜a[j]＜＜" ";

cout＜＜endl;

cout＜＜"逆序数组：";

for(j=1;j＜num;j++)

cout＜＜b[j]＜＜" ";

cout＜＜endl;

cout＜＜endl;

cout＜＜"插入排序结果为："＜＜"\n";

InsertSort(a,num);

InsertSort(b,num);

InsertSort(c,num);

cout＜＜endl;

Newarray(a,b,c);

cout＜＜"希尔排序结果为："＜＜"\n";

ShellSort(a, num);

ShellSort(b, num);

ShellSort(c, num);

cout＜＜endl;

Newarray(a,b,c);

cout＜＜"起泡排序结果为："＜＜"\n";

BubbleSort(a, num);

BubbleSort(b, num);

BubbleSort(c, num);

cout＜＜endl;

int count1=0,count2=0;

Newarray(a,b,c);

cout＜＜"快速排序结果为："＜＜"\n";

QuickSort(a,0,num-1,count1,count2);

for(int i=1;i＜num;i++)

cout＜＜a[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

count1=0,count2=0;

QuickSort(b,0,num-1,count1,count2);

for(i=1;i＜num;i++)

cout＜＜b[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

count1=0,count2=0;

QuickSort(c,0,num-1,count1,count2);

for(i=1;i＜num;i++)

cout＜＜c[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

cout＜＜endl;

cout＜＜endl;

Newarray(a,b,c);

cout ＜＜ "简单选择排序结果为：" ＜＜ "\n";

SelectSort(a,num);

SelectSort(b,num);

SelectSort(c,num);

cout＜＜endl;

Newarray(a,b,c);

cout ＜＜ "堆排序结果为：" ＜＜ "\n";

HeapSort(a, num);

HeapSort(b, num);

HeapSort(c, num);

cout＜＜endl;

Newarray(a,b,c);

cout ＜＜ "归并排序结果为：" ＜＜ "\n";

MergeSort(a, c1,num );

MergeSort(b, c1,num );

MergeSort(c, c1,num );

}