前言回顾

        冯·诺依曼计算机的构成包括：运算器；控制器；存储器；输入设备；输出设备；
        程序计数器PC存储的是下一条机器指令的地址；
        操作系统的资源管理主要包括：(外部)设备管理、处理机 (CPU) 管理、存储 (内存) 管理、文件 (磁盘) 管理；
        在单CPU系统中，分时操作系统可以实现程序的并发执行。

目录

一、算法类问题求解框架

        1.算法及特点

二、内排序

        1.冒泡排序

        2.二路归并排序

三、外排序

一、算法类问题求解框架

        1.算法及特点

        算法：描述求解问题方法的步骤集合
        特点：确定性；可执行性；可终止性；有零个或多个输入；有一个或多个输入。

        算法类问题求解的一般步骤：
        1.问题抽象及数学建模；2.算法策略设计；3.算法的数据结构和控制结构设计；
        4.算法的实现；5.算法的分析。

二、内排序

        内排序：所有待排序记录可以一次性装入内存中进行的排序。

        1.冒泡排序

        冒泡排序——穷举法，也称蛮力法，是一种基于遍历的方法。
        冒泡排序思想：

        示例代码：

void BubbleSort(int r[],int n)//升序排序
{
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(r[i]>r[j]){
                int temp = r[i];
                r[i] = r[j];
                r[j] = temp;
            }
    }
}

        改进后的示例代码：

void BubbleSort_1(int r[],int n)//改进一，升序排序
{
    int exchange=1,i=1,j,temp;
    while(exchange){
        exchange=0;
        for(j=0;j<n-i;j++){
            if(r[j]>r[j+1]){
                temp = r[j];
                r[j] = r[j+1];
                r[j+1] = temp;
                exchange = 1;
            }
        }
        i++;
    } 
}

void BubbleSort_2(int r[],int n)//改进二，升序排序
{
    int exchange=n-1,bound=n-1,j,temp;
    while(exchange){
        exchange = 0;
        for(j=0;j<bound;j++){
            if(r[j]>r[j+1]){
                temp = r[j];
                r[j] = r[j+1];
                r[j+1] = temp;
                exchange = j;  
            }
        }
        bound = exchange;
    }
}

        冒泡排序的分析
        时间复杂性：
                1.最坏情况：n(n-1)/2 = O(n^2);
                2.最好情况：n-1 = O(n);

                3.平均情况：O(n^2)。
        空间复杂性：
                1.输入空间：O(n)；
                2.辅助空间：O(1)。

        2.二路归并排序

        算法思想——分治法：将一个难以直接解决的大规模原问题划分成k个可以直接解决的小规模子问题，分别求解各个子问题，再合并子问题解得到原问题解。

        示例代码：

void MergeSort(int r[],int p[],int s,int e)//归并排序，升序排序
{
    int m;
    if(s == e) return;
    else{
        m = (s+e)/2;
        MergeSort(r,p,s,m);
        MergeSort(r,p,m+1,e);
        Merge(r,p,s,m,e);
    }   
}
void Merge(int r[],int p[],int s,int m,int e)//归并，升序
{
    int i,j,k;
    i = s;
    while(i<=m) p[i] = r[i++];
    i = sl
    j = m+1;
    k = s;
    while(i<=m && j<=e){
        if(p[i]<=r[j]) r[k++] = p[i++];
        else r[k++] = r[j++];
    }
    while(i<=m) r[k++] = p[i++];
}

        二路归并排序的分析
        时间复杂性：
                1.最坏情况：O(nlogn);

                2.最好情况：O(nlogn);
                3.最坏情况：O(nlogn);

        空间复杂性：

                1.输入空间：O(n);

                2.辅助空间：O(n);

三、外排序

        外排序的基本算法思想：排序-归并。
        排序-归并——分治法：第一阶段，排序，根据可用内存，将外存的记录分成若干段，将每段依次读入内存并利用内排序进行排序，再将排序后每段写入外存。排序后的有序段称为归并段。第二阶段，归并，根据可用内存，将归并段依次读入内存，进行归并，再写入外存，逐渐得到更大的归并段，直至得到所有记录的归并段即有序段。
      对同一文件进行“排序-归并”外排序时，读/写外存次数与归并趟数成正比，我们可以通过增加归并的个数，即多路归并来减少归并趟数。但在减少归并趟数的同时，内部归并的时间将增加。那我们不能简单地内部归并排序，于是我们引入了败者树。