算法

发表于 更新于
  • 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度、空间复杂度的推算方法、常见类型、示例等。
  • 数据结构：基本数据类型，数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。
  • 算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤、示例题目等。

1.0 排序算法

  • 插入排序：
    对于一段数组，从a[1]开始依次插入到前面已经排序好的数组里。
    实现：比较大小，把比待排序元素key大的元素往后移。
    key = a[j];  // 待排序数组
    i = j - 1;
    while (i >= 0 && a[i] > key) {  // 比较大小
        a[i+1] = a[i];  // 比key大的往后挪
        i--;
    }
    a[i+1] = key;
  • 选择排序：
    第一次从数组a[0…LEN-1]中找出最小值，与a[0]交换，第二次从a[1…LEN-1]找最小值与a[1]交换，等等。
    实现：遍历数组，记录最小值及其下标，与a[0~LEN-1]交换
    key = a[i];
    for (j = i+1; j < LEN; j++) {  // 遍历数组i到末尾
        if (a[j] < key) {  // 找出最小值并储存值和索引
        key = a[j];
        tag = j;
        }
    }
    a[tag] = a[i];
    a[i] = key;
  • 归并排序：
    把数组分成前后两半，直到不可再分；然后对已排序好的小数组排序。
    实现：将原数组复制成左右两份，比较左右数组每一项的大小，并给原数组重新赋值。
merge(int start, int mid, int end)
{
    int n1 = mid - start + 1;  // 9/2 = 4, 0-4共5个元素
    int n2 = end - mid;  // 9 - 9/2 = 5, 刚好5个元素
    int left[n1], right[n2];
    int i, j, k;
        
    // 复制数组
    for (i = 0; i < n1; i++)
        left[i] = a[start+i];
    for (j = 0; j < n2; j++)
        right[j] = a[mid+1+j];

    i = j = 0;
    k = start;
    while (i < n1 && j < n2) {
        if (left[i] < right[j])  // 已排序好的小数组再排序
            a[k++] = left[i++];
        else
            a[k++] = right[j++];
    }
    while (i < n1)  // 处理剩余项（已排序好无需比较）
        a[k++] = left[i++];
    while (j < n2)
        a[k++] = right[j++];
}

sort(int start, int end)  
// start, end应为数组下标范围; a[10]传入0, 9
{
    if(start < end) {
        int mid = (start+end) / 2;
        sort(start, mid);  // 分割数组为两半
        sort(mid+1, end);
        merge(start, mid, end);  // 对已排序好的数组排序
    }
}

  • 快速排序：
    找到一个标兵pivot，并把数组按左小右大顺序排到pivot两侧，对左右两侧再排序。
    实现：两个索引从数组前后向中间遍历，每找到一组“左大右小”就交换，直到索引重合（排序完毕）。将pivot与索引位置交换，对左右两组再次排序。和冒泡排序一样属于交换排序。

    // end在数组下标取值范围里  
    int partition(int start, int end)  {  
        int i = start, j = end;  
        // 完全遍历数组，将组内全部元素排序成“左小右大”  
        while (i < j) {  
            while (i < j && a[j] >= a[start])  
                j--;  
            while (i < j && a[i] <= a[start])  
                i++;  
            // 找到一组“左大右小”就交换
            swap(&a[i], &a[j]);  
        }  
        // 交换pivot到组中间  
        swap(&a[start], &a[i]);  
        return a[i];  
    }  
      
    void quick_sort(int start, int end)  
    {  
        if (end > start) {  
            int pivot = partition(start, end);  
            // 如果把pivot变成pivot-1，pivot+1变成pivot就会死循环，为什么？  
            quick_sort(start, pivot);          quick_sort(pivot+1, end);  
        }  
    }

  • 算法

    • 有限指令集
    • 接受输入或不需要输入
    • 产生输出
    • 一定在有限步骤后终止
    • 每条指令必须
      1. 明确无歧义
      2. 计算机处理范围内（如递归别爆内存）
      3. 伪代码，不依赖特定语言和实现手段
    • 例子
/* 将N个整数List[0]...List[N-1]进行非递减排序 */
void SelectionSort(int List[], int N) 
{
    for (i = 0; i < N; i++) {
        MinPosition = ScanForMin( List, i, N–1 );
        /* 从List[i]到List[N–1]中找最小元,并将其位置赋给MinPosition */
        Swap( List[i], List[MinPosition] );
        /* 将未排序部分的最小元换到有序部分的最后位置 */
    }
}
  • 什么是好的算法
    • 空间复杂度S(n)和时间复杂度T(n)
    • S(n)：递归PrintN(int N)占用跟N大小呈线性增长；而循环始终占用1个函数空间
    • T(n)：多项式例子，直接算的方法执行(1+2+…+n)次乘法，巧妙方法只执行n次乘法
      • 只关心 Tworst(n)和Tavg(n)T_{worst}(n) \text{和} T_{avg}(n) 最坏情况更容易统计