算法笔记——排序、模拟

发布于 2021-02-25  0 次阅读



本文原写于2020年1月,因为当时对 Markdown 和 \LaTeX 不太熟悉导致排版有些乱,为了从排版中找到教训,就不修改了。

一 复杂度理论

1.算法

1.定义:算法是指对特定问题求解步骤的一种描述。

2.算法的特性:

  1. 有穷性:算法是由若干条指令组成的有穷数列,总是在执行若干次后结束,不可能永不停止。

  2. 确定性:每条语句有确定的含义,无歧义。

  3. 可行性:算法在当前环境条件下可以通过有限次运算实现。

  4. 输入和输出:有零个或多个输入,一个或多个输出。

2. 时间复杂度

1. 定义:算法运行所需要的时间。

一般将算法基本运算的执行次数作为时间复杂度的度量标准

2. 举例:

int getSum(int n)
{
    sum = 0;
    for(i = 1;i <= n; i++)
        for(j = i;j <= n; j++)
            sum += i * j;
    return sum;
}

5 行的 for 每次执行需要 n 次操作;

这个 for 一共被执行 n 遍。

n + n + · · · + n = n^2

int getSum(int n)
{
    sum = 0;
    for(i = 1;i <= n; i++)
        for(j = i;j <= n; j++)
            sum += i * j;
    return sum;
}

1 + 2 +···+ n = n * (n + 1) / 2

3. O记号:O 记号是“最坏情况下,程序执行操作的总次数”。

  • 如果是多个项相加,只取最大的项。

  • 省略掉所有的常数

  • 复杂度只考虑数量级,例如 2^n + 233n^2O(2^n).

例如 :

  • $2n(n+1)$ 是 $O(n^2)$ 的。

  • $3n−10$ 是 $O(n)$ 的。

  • $n^2 +n+ 1$ 是 $O(n^2)$ 的。

  • $233$ 是 $O(1)$ 的。

3.空间复杂度:

1. 定义:算法占用的空间大小。

一般将算法的辅助空间作为衡量空间。

空间复杂度的本意是指算法在运行过程中占用了多少存储空间。

2. 算法占用的存储空间包括:

  1. 输入/输出数据所需空间。

  2. 算法本身所占空间。

  3. 额外需要的辅助空间。

二 排序

1.定义:

设有记录序列 {K_1,K_2,......,K_n},若存在某种确定的关系 K_x <= K_y <= ...... <= K_z,其中 1<=x, y, z<=nx,y,z 各不相同,则将记录序列 {R1,R2,...,Rn} 排成按关键字有序的序列 {R_x,R_y,......,R_z} 的操作,叫做排序(sort)

其中排序所依赖的关系是任意的,通常使用小于(递增)、大于(递减)等关系。

2.桶排序:

1. 定义:

假定:输入是由一个随机过程产生的 [0, 1) 区间上均匀分布的实数。将区间 [0, 1) 划分为 n 个大小相等的子区间(桶),每桶大小 1/n:[0, 1/n), [1/n, 2/n), [2/n, 3/n),…,[k/n, (k+1)/n ),…n 个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入 0 ≤A[1..n] <1 辅助数组 B[0..n-1]​ 是一指针数组,指向桶(链表)。

2. 例题:

洛谷P1271

3. 插入排序:

1. 工作原理:

每次将一个待排序的数据按照其关键字的大小插入到一个已经完成排序的有序序列中,直到全部记录排序结束。

2. 直接插入排序:

1. 算法思路:

通过构造有序数列,对于未排序数据,在已排序序列中从后向前扫描,从而找到相应的位置并插入。

在从后向前扫描的过程中,需要反复把已排序的元素逐步向后挪位,为待插入的新元素提供插入空间。

2. 步骤

  1. 设置 i = 2.

  2. 将代插入记录 r[i] 放入编号为 0 的结点(即下标为 0 的结点),即 r[0] = r[i];并令 j = i - 1,从第 j 个记录开始向前查找插入位置。

  3. r[0].key >= r[j].key ,执行第五步;否则执行第四步。

  4. 将第j个记录后移,即 r[j + i] = r[j];并令 j = i - 1;执行第三步。

  5. 完成插入记录:r[j + 1] = r[0]i = i + 1。若 i > n,则排序结束,否则执行第二步。

3. 代码实现:

void SInsertSort(SqList &L)
{
    for(int i = 2; i <= L.length; i++)
      if(L.r[i] <= L.r[i - 1])
       {
          L.r[0] = L.r[i];
          L.r[i] = L.r[i - 1];
          for(int j = i - 2;L.r[0] <= L.r[j]; j--)
             L.r[j + 1] = L.r[j];
          L.r[j + 1] = L.r[0];
       }
}

4. 算法分析:

  1. 时间复杂度:直接插入排序方法是一个两层嵌套循环结构,其外层循环执行n-1次,而内层循环的执行次数则取决于待排序列记录初始的排列情况。
  • 最好情况:当排序列为正序时,达到该算法的最好情况。此时每趟操作只需进行一次比较和2次记录的移动。因此算法总比较次数和总移动次数分别为n-12(n-1)。即此时算法的时间复杂度为O(n)

  • 此时第i个记录要与之前i-1个记录进行比较,并且每次比较就要对记录做一次移动,所以算法的总比较次数和总移动次数分别为 ∑\limits_{(2,n)}^i=(n+2)(n-1)/2∑\limits_{(2,n)}^i=(i+i)=(n+4)(n-1)/2。因此时间复杂度为 O(n^2)

  • 平均情况:假设待排序列中各种可能排列的概率相同,则第i个记录平均要与前 (i-1)/2 个记录进行比较,记录移动的次数为 (i+1)/2。因此,平均情况下算法总的比较次数为 ∑\limits_{(2,n)}^{(i-1)/2}=(n+2)(n-1)/4,而记录的总移动次数为 ∑\limits_{(2,n)}^{(i-1)/2}=(n+4)(n-1)/4。所以直接插入算法的平均时间复杂度为 O(n^2)

  • 总体而言,当待排序列基本有序或者记录的数量较少时,直接插入排序有非常良好的时间效率,是最佳的排序方法。但是当待排记录数量较多时或者排序列接近倒序时,其算法时间效率将会大大降低。

  1. 空间复杂度:由于直接插入排序只需要一个作为暂存待插入记录的存储单元,因此其空间复杂度为 O(1)

  2. 稳定性:该算法是稳定的排序方法。

2. 交换排序:

交换排序是一类借助比较和交换进行排序的方法。其中交换是指对序列中两个记录的关键字进行比较,如果排列顺序不对则对换两个记录在序列中的位置,交换排序的特点是:将关键字较大的记录想序列的一端移动,而关键字较小的记录想序列的另一端移动。

1. 冒泡排序:

1. 算法思路:

通过对待排序元素中相邻元素间关键字的比较和交换,使关键字最大的元素如冒泡一样逐渐“上浮”。

2. 冒泡排序的具体操作步骤如下:

  1. 从存储 n 个待排序元素的表位开始,并令 j = n

  2. j<2,则排序结束。

  3. 从第一个元素开始进行两两比较,令 i = 1

  4. i >= j,则一趟冒泡排序结束,j = j - 1;待排序表的记录数 - 1,转到第二步。

  5. 比较 r[i].keyr[i+1].key,若 r[i].kry<=r[i+1].key,则不交换,转到第七步。

  6. r[i].key > r[i+1].key时,将 r[i]r[i+1]交换。

  7. i = i + 1,转到第四步继续比较。

3. 代码实现:

void BubbleSort (SqList &L)
{
    for (int j = 0; j < L.length - i; j++)
    {
        if (L.r[j] > L.r[j + 1])
        {
            int t = L.r[j];
            L.r[j] = L.r[j + 1];
            L.r[j + 1] = t;
        }
    }
}
void main ()
{
    SqList sl;
    QSort q;
    q.CreateSqList(sl);
    cout << "冒泡排序的结果如下:" << endl;
    q.BubbleSort(sl);
    q.SqListDisplay(sl);
}//end main

4. 算法分析:

  1. 时间复杂度:
  • 冒泡排序总共需要进行 n-1 趟冒泡,对 j 个记录的表进行一趟冒泡需要 j-1 次关键字比较。则平均的总比较次数为: \sum\limits_{(j=2,n)}^{(j-1)}=1/2\times n\times (n-1)。因此,平均时间复杂度为 O(n^2)

  • 最好情况:待排序的记录序列为正序,算法只执行一趟,进行n-1次关键字的比较,不需要进行移动,此时排序效率最高,时间复杂度为 O(n)

  • 最坏情况:待排序的记录序列为反序,每趟排序在无序序列中只有一个最大的记录被交换到最终的正确位置,故算法要执行 n-1 趟,第 i\le n 趟排序执行了 n-i 次关键字的比较和 n-i 次记录的交换。这样,关键字的比较字数为:\sum\limits_{(i=1,n-1)}^{(n-i)}=1/2\times n\times (n-1),记录的移动次数为:3\sum\limits_{(i=1,n-1)}^{(n-i)}=3/2\times n\times(n-1),因此,时间复杂度为 O(n^2)

  • 算法只执行一趟,进行 n - 1 次关键字的比较,不需要进行移动,此时排序效率最高,时间复杂度为 O(n)

  1. 空间复杂度:冒泡排序只需要一个记录的辅助空间,用来作为记录交换的暂存单元。

  2. 稳定性:冒泡排序是一种稳定的排序方法。因为比较和交换是在相邻单元进行的,如果关键字值相同,则不发生交换。

2. 快速排序:

快速排序(Quick Sort)是1962年由Hore提出的一种算法,也称为分区交换排序

1. 算法思想

通过对关键字的比较和交换,以待排序列中的某个数据作为支点(或称枢轴量),将待排序列分为两个部分,其中左半部分数据小于等于支点,右半部分数据大于等于支点。然后,对左右两部分分别进行快速排序的递归处理,直到整个序列按关键字有序为止。

2. 操作步骤

  1. 如果待排子序列中元素的个数等于 1,则排序结束;否则以 r[low]为支点,按照如下方式进行一次划分。
  • 设置两个搜索指针:low是向后搜索指针,初始指向序列第一个结点;high是向前搜索指针,初始指向最后一个结点;取第一个记录为支点,low位暂时取值为支点 pivotkry = r[low]key

  • low = high,枢纽空位确定为low,一次划分结束。

  • low < highr[high].key >= pivotkey,则从high所指定的位置向前搜索:high = high - 1。重新执行此步;否则若有low < high并且有r[high].key < pivotkry,则设置high为新的支点位置,并交换r[high].keyr.[low]key,然后令low = low + 1,执行下一步,若有low >= high,执行上一步。

  • low < highr[high].key <= pivotkey。则从low所指的位置开始向后搜索:low = low + 1,重新执行此步;否则若有low < high并且有r[low].key > pivortkry,则设置low为新的支点位置,并交换r[high].keyr[low].key,然后令high = high - 1,执行第三步;若有low >= high,则执行第二步。

  1. 对支点左半子序列重复Step1。

  2. 对支点右半子序列重复Step2。

3. 代码实现:

1.:

int Partition(SqList &L, int low, int high)
{
    int pivotkey;
    L.r[0] = L.r[low];  //用子表的第一个记录作枢轴记录
    pivotkey = L.r[low];    //关键字
    while(low < high)   //从表的两端交替向中间扫描
    {
        while(low < high && L.r[high] >= pivotkey)  --high;
        L.r[low] = L.r[high];   //将比枢轴小的记录移至低端
        while(low < high && L.r[low] <= pivotkey)   ++low;
        L.r[high] = L.r[low];   //将比枢纽小的记录移至低端
    }
    L.r[low] = L.r[0];  //枢轴记录到位
    return low;
}
//主程序(按分区对子程序进行调用):
void QuickSort1(SqList &L, int low, int high)
{
    int mid;    //接收枢纽位置
    if(low < high)
    {
        mid = Partition(L, low, mid - 1);   //对低子表进行排序
        QuickSort1(L, mid + 1, high);   //对高子表进行排序
    }
}

2.简化版:

void QuickSort2(int left, int right)
{
    int i, j, t, temp;
    if(left > right)    return;
    temp = a[left]; //用temp存储基准数
    i = left, j = right;
    while(i != j)
    {
        //先从右往左找
        while(a[j] >= temp && i < j)    j--;
        //再从左往右找
        while(a[i] <= temp && i < j)    i++;
        //交换两个数组中的位置
        if(i < j)   //当i和j没有相遇时
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    //最后将基准数归位
    a[left] = a[i];
    a[i] = temp;
    QuickSort2(left, i -1); //继续处理左边的,这里是一个递归的过程
    QuickSort2(i + 1, right);   //继续处理右边的,这里是一个递归的过程
    return;
}

4. 算法分析:

  1. 时间复杂度:
  • 快速排序通常被认为是在同数量级(O(n\log_2 n))排序算法中平均性能最好的算法。设 T(n) 为对含有 n 个记录的待排序列进行排序所需要的时间。

  • 最好情况:当每次支点都将待排序列分成两个相同的子列时,快速排序达到最高效率,此时:

    T(n)<=n+2T(n/2)<=n+2(n/2+2t(n/4))=2n+4T(n/4)<=2n+4(n/4+T(n/8))=3n+8T(n/8)<=...<=n\log_2 n+nT(1)=O(n\log_2 n)

  • 最坏情况:当每次划分都只得到一个子列时,快速排序的执行过程则类似于冒泡排序,此时快速排序的效率最低,时间复杂度为 O(n^2)

  • 为了避免出现最坏情况,要对快速排序算法进行一定的改进。通常的改进方法是选取支点时选最左、最右和中间 3 个元素中取值处于中间的元素作为支点。

  1. 空间复杂度:由于快速排序的过程是一个递归过程,每层递归时都需要用栈来存放指针和相应的参数,且递归的层数与其二叉树的深度一致。因此其空间复杂度平均为 O(\log_2 n)

  2. 稳定性:以 {55, 49, 65, 97, 76, 52, 50, 49(1)} 为例,该序列经过快速排序得到有序序列为 {49(1), 49, 50, 52, 55, 65, 76, 97} ,因此可以看出快速排序是不稳定的排序方法。

4. 选择排序:

  • 选择排序(Selection Sort) 是一类借助“选择”进行排序的方法。

  • 选择排序的基本思想:每一趟从待排序列中选取一个关键字最小的记录,也即第一趟从n个记录中选取关键字最小的记录,第二趟从剩下的n-1个记录中选取关键字最小的记录。

1. 简单选择排序:

简单选择排序(Simple Selection Sort) 是选择排序中最简单的一种排序算法。

1. 算法思想:

第一趟从 n 个记录中选出关键字最小的记录和第一个记录交换;第二趟从第二个记录开始的 n-1 个记录中再选出关键字最小的记录和第二个记录交换;如此第 i 趟则从第 i 个记录开始的 n-i+1 个记录中选出关键字最小的记录与第 i 个记录交换,直到整个序列按关键字有序。

2. 操作步骤:

  1. 创建一个辅助变量j用于存放每次遍历关键字最小的记录的下标。设置变量为 i=1

  2. 遍历第 i 个记录到底 L.length 个记录。选择一个关键字最小的记录,将其下标保存至 j 中。

  3. 若第 i 个记录的关键字小于 j 中保存的记录为关键字,则交换这两个记录。

  4. i = i + 1,若第 i 个记录的关键字小于 j 中保存的记录的关键字,则交换这两个记录。

3. 代码实现

子程序(选择key最小记录)

int SelectMinKey(SqList &L, int n)
{
    int min = n;
    int minkey; //最小值
    minkey = L.key[n];
    for(int i = n + 1; i <= L.length; i++)
        if(L.key[i] < minkey)
        {
            minkey = L.key[i];
            min = i;
        }
    return min;
}

主程序(调用子程序对顺序表L做简单选择排序)

void SelectSort(SqList &L)  //对顺序表L做简单选择排序
{
    int j, t;
    for(int i = 1;i <= L.length; i++)
    {
        j = SelectMinkey(L, i)  //在L.key[i]--L.key[L.length]中选择最小的记录并将其地址赋给j
        if(i != j)  //交换记录
        {
            t = L.key[i];
            L.key[i] = L.key[j];
            L.key[j] = t;
        }
    }
}

4. 算法分析

  1. 时间复杂度:简单选择排序的过程中,记录移动的次数越少,且分别在待排序为正序和逆序时取到记录移动次数的最大值和最小值。但是无论待排序列初始状态如何,其关键字的比较次数都相同,总比较次数为:1/2n(n-1),算法的时间复杂度仍然为 O(n^2)

  2. 空间复杂度:简单选择排序算法只需要一个作为暂存待插入记录的吹你出单元,其空间复杂度为 O(1)

  3. 稳定性:简单选择排序是稳定的排序方法。

5. 归并排序:

归并排序(Merge Sort) 是一类借助“归并”进行排序的方法。归并的含义是将两个或两个以上的有序序列归并成一个有序序列的过程。

1.二路归并排序(2-way Merge Sort)

1.算法思想:

将待排序的n个元素看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2]个长度为2或1(最后一个有序序列的长度可能为1)的有序子序列;再两两归并,得到[n/4]个长度为4或小于4(最后一个有序序列的长度可能小于4)的有序子序列;在两两归并,……直至得到一个长度为n的有序序列。

2.操作步骤

  1. 将待排序列划分为两个长度相当的子序列。

  2. 若子序列长度大于 1,则对子序列执行一次归并排序。

  3. 执行下列步骤对子序列两两合并成有序序列。

  • 创建一个辅助数组 temp[],假设两个子列的长度分别为 uv,两个子列的下标为 0\sim u,u+1\sim v+u+1。设置两个子表的起始下标和辅助数组的起始下标:i = 0; j = u + 1; k = 0

  • i > uj > v + u + 1,说明其中一个子表已经合并完毕,直接执行第四步。

  • 选取 r[i]r[j] 中关键字较小的存入辅助数组 temp[]:若 r[i].kry < r[j].key,则 temp[k] = r[i]; i++; k++;否则 remp[k] = r[j]; j++; k++,返回执行上一步。

  • 将尚未处理完的子表元素依次存入 temp[] ,结束合并,并将结果返回。

3.代码实现

子程(一趟归并排序算法):

void Merge(int* SR, int* TR, int i, int m, int n)
{
    for(int j = m + 1, k = i; i <= m && j <= n; k++)
    {
        if(SR[i] <= SR[j])      TR[k] = SR[i++];
        else        TR[k] = SR[j++];
    }
    if(i <= m ) //将剩余的SR[i...m]赋值到TR
        for(int a = i; a <= m; a++)     TR[k++] = SR[a];
    else if(j <= n) //将剩余的SR[j...n]复制到TR
        for(int b = j; b <= n; b++)     TR[k++] = SR[b];
}

主程序(归并排序递归算法):

void MergeSort1(int* SR, int* TR, int s, int t)
{
    int TR2[100];
    int m;
    if(s == t)      TR1[s] = SR[s];
    else
    {
        m = (s + t) / 2;    //将SR[s...t]平分为SR[s...m]和SR[m+1...t]
        MergeSort1(SR, TR2, s, m);  //递归地将SR[s...m]归并为有序的TR2[s...m]
        MergeSort1(SR, TR2, m + 1, t);  //递归地将SR[m+1...t]归并为有序的TR2[m+1...t]
        Merge(TR2, TR1, s, m, t);   //将TR2[s...m]和TR2[m+1...t]归并到TR1[s...t]
    }
}

4.算法分析:

  1. 时间复杂度:对于二路归并排序,设有 n 个元素的表 r[],若 h 为归并子序列的长度,则每趟归并操作需要进行 [n/(2h)] 次归并,并把结果存放到新的表 r1[]中,这需要 O(n) 的时间。因此整个二路并归排序的时间复杂度为 O(nlog2 n)

  2. 空间复杂度:由于二路并归排序需要一个新的表 r1[]存储一趟归并后的记录,因此其空间复杂度为 O(n)

  3. 稳定性:归并排序是稳定的排序方法。

三 模拟

  • 模拟是一类算法的统称:题目要你干什么,你就照着用最暴力的方式干一遍,判断结果。

  • 模拟是最朴素的算法。几乎所有题目都可以通过模拟拿到一些分数。


大变に气分がいい