中北大学算法分析与设计实验报告二（选择排序，冒泡排序，堆排序）

1.实验名称

实验二 蛮力优化算法实验

2.实验目的

题目1、排序问题程序设计 （1）掌握选择排序和起泡排序的基本思想； （2）掌握两种排序方法的具体实现过程； （3）在掌握的基础上编程实现两种排序方法。 题目2、整数排序问题 增强学生对算法时间复杂度的理解与应用。

3.训练知识点集群

（1）根据实验内容设计算法伪代码进行算法描述； （2）利用C++/C/Java等编程语言对算法伪代码进行工程化实现； （3）输入测试用例对算法进行验证； （4）列出算法时间复杂度模型并与计算机运行统计时间进行对比分析。

4.实验内容

题目1： 输入一个待排序的序列，分别用选择排序和起泡排序两种排序方法将其变换成有序的序列，输出结果，输出时要求有文字说明。请任选一种语言编写程序实现上述算法，并分析其算法复杂度。 题目2： 任意输入N个整数，请用选择排序、堆排序和冒泡排序算法对输入的任意N个数进行有序排列，输出排序结果，并比较三种算法的时间复杂度。

5.实验原理

题目1：

（1）问题描述 输入一个待排序的序列，分别用选择排序和起泡排序两种排序方法将其变换成有序的序列，输出结果，输出时要求有文字说明，并分析其算法复杂度。

（2）算法思想 选择排序： 选择排序基本思想：第一次从arr[0]arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]arr[n-1]中选取最小值，与arr[i-1]交换，…,第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

起泡排序（冒泡排序）： 通过对待排序序列从前向后（从下标较小的元素开始）,依次比较 相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

（3）算法描述 选择排序： 1）将整个记录序列化分为有序区和无序区，初始时有序区为空，无序区含有待排序的所有记录； 2）在无序区查找值最小的记录，将它与无序区的第一个记录交换，使得有序区扩展一个记录，同时无序区减少一个记录； 3）不断重复步骤（2），直到无序区只剩下一个记录为止。

起泡排序（冒泡排序）： 1）将整个记录序列划分为有序区和无序区，初始时有序区为空，无序区含有待排序的所有记录； 2）对无序区从前向后依次比较相邻记录，若反序则交换，从而使得值晓得记录向前移，值较大的记录向后移（像水中的气泡，体积大的先浮上来）； 3）不断重复步骤2），直到无序区没有反序的记录。

题目2：

（1）问题描述： 任意输入N个整数，请用选择排序、堆排序和冒泡排序算法对输入的任意N个数进行有序排列，输出排序结果，并比较三种算法的时间复杂度。 （2）算法思想 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]]>=A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

（3）算法描述 1）将初始待排序关键字序列(R1,R2…Rn)构建成大顶堆，此堆为初始的无须区； 2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,…Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]; 3）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,…Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2…Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

6.源代码实现

（1）选择排序:

#include

//对含有n个数的数组进行遍历

void visit(int r[],int n){

for(int i=0;i

printf("%4d",r[i]);

printf("\n");

}

}

void SelectSort(int r[], int n){

int i, j, index, temp;

int compare = 0, move = 0;

for(i=0;i

index= i;

for(j=i+ 1;j

if (r[j]

index= j;

compare++; //比较次数增加1

}

if(index!=i){ //交换记录

temp = r[i];

r[i] = r[index];

r[index] = temp;

move+=3; //交换一次移动3次

}

visit(r,10);

}

printf("在本次排序中共比较了%d次，移动了%d次。\n",compare,move);

}

int main(){

int r[10]={0};

printf("请依次输入10个整数，用空格隔开: \n");

for(int i=0;i<10;i++)

scanf("%d", &r[i]);

printf("排序之前的记录: \n");

visit(r,10);

printf("进行选择排序: (每趟排序后的结果如下所示)\n");

SelectSort(r,10);

printf("排序之后的记录: \n");

visit(r,10);

return 0;

}

（2）起泡排序（冒泡排序）：

#include

//对含有n个数的数组进行遍历

void visit(int r[],int n){

for(int i=0;i

printf("%4d",r[i]);

printf("\n");

}

void BubbleSort(int r[], int n){

int count1 = 0, count2 = 0; //count1和count2记载比较次数和移动次数

int bound, exchange= n-1; //第一趟起泡排序的区间是[0, n-1]

while(exchange!=0){ //当上一趟排序有记录交换时

bound = exchange;

exchange = 0;

for(int j=0;j

if(++count1 && r[j] > r[j+1]){ //注意不能写作count1++

int temp = r[j];

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

r[j+ 1] = temp;

count2 = count2 + 3; //1次交换是3次移动操作

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

}

visit(r,10); //每趟排序输出一次，观察记录的变动情况

}

printf("本次排序中的比较次数为%d,移动次数为%d。\n",count1,count2);

}

int main(){

int r[10]={0};

printf("请依次输入10个整数，用空格隔开: \n");

for(int i=0;i<10;i++)

scanf("%d",&r[i]);

printf("排序之前的记录: \n");

visit(r,10);

printf("进行冒泡排序: (每趟排序后的结果如下所示)\n");

BubbleSort(r, 10);

printf("排序之后的记录: \n");

visit(r,10);

return 0;

}

（3）堆排序

#include

typedef int ElementType;

int arr1[11]={0,2,87,39,49,34,62,53,6,44,98};

#define LeftChild(i) (2 * (i) + 1)

void Swap(int* a,int* b)

{

int temp=*a;

*a=*b;

*b=temp;

}

void PercDown(int A[], int i, int N)

{

int child;

ElementType Tmp;

for (Tmp = A[i]; 2*i+1 < N; i = child){

child = 2*i+1; //注意数组下标是从0开始的，所以左孩子的求发不是2*i

if (child != N - 1 && A[child + 1] > A[child])

++child; //找到最大的儿子节点

if (Tmp < A[child])

A[i] = A[child];

else

break;

}

A[i] = Tmp;

}

void HeapSort(int A[], int N)

{

int i;

for (i = N / 2; i >= 0; --i)

PercDown(A, i, N); //构造堆

for(i=N-1;i>0;--i)

{

Swap(&A[0],&A[i]); //将最大元素（根）与数组末尾元素交换，从而删除最大元素，重新构造堆

PercDown(A, 0, i);

}

}

void Print(int A[],int N)

{

int i;

for(i=0;i

{

printf(" %d ",A[i]);

}

}

int main()

{

int arr[10]={2,87,39,49,34,62,53,6,44,98};

Print(arr,10);

printf("\n");

HeapSort(arr,10);

Print(arr,10);

printf("\n");

return 0;

}

7.实验结论及心得体会

（1）算法分析

时间复杂度分析 最好的情况下：正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n) 最坏的情况下：逆序有序,这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n^2) 平均情况下：O(n^2)

选择排序的时间复杂度为O(N^2)。 起泡排序的时间复杂度为O(N^2)。 堆排序的时间复杂度为O(n*logn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是logn，调用了n-1次。

（2）心得体会

通过本次实验我理解了选择排序、起泡排序和堆排序的基本思想，掌握了三种排序方法的具体实现过程，并且编程实现了三种排序方法，增强了对算法时间复杂度的理解与应用。

查看原文