一、实验目的

1. 熟悉C/C++语言的集成开发环境;
2. 掌握算法的概念；
3. 了解问题的求解方法；
4. 理解递归思想，学会编写递归。

二、实验原理

1. 算法（algorithm）
   一个算法是对特定问题求解步骤的一种描述，它是指令的有限序列。算法具有下列 5个特征: 输入（input）；输出（output）；确定性（definiteness）；能行性（effectiveness）；有穷性（finiteness）。
2. 问题求解过程
   理解问题（understand the problem）；
   设计方案（devise a plan）；
   实现方案（carry out theplan）；
   回顾复查（look back）。
3. 递归（recursive）
   递归定义是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分：基础情况（base case）和递归部分。基础情况以直接形式明确列举新事物的若干简单对象，递归部分给出由简单（或较简单）对象定义新对象的条件和方法。

三、实验内容

1.对于数组A[0…n-1]，用插入法实现非降序排序。

实验原理：
插入排序的基本思想是每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。插入排序算法的

一般步骤：
(1)从第一个元素开始，该元素可以认为已被排序；
(2)取出下一个元素，在已经排序的元素序列中从后向前扫描；
(3)如果已排序元素大于新元素，将已排序元素移到下一个位置；
(4)重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
(5)将新元素插入到该位置后，重复2~5.

实验原理：
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

实验程序：

#include <stdio.h>
#include <stdlib.h>

using namespace std;

int main()
{
    int i,j,k,n;//循环变量i,j,k以及用户定义数组长度
    printf("请输入你要排序数据的个数：");
    scanf("%d",&n);
    //根据用户输入的数据个数定义待排序数组以及正确排序数组
    int a[n],b[n];
    printf("已随机生成1-100的%d个随机数，排序完成：\n\n",n);
    for(i=0;i<n;i++)
    {
        a[i]=rand() % 100 + 1;//1-100随机数构成数组a
        printf("%d  ",a[i]);
        //打印输出原始乱序队列
    }

    b[0]=a[0];   //第一个数默认有序
    for(i=1;i<20;i++)   //依次选定一个待排序数字
        for(j=0;j<20;j++)  //与有序数组分别对比，寻找插入位置
        {
            if(a[i]<=b[j])
            {
                for(k=19; k>=j+1; k--)
                    b[k] = b[k-1];
                b[j]=a[i];
                break;
            }
            //如果待排序数字比当前的b数组某个元素小，则先将所有元素后移一位再插入乱序数组
            if(b[j]==0)
            {
                b[j]=a[i];
                break;
            }
            //如果待排序数字没有碰见比自己大的（自己最大），则直接放在最后一位
        }
    printf("\n");
    for(i=0;i<20;i++)
        printf("%d  ",b[i]);  //输出已排序数组
    return 0;
}

实验测试：

1. 使用20个数据测试：
   
2. 使用25个数据测试：
   
   算法复杂度分析：
   

2.对于数组A[0…n-1]，用冒泡法实现非降序排序。

实验原理：
从数组头部开始，不断比较相邻的两个元素的大小，让较大的元素逐渐往后移动（交换两个元素的值），直到数组的末尾。经过第一轮的比较，就可以找到最大的元素，并将它移动到最后一个位置。第一轮结束后，继续第二轮。仍然从数组头部开始比较，让较大的元素逐渐往后移动，直到数组的倒数第二个元素为止。经过第二轮的比较，就可以找到次大的元素，并将它放到倒数第二个位置。以此类推，进行n减一（n 为数组长度）轮“冒泡”后，就可以将所有的元素都排列好。

实验原理：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

实验程序：

#include <stdio.h>
#include <stdlib.h>
//函数声明
int bubble_sort(int a[],int n);  //一般冒泡排序
int bubble_sort_better(int a[],int n);  //上面的升级版

int  main()
{
    int i,n;
    printf("请输入你要排序数据的个数：\n");
    scanf("%d",&n);
    //根据用户输入的数据个数定义数组大小
    int num[n];
    printf("已随机生成1-100的%d个随机数，排序完成：\n",n);
    for(i=0;i<n;i++)
    {
        num[i]=rand() % 100 + 1;
        printf("%d  ",num[i]);
    }
    printf("\n");
    //调用冒泡排序函数，传入待排序数组，以及数组长度
    bubble_sort(num, n);
    //将排序完成的数组顺序输出
    for(i=0; i<n; i++)
        printf("%d  ", num[i]);

    printf("\n");
    return 0;
}

int bubble_sort(int a[],int n)
{
    int i,j;  //i，j 循环变量
    for(i=0; i<n-1; i++)  //从第一个数组元素开始遍历
    {
        for(j=0; j<n-1-i; j++)
        //由于是两个数的比较，以及最大数每循环一次后位置最后，所以内循环只到n-1
        {
            if(a[j] > a[j+1]) //跑一遍完成最大值的置后，所以下一次就不用排最后的值了
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1]=temp;
            }
        }
    }
    return 0;
}
//冒泡排序的优化改进版
int bubble_sort_better(int a[],int n)
{
    int i,j,flag;  //多了一个用于标记的变量flag
    for(i=0; i<n-1; i++)
    {
        flag=1;  //每次循环都将flag置1
        for(j=0; j<n-1-i; j++)
        {
            if(a[j] > a[j+1])
            {
                flag=0;  //一次循环出现需要排序的时候flag置0
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1]=temp;
            }
        }
        if(flag) break;
        /*如果一边跑完，没有换位，说明此时的数组有序了。
        直接结束排序，不用完成所有的for循环*/
    }
    return 0;
}

实验测试：

• 使用25个数据测试：
  
• 使用20个数据测试：
  
  算法复杂度分析：
  

3. 对于数组A[0…n-1]，用快速排序实现非降序排序。

实验原理：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。该方法的基本步骤是：
(1)先从数列中取出一个数作为基准数。
(2)分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
(3)再对左右区间重复第二步，直到各区间只有一个数。
x=a[0]

实验原理：
一趟快速排序的算法是：
1.设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2.以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3.从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
4.从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
5.重复第3、4步，直到ij； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，ij这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

实验程序：

#include <stdio.h>
#include <stdlib.h>
void display(int a[], int n)
{
    int i;
    for(i = 0; i < n; i++)
    {
        printf("%d  ", a[i]);
    }
    printf("\n\n");
    return ;
}
void QuickSort(int *p, int low, int high)  //传入排序数组arr，数组下限low，上限high
{
    if (low < high)  //保证传入下限低于上限
    {
        int i = low;
        int j = high;   //i,j分别用于从左边和右边遍历
        int k = p[low];   //选定最左边的数字作为默认比较值
        //所有操作都要在i<j的前提下进行，当i>=j，一次排序结束
        while (i < j)
        {
            while(i < j && p[j] >= k)     // 从右向左找第一个小于k的数
            {
                j--;
            }
            //找到之后，准备换位置
            if(i < j)
            {
                p[i++] = p[j];
            }
            //用大于等于标准值的数字换掉小于标准值的数字
            while(i < j && p[i] < k)      // 从左向右找第一个大于等于k的数
            {
                i++;
            }
            //找到之后，准备换位置
            if(i < j)
            {
                p[j--] = p[i];
            }
            //用小于等于标准值的数字换掉大于标准值的数字
        }
        p[i] = k;
        //将一开始保留的标准值，放在i和j相遇的位置，实现左边小于标准值，右边大于标准值
        // 递归调用
        QuickSort(p, low, i - 1);     // 排序k左边
        QuickSort(p, i + 1, high);    // 排序k右边
    }
}
// 主函数
int main()
{
    int i,n;
    printf("请输入你要排序数据的个数：");
    scanf("%d",&n);
    //根据用户输入的数据个数定义数组大小
    int num[n];
    printf("已随机生成1-100的%d个随机数，排序完成：\n\n",n);
    for(i=0;i<n;i++)
    {
        num[i]=rand() % 100 + 1;
    }
    printf("排序前的数组\n");
    display(num, n);
    QuickSort(num, 0, n-1);  // 快速排序
    printf("排序后的数组\n");
    display(num, n);
    return 0;
}

实验测试：

• 使用25个数据测试：
  

• 使用20个数据测试：
  
  算法复杂度分析：

1. 快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。
2. 理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。
3. 最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。
4. 可以证明，快速排序的平均时间复杂度也是O(nlog2n)。因此，该排序方法被认为是目前最好的一种内部排序方法。
5. 从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log2(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(log2n)。