算法注释

2025-05-24

算法注释

我正在edx.org上学习CS50：计算机科学导论。我发现，通过完成、重写和分享笔记，复习所学知识是一种很好的方式。

注意：大 O 符号可以理解为“大约”，它表示算法的运行时间。在 C 语言示例中，n相当于 ，sizeof(arr)/sizeof(arr[0])在 JavaScript 中则转换为arr.length。

第三周是关于算法的。😺

目录

线性搜索

从左到右遍历数组以搜索目标元素。

伪代码示例#1：

Repeat, starting at the first element:
    If the element is the target element, stop
    Else, move to the next element
Enter fullscreen mode Exit fullscreen mode

伪代码示例#2：

For i from 0 to n–1
    If i'th element is target_element
        Return true
Return false
Enter fullscreen mode Exit fullscreen mode

C 语言示例：

bool linearSearch(int arr[], int n, int target) 
{ 
    for (int i = 0; i < n; i++) 
        if (arr[i] == target) return true;
    return false; 
}
Enter fullscreen mode Exit fullscreen mode

JavaScript 示例：

linearSearch = (arr, target) => {
    for (let i = 0; i < arr.length; i++)
        if (arr[i] === target) return true;
    return false;
}
Enter fullscreen mode Exit fullscreen mode

线性搜索算法

  • 最坏情况： 如果目标元素是最后一个元素，或者它不在数组中，
    则必须遍历整个数组。 用大 O 表示法，就是O(n)。n

  • 最佳情况：
    目标元素是第一个元素。
    用大 O 表示法，它转换为Ω(1)。

二分查找

通过每次将搜索范围缩小一半来找到目标元素。确保使用二分搜索算法的数组已排序，否则无法对其内容做出任何假设。

伪代码示例#1：

Repeat until the (sub)array is of size 0:
    Calculate the middle point of the current (sub)array
    If the target element is the middle element, stop
    Else if it's less than the middle: 
        End point is now just to the left of the current middle, repeat
    Else if it's greater than the middle: 
        Start point is now just to the right of the current middle, repeat
Enter fullscreen mode Exit fullscreen mode

伪代码示例#2：

If no items
    Return false
If middle item is target_element
    Return true
Else if target_element < middle item
    Update end point
    Search left half
Else if target_element > middle item
    Update start point
    Search right half
Enter fullscreen mode Exit fullscreen mode

C 示例（递归）：

int binarySearch(int arr[], int target, int start, int end) 
{ 
    if (end >= start) { 
        // instead of (start+end)/2 to avoid overflow
        int mid = start+(end-start)/2; 
        if (arr[mid] == target) return mid; 
        else if (arr[mid] > target) return binarySearch(arr, target, start, mid-1); 
        else return binarySearch(arr, target, mid+1, end); 
    } 
    return -1; 
}
Enter fullscreen mode Exit fullscreen mode

JavaScript 示例（递归）：

binarySearch = (arr, target, start, end) => {   
    if (end >= start) {
        let mid = Math.floor((start+end)/2);
        if (arr[mid] === target) return mid;
        else if(arr[mid] > target) return binarySearch(arr, target, start, mid-1); 
        else return binarySearch(arr, target, mid+1, end); 
    }
    return false;
}
Enter fullscreen mode Exit fullscreen mode

二分查找算法

  • 最坏情况：
    为了找到目标元素，不得不反复将列表中的n元素一分为二，因为目标元素出现在最后一次除法的末尾，或者不在数组中。
    用大 O 表示法，它相当于O(log n)。

  • 最佳情况：
    目标元素位于数组的中点，因此我们可以在开始搜索后立即停止。
    用大 O 表示法，它等于Ω(1)。

冒泡排序

以冒泡方式排序：将较高的值移向数组的右侧，将较低的值移向左侧。

伪代码示例#1：

Set swap counter to a non-zero value
Repeat until the swap counter is equal to 0:
    Reset swap counter to 0
    Look at each adjacent pair:
        If two adjacent elements are not in order:
            Swap them
            Add one to the swap counter
Enter fullscreen mode Exit fullscreen mode

伪代码示例#2：

Repeat until no swaps
    For i from 0 to n–2
        If i'th and i+1'th elements out of order
            Swap them
Enter fullscreen mode Exit fullscreen mode

C 语言示例：

void bubbleSort(int arr[], int n) 
{ 
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
            {
                int temp = arr[j]; 
                arr[j] = arr[j+1]; 
                arr[j+1] = temp;
            }
}
Enter fullscreen mode Exit fullscreen mode

JavaScript 示例：

bubbleSort = arr => {
    for (let i = 0; i < arr.length-1; i++)
        for (let j = 0; j < arr.length-i-1; j++)
            if (arr[j] > arr[j+1]) {
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
    return arr;
}
Enter fullscreen mode Exit fullscreen mode

因为比较i第 th 个元素和i+1第 th 个元素，排序只需进行到 ，n-2然后i如果两个元素顺序错误则交换它们。由于已知最大的n-1元素会冒泡到右侧，排序可以在n-1遍历之后停止。
重新遍历数组时，只需考虑未排序的元素。
当交换计数器保持在 时0，表示没有其他元素可交换。

冒泡排序算法

  • 最坏情况：
    由于数组是逆序的，所以必须将每个元素冒泡到整个数组中。由于每次只能将一个元素完全冒泡到其排序位置，因此排序必须进行n多次。
    用大 O 表示法，它转换为O(n²)。

  • 最佳情况：
    数组已经完美排序，因此第一次遍历时无需交换元素。
    用大 O 表示法，它等于Ω(n)。

选择排序

找到最小的未排序元素并将其添加到排序列表的末尾。

伪代码示例#1：

Repeat until there is no unsorted elements remaining:
    Search unsorted part of data to find the smallest value
    Swap the found value with the first element of the unsorted part
Enter fullscreen mode Exit fullscreen mode

伪代码示例#2：

For i from 0 to n–1
    Find smallest item between i'th item and last item
    Swap smallest item with i'th item
Enter fullscreen mode Exit fullscreen mode

C 语言示例：

void selectionSort(int arr[], int n) 
{ 
    for (int i = 0; i < n-1; i++)
    {
        int min = i; 
        for (int j = i+1; j < n; j++) 
            if (arr[j] < arr[min]) min = j;
        int temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}
Enter fullscreen mode Exit fullscreen mode

JavaScript 示例：

selectionSort = arr => { 
    for (let i = 0; i < arr.length-1; i++) {
        let min = i; 
        for (let j = i+1; j < arr.length; j++)
            if (arr[j] < arr[min]) min = j;
        let temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
    return arr;
}
Enter fullscreen mode Exit fullscreen mode

选择排序算法

  • 最坏情况：
    必须重复排序过程n100 次，迭代n数组中的每个元素，找到最小的未排序元素并对其进行排序。每次迭代只能对一个元素进行排序。
    用大 O 表示法，它相当于O(n²)。

  • 最佳情况：
    与最坏情况相同，因为在排序过程迭代遍历数组的所有元素之前，无法保证数组已排序。
    用大 O 表示法，它等于Ω(n²)。

插入排序

就地构建一个排序数组；在构建数组时，如果需要，可以移动元素以腾出空间。

伪代码示例#1：

Call the first element of the array sorted
Repeat until all elements are sorted:
    Insert next unsorted item into sorted part shifting the required number of items
Enter fullscreen mode Exit fullscreen mode

伪代码示例#2：

For i from 1 to n–1
    Insert next unsorted item into sorted part shifting i items
Enter fullscreen mode Exit fullscreen mode

C 语言示例：

void insertionSort(int arr[], int n) 
{ 
    for (int i = 1; i < n; i++) { 
        int key = arr[i]; 
        int j = i-1; 
        while (j >= 0 && arr[j] > key) { 
            arr[j+1] = arr[j]; 
            j = j-1; 
        } 
        arr[j+1] = key; 
    } 
}
Enter fullscreen mode Exit fullscreen mode

JavaScript 示例：

insertionSort = arr => { 
    for (let i = 1; i < arr.length; i++) { 
        let key = arr[i]; 
        let j = i-1; 
        while (j >= 0 && arr[j] > key) { 
            arr[j+1] = arr[j]; 
            j = j-1; 
        } 
        arr[j+1] = key; 
    } 
    return arr;
}
Enter fullscreen mode Exit fullscreen mode

插入排序算法

  • 最坏情况： 由于数组是逆序的，每次插入时
    都必须将元素n从原位置移位。 用大 O 表示法，就是O(n²)。n

  • 最佳情况：
    数组已经排序。只需在迭代每个元素时，在未排序元素和已排序元素之间不断切换即可。
    用大 O 表示法，它等于Ω(n)。

递归

优雅地编写代码。🌹

递归与算法或函数的实现方式有关，它本身并不是算法。

递归函数在执行过程中调用自身。

使用阶乘函数的详细示例：

  • n!在所有正整数上定义
  • n!等于所有小于或等于n 的正整数相乘
  • n!为fact(n)：

伪代码示例#1：

fact(1) = 1
fact(2) = 2 * 1
fact(3) = 3 * 2 * 1
…
Enter fullscreen mode Exit fullscreen mode

伪代码示例#2：

fact(1) = 1
fact(2) = 2 * fact(1)
fact(3) = 3 * fact(2)
…
Enter fullscreen mode Exit fullscreen mode

阶乘函数的递归定义的基础：

fact(n) = n * fact(n-1)
Enter fullscreen mode Exit fullscreen mode

递归函数有两种情况可以应用于任何输入：

  • 基本情况：触发时终止递归过程
  • 递归情况：递归发生的地方
int fact(int n) 
{
    // base case
    if (n == 1)
        return 1;
    // recursive case
    else
        return n * fact(n-1);
}
Enter fullscreen mode Exit fullscreen mode

可以有多个基准情况。
例如斐波那契数列，其中：

  • 第一个元素是0
  • 第二个元素是1
  • n第个元素是(n-1)+(n-2)

递归情况可能存在多种。
例如，collat​​z 猜想。

接下来的 C 和 JavaScript 示例定义了一个collatz函数，用于计算“回到 1”需要多少步：

C 语言示例：

int collatz(int steps) 
{
    // base case
    if (steps == 1) return 0;
    // recursive case: even numbers
    else if ((steps % 2) == 0) return 1+collatz(steps/2);
    // recursive case: odd numbers
    else return 1+collatz(3*steps+1);
}
Enter fullscreen mode Exit fullscreen mode

JavaScript 示例：

collatz = steps => {
    // base case
    if (steps == 1) return 0;
    // recursive case: even numbers
    else if ((steps % 2) == 0) return 1+collatz(steps/2);
    // recursive case: odd numbers
    else return 1+collatz(3*steps+1);
}
Enter fullscreen mode Exit fullscreen mode

合并排序

将数组分成更小的数组进行排序，然后按排序顺序将这些排序后的数组重新组合在一起。

伪代码示例#1：

If only one element
  Return
Else
    Sort left half of elements
    Sort right half of elements
    Merge sorted halves
Enter fullscreen mode Exit fullscreen mode

伪代码示例#2：

Sort the left half of the array (assuming n > 1)
Sort right half of the array (assuming n > 1)
Merge the two halves together
Enter fullscreen mode Exit fullscreen mode

C 示例（递归）：

// merges two subarrays of arr[]
void merge(int arr[], int leftIndex, int mid, int rightIndex) 
{ 
    int n1 = mid-leftIndex+1; 
    int n2 =  rightIndex-mid; 

    // temp arrays
    int Left[n1], Right[n2]; 

    // copy data to temp arrays
    for (int i = 0; i < n1; i++) 
        Left[i] = arr[leftIndex+i]; 
    for (int j = 0; j < n2; j++) 
        Right[j] = arr[mid+1+j]; 

    // merge the temp arrays back into arr[]
    int i = 0; // init index of 1st subarray 
    int j = 0; // init index of 2nd subarray 
    int k = leftIndex; // init index of merged subarray 
    while (i < n1 && j < n2) 
    { 
        if (Left[i] <= Right[j]) 
        { 
            arr[k] = Left[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = Right[j]; 
            j++; 
        } 
        k++; 
    } 

    // copy the remaining elements of Left[], if any
    while (i < n1) 
    { 
        arr[k] = Left[i]; 
        i++; 
        k++; 
    } 

    // copy the remaining elements of Right[], if any
    while (j < n2) 
    { 
        arr[k] = Right[j]; 
        j++; 
        k++; 
    } 
} 

void mergeSort(int arr[], int leftIndex, int rightIndex) 
{   
    if (leftIndex < rightIndex) 
    { 
        // instead of (l+r)/2 to avoid overflow
        int mid = leftIndex+(rightIndex-leftIndex)/2; 
        // sort first and second halves 
        mergeSort(arr, leftIndex, mid); 
        mergeSort(arr, mid+1, rightIndex); 
        // merge them back together
        merge(arr, leftIndex, mid, rightIndex); 
    } 
}
Enter fullscreen mode Exit fullscreen mode

JavaScript 示例（递归）：

// to merge left subarray and right subarray
merge = (left, right) => {
    let resultArray = [], leftIndex = 0, rightIndex = 0;

    // concat values into the resultArray in order
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            resultArray.push(left[leftIndex]);
            leftIndex++;
        } else {
            resultArray.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // concat remaining element from either left OR right
    return resultArray
        .concat(left.slice(leftIndex))
        .concat(right.slice(rightIndex));
}

mergeSort = arr => {
    // if array has one element or is empty, no need to sort
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length/2);
    // divide the array into left and right
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);

    // merge back together using recursion
    return merge(mergeSort(left), mergeSort(right));
}
Enter fullscreen mode Exit fullscreen mode

归并排序算法

  • 最坏情况：
    必须先拆分n元素，然后再有效地重新组合它们，这会导致排序后的子数组在构建时耗时加倍。
    用大 O 表示法，就是O(n log n)。

  • 最佳情况：
    数组已经排序，但仍然需要拆分并重新组合才能确定其是否已排序。
    用大 O 表示法，它等于Ω(n log n)。

资源：

文章来源：https://dev.to/emilie_gl/notes-on-algorithms-36pi
Devto 翻译
PREV
如何在 React 中构建搜索栏
NEXT
Web 开发人员安全检查表 V2