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

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 <stdio.h>
//对含有n个数的数组进行遍历
void visit(int r[],int n){
    for(int i=0;i<n;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<n-1;i++){ //对n个记录进行n-1趟选择排序
        index= i;
        for(j=i+ 1;j<n;j++){ //在无序区中查找最小记录
            if (r[j]<r[index])
            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<stdio.h>
//对含有n个数的数组进行遍历
void visit(int r[],int n){
    for(int i=0;i<n;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<bound;j++) //一趟起泡排序区间是[0, bound]
            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<stdio.h>
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<N;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）心得体会

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