[算法沉淀记录] 排序算法 —— 归并排序

排序算法 —— 归并排序

算法介绍

归并排序是一种分治算法，由约翰·冯·诺伊曼在1945年发明。它的工作原理是将未排序的列表划分为n个子列表，每个子列表包含一个元素(包含一个元素的列表被认为是有序的)，然后重复合并子列表以生成新的有序子列表，直到只剩下一个子列表。

算法基本思想

基本概念

  1. 分治法：将一个复杂的问题分解成两个或更多的相同或相似的子问题，再将子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
  2. 递归：函数自身调用自身。
  3. 稳定性：如果待排序列中两个元素相等，排序后这两个相等元素的相对位置不变，则该算法是稳定的。

算法步骤

  1. 分解：将待排序的n个元素的序列分成两个子序列，每个子序列包含n/2个元素。
  2. 解决：使用归并排序递归地排序两个子序列。
  3. 合并：将两个已排序的子序列合并成一个最终的排序序列。

伪代码描述

function mergeSort(list)
    if length(list) <= 1
        return list
    mid <- length(list) / 2
    left <- mergeSort(list[0...mid])
    right <- mergeSort(list[mid+1...end])
    return merge(left, right)
end function

function merge(left, right)
    result <- empty list
    while left and right are not empty
        if first(left) <= first(right)
            append first(left) to result
            remove first element from left
        else
            append first(right) to result
            remove first element from right
        end if
    end while
    append remaining elements of left and right (if any) to result
    return result
end function

归并排序是一种高效的排序算法，其优缺点如下：

优点

  1. 稳定性：归并排序是一种稳定的排序算法，即相同元素的相对顺序在排序后不会改变。
  2. 时间复杂度：归并排序的最坏、平均和最佳时间复杂度均为(O(n log n))，这意味着它能够提供一致的快速排序性能，不受输入数据初始顺序的影响。
  3. 适用于大量数据：由于时间复杂度较低，归并排序非常适合处理大量数据。
  4. 外部排序：归并排序特别适合外部排序，即数据量太大，无法全部加载到内存中的情况。归并排序可以分块读取数据，逐块排序，最后合并结果。

缺点

  1. 空间复杂度：归并排序的主要缺点是它需要额外的存储空间。在归并过程中，需要与原始数组大小相同的额外空间来存储临时合并的数组。因此，其空间复杂度为(O(n))。
  2. 内存使用：对于内存受限的系统，归并排序可能不是最佳选择，因为它需要足够的内存来存储临时数组。
  3. 小数组效率：对于小数组，归并排序可能不如其他简单排序算法（如插入排序）效率高。尽管时间复杂度相同，但归并排序的常数因子较大，因为它涉及到递归和合并操作。
  4. 递归开销：如果使用递归实现，归并排序可能会受到递归调用的开销影响，尤其是在深度较大的情况下。尽管现代编译器和操作系统对递归有很好的优化，但非递归实现可以避免这种开销。

总体而言，归并排序是一种高效的通用排序算法，特别适合需要稳定排序和大量数据的情况。然而，如果内存使用是一个关键因素，或者数据集非常小，可能需要考虑其他排序算法。

应用场景

归并排序是一种高效的通用排序算法，由于其稳定性和(O(n log n))的时间复杂度，它在多种应用场景中都非常适用。以下是一些归并排序的常见应用场景：

  1. 大数据集排序：归并排序非常适合处理大量数据的排序问题，尤其是当数据集无法一次性加载到内存中时，可以使用外部归并排序。
  2. 并发编程：在多线程或分布式系统中，归并排序可以很容易地并行化。每个线程或进程可以独立地排序数据的一部分，然后合并结果。
  3. 数据库系统：数据库管理系统中的排序操作经常使用归并排序，因为它可以提供稳定的排序结果，这对于数据库的完整性非常重要。
  4. 文件排序：在需要对大量文件进行排序时，归并排序是一个很好的选择。文件可以分块读取到内存中，排序后再合并。
  5. 算法教学：归并排序是计算机科学教育中常用的教学示例，用于讲解分治策略和递归思想。
  6. 网络数据传输：在网络数据传输中，为了保证数据的顺序，可以使用归并排序对分段传输的数据进行排序。
  7. 数值计算：在科学计算和工程应用中，经常需要处理大量的数值数据，归并排序可以有效地对这些数据进行排序。
  8. 操作系统：操作系统的文件系统或虚拟内存管理等组件可能会使用归并排序来管理数据。
  9. 编译器优化：编译器在优化代码时，可能会使用归并排序来处理符号表或优化指令序列。
  10. 多媒体数据处理：在多媒体数据的管理和播放中，如音频剪辑、视频编辑等，归并排序可以用来对数据片段进行排序。

尽管归并排序在许多场景中都非常适用，但它也有一些局限性。例如，归并排序需要额外的存储空间，这在内存受限的环境中可能是一个问题。此外，对于小数据集，归并排序可能不如其他简单的排序算法（如插入排序）效率高，因为归并排序的常数因子较大。因此，在实际应用中，通常会根据具体的需求和数据特性来选择最合适的排序算法。

时间复杂度

归并排序的时间复杂度在最好情况、最坏情况和平均情况下的表现如下

最好情况

最好情况发生在输入数组已经是有序的情况下。在这种情况下，每个子数组都是有序的，所以合并操作会非常快，只需要一次比较就可以将两个子数组合并成一个有序数组。但是，分割过程仍然需要执行 (log(n)) 次，因为我们需要将整个数组分成两个有序的子数组。因此，最好情况下的时间复杂度是 (O(n))。

最坏情况

最坏情况发生在输入数组是完全逆序的情况下。在这种情况下，每次合并操作都需要比较和移动所有的元素，因为我们需要将最大的元素移动到数组的末尾。因此，最坏情况下的时间复杂度是 (O(nlog(n)))。

平均情况

平均情况下，输入数组的元素是随机排列的。在这种情况下，归并排序的时间复杂度仍然是 (O(nlog(n)))。这是因为尽管某些合并操作可能比最好情况下的时间复杂度高，但平均来看，每个元素仍然只需要比较和移动 (log(n)) 次。

小结：

  • 最好情况：(O(n))
  • 最坏情况：(O(n log n))
  • 平均情况：(O(n log n))

归并排序的时间复杂度不受输入数据初始顺序的影响，因为它总是需要进行 (log(n)) 次分割，并且每次合并操作的复杂度是 (O(n))。因此，归并排序是一个稳定的排序算法，其性能在各种情况下都是可预测的。

归并排序的时间复杂度主要由两部分组成：分割和合并。

  1. 分割：分割过程是一个递归过程，它将数组分成越来越小的部分，直到每个部分只包含一个元素。这个分割过程会执行 (log(n)) 次，因为每次分割都会将数组大小减半。
  2. 合并：合并过程将两个有序数组合并成一个有序数组。在合并过程中，每个元素最多比较和移动一次。对于每个级别的分割，合并操作的总次数是 (n)，因为每次合并都会处理整个数组。

综合以上两点，归并排序的时间复杂度是 (O(n log n))。这是因为分割过程的时间复杂度是 O(log n)，而合并过程的时间复杂度是 (O(n))，所以总的时间复杂度是 (O(n log n))。

空间复杂度

归并排序的空间复杂度主要由合并过程中的临时数组决定。

  1. 临时数组：在合并两个有序数组时，需要一个与待排序数组大小相同的临时数组来存储合并的结果。这个临时数组在合并完成后会被复制回原数组。

因此，归并排序的空间复杂度是 (O(n))，因为它需要一个额外的数组来存储合并过程中的临时结果。

证明

我们可以通过数学归纳法来证明归并排序的时间复杂度是 (O(n log n))。
基础情况：当数组大小为 1 时，不需要排序，时间复杂度为 O(1)。
归纳假设：假设对于大小为 k 的数组，归并排序的时间复杂度是 O(k log k)。
归纳步骤：对于大小为 2k 的数组，我们将其分成两个大小为 k 的子数组，分别对它们进行排序，然后合并。根据归纳假设，每个子数组的排序时间是 O(k log k)，合并时间是 O(k)。因此，总的时间复杂度是 O(k log k + k) = O(k log k) = O((2k) log (2k)) = (O(n log n))。
由于每次递归都会将数组大小减半，所以每次递归的时间复杂度都是 (O(n log n))。因此，归并排序的时间复杂度是 (O(n log n))。
空间复杂度的证明类似，每次合并都需要一个大小为 n 的临时数组，所以总的空间复杂度是 (O(n))。
综上所述，归并排序的时间复杂度是 (O(n log n))，空间复杂度是 (O(n))。

代码实现

Python 实现

递归版本

多个函数版：

def merge(left, right):
    # Create an empty array to store the merged elements
    merged = []
    # Initialize indexes for the left and right subarrays
    left_index = 0
    right_index = 0

    # Compare elements of the left and right subarrays and add them to the merged array
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    # Add the remaining elements of the left subarray to the merged array
    merged += left[left_index:]
    # Add the remaining elements of the right subarray to the merged array
    merged += right[right_index:]

    # Return the merged array
    return merged

def merge_sort(lst):
    # Check if the length of the array is less than or equal to 1
    if len(lst) <= 1:
        # Return the array if it is
        return lst

    # Calculate the midpoint of the array
    mid = len(lst) // 2
    # Create two subarrays, one from the start to the midpoint and one from the midpoint to the end
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])

    # Merge the two subarrays and return the sorted array
    return merge(left, right)

单个函数版：

def mergeSort(arr):
    # Check if the length of the array is greater than 1
    if len(arr) > 1:
        # Calculate the midpoint of the array
        mid = len(arr) // 2
        # Create two subarrays, one from the start to the midpoint and one from the midpoint to the end
        left = arr[:mid]
        right = arr[mid:]

        # Recursively call the mergeSort function on each subarray
        mergeSort(left)
        mergeSort(right)

        # Initialize indexes for the left and right subarrays
        i = j = k = 0

        # Compare elements of the left and right subarrays and add them to the sorted array
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        # Add the remaining elements of the left subarray to the sorted array
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1

        # Add the remaining elements of the right subarray to the sorted array
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
非递归版本
def mergeNew(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = arr[l + i]
    for j in range(0, n2):
        R[j] = arr[m + 1 + j]
    i, j, k = 0, 0, l
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

def merge_sort_bottom_up(arr):
    n = len(arr)
    size = 1
    while size <= n - 1:
        for left_start in range(0, n - 1, 2 * size):
            mid = min(left_start + size - 1, n - 1)
            right_end = min(left_start + 2 * size - 1, n - 1)
            mergeNew(arr, left_start, mid, right_end)
        size = size * 2

C++ 实现

C++ 模板实现

递归版本
template <typename T>
vector<T> merge(vector<T> &left, vector<T> &right)
{
    vector<T> merged;
    while (!left.empty() && !right.empty())
    {
        // Compare the first elements of the two sublists
        if (left[0] <= right[0])
        {
            // If left sublist's element is smaller, add it to the merged sublist
            merged.push_back(left[0]);
            // Erase the element from the sublist
            left.erase(left.begin());
        }
        else
        {
            // If right sublist's element is smaller, add it to the merged sublist
            merged.push_back(right[0]);
            // Erase the element from the sublist
            right.erase(right.begin());
        }
    }
    // Add the remaining elements of the left sublist to the merged sublist
    merged.insert(merged.end(), left.begin(), left.end());
    // Add the remaining elements of the right sublist to the merged sublist
    merged.insert(merged.end(), right.begin(), right.end());
    return merged;
}

template <typename T>
vector<T> mergeSort(const vector<T> &list)
{
    // If the list has one or less elements, it is already sorted
    if (list.size() <= 1)
    {
        return list;
    }
    // Find the midpoint of the list
    int mid = list.size() / 2;
    // Create two sublists, one from the beginning to the midpoint, and one from the midpoint to the end
    vector<T> left = mergeSort(vector<T>(list.begin(), list.begin() + mid));
    vector<T> right = mergeSort(vector<T>(list.begin() + mid, list.end()));
    // Merge the two sublists and return the sorted list
    return merge(left, right);
}
非递归版本
template <typename T>
void mergeSortNonRecursive(vector<T> &arr)
{
    // 1. Find the size of the array
    int n = arr.size();
    // 2. Iterate through the array
    for (int size = 1; size < n; size *= 2)
    {
        // 3. Iterate through the array
        for (int leftStart = 0; leftStart < n - size; leftStart += 2 * size)
        {
            // 4. Find the mid point
            int mid = min(leftStart + size, n);
            // 5. Find the right start point
            int rightStart = min(leftStart + 2 * size, n);
            // 6. Create a temporary array
            int i = leftStart;
            int j = mid;
            int k = leftStart;
            vector<T> temp(arr.begin(), arr.end());
            // 7. Compare the elements and move them to the temporary array
            while (i < mid && j < rightStart)
            {
                if (arr[i] <= arr[j])
                {
                    temp[k++] = arr[i++];
                }
                else
                {
                    temp[k++] = arr[j++];
                }
            }
            // 8. Move the remaining elements to the temporary array
            while (i < mid)
            {
                temp[k++] = arr[i++];
            }
            while (j < rightStart)
            {
                temp[k++] = arr[j++];
            }
            // 9. Copy the elements from the temporary array to the original array
            copy(temp.begin(), temp.end(), arr.begin());
        }
    }
}

扩展阅读

优化时间复杂度的思路

时间复杂度优化

  1. 最小化复制操作：在归并过程中，可以减少不必要的数据复制。例如，可以使用指针而不是实际复制数据来合并两个子数组。
  2. 局部性优化：利用数据的局部性原理，优先合并相邻的小数组块，这样可以提高缓存利用率。
  3. 切换到插入排序：对于小数组，归并排序的常数因子较大，可以切换到插入排序来处理小数组，因为插入排序在小数组上通常表现得更好。
  4. 并行化：归并排序可以很容易地并行化，尤其是在合并阶段，可以同时对多个子数组进行合并。

空间复杂度优化

  1. 原地归并：通过使用额外的几个变量，可以在原地完成归并操作，从而将空间复杂度从(O(n))降低到O(1)。这通常会增加算法的复杂性。
  2. 使用迭代而非递归：迭代版本的归并排序可以避免递归带来的额外空间开销。

归并排序的变种算法

  1. 自底向上的归并排序：这是一种非递归的归并排序，它从最小的数组块开始合并，逐步增加块的大小，直到整个数组被排序。
  2. 多路归并排序：传统的归并排序是两路归并，即每次合并两个子数组。多路归并排序可以同时合并多个子数组，这可以进一步提高合并阶段的效率，尤其是在并行计算中。
  3. 外部归并排序：当数据集太大而无法全部加载到内存中时，可以使用外部归并排序。这种算法将数据分块存储在磁盘上，然后分块读取、排序并合并。
  4. Timsort：Timsort是Python和Java标准库中使用的排序算法，它是归并排序和插入排序的结合。Timsort利用了现实世界数据通常部分有序的特点，通过优化来提高排序效率。
    历史上，归并排序的变种算法还包括一些针对特定应用场景的优化，例如在数据库排序、多核处理器排序等方面的变种。这些变种算法通常结合了特定硬件特性和数据特征来进一步提高排序效率。

自底向上的归并排序（Bottom-Up Merge Sort）

自底向上的归并排序（Bottom-Up Merge Sort）是一种非递归的归并排序算法。它与传统的递归归并排序不同，不是一开始就将数组分成单个元素的小数组，然后再两两合并，而是从最小的数组块开始，逐步合并成更大的有序块，直到整个数组排序完成。

算法步骤
  1. 初始化：将数组分解成n个长度为1的子数组（每个元素都是一个子数组）。
  2. 迭代合并：重复以下过程，直到所有子数组合并成一个有序数组：
    • 合并相邻的子数组对，每个子数组的长度是上一次合并的长度的两倍。
    • 每次合并后，子数组的数量减半，每个子数组的长度加倍。
  3. 完成排序：当数组完全合并时，排序完成。
伪代码
自底向上的归并排序(A)
    n = A的长度
    size = 1  // 初始子数组大小
    while size < n
        p = 0  // 子数组的起始索引
        while p + size < n
            q = p + size - 1  // 第一个子数组的结束索引
            r = min((p + 2 * size - 1), (n - 1))  // 第二个子数组的结束索引
            合并(A, p, q, r)
            p = r + 1  // 更新下一个子数组的起始索引
        size = size * 2  // 子数组大小翻倍
Python 代码实现
def mergeNew(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = arr[l + i]
    for j in range(0, n2):
        R[j] = arr[m + 1 + j]
    i, j, k = 0, 0, l
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

def merge_sort_bottom_up(arr):
    n = len(arr)
    size = 1
    while size <= n - 1:
        for left_start in range(0, n - 1, 2 * size):
            mid = min(left_start + size - 1, n - 1)
            right_end = min(left_start + 2 * size - 1, n - 1)
            mergeNew(arr, left_start, mid, right_end)
        size = size * 2
C++模板代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 合并两个有序数组A[p...q]和A[q+1...r]
template <typename T>
void Merge(vector<T>& A, int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    vector<T> L(n1);
    vector<T> R(n2);
    for (int i = 0; i < n1; i++) {
        L[i] = A[p + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = A[q + 1 + j];
    }
    int i = 0, j = 0;
    for (int k = p; k <= r; k++) {
        if (i < n1 && (j >= n2 || L[i] <= R[j])) {
            A[k] = L[i];
            i++;
        } else {
            A[k] = R[j];
            j++;
        }
    }
}

// 自底向上的归并排序
template <typename T>
void MergeSortBottomUp(vector<T>& A) {
    int n = A.size();
    for (int size = 1; size < n; size *= 2) {
        for (int leftStart = 0; leftStart < n - size; leftStart += 2 * size) {
            int mid = leftStart + size - 1;
            int rightEnd = min(leftStart + 2 * size - 1, n - 1);
            Merge(A, leftStart, mid, rightEnd);
        }
    }
}

int main() {
    vector<int> arr = {5, 2, 4, 7, 1, 3, 2, 6};
    MergeSortBottomUp(arr);
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

这段代码定义了一个模板函数MergeSortBottomUp，它接受一个vector类型的参数arr，并对其进行自底向上的归并排序。函数使用两层循环：外层循环控制子数组的大小，内层循环遍历数组并合并相邻的子数组。在合并过程中，使用了一个临时数组L和R来存储合并前的子数组，然后再将合并后的结果复制回原数组arr。
在main函数中，我们创建了一个整数类型的vector，并调用MergeSortBottomUp进行排序，最后输出排序后的数组。

多路归并排序(Multi-way Merge Sort)

多路归并排序（Multi-Way Merge Sort）是一种改进的归并排序算法，它能够同时合并多个有序的子数组，而不是传统的归并排序中每次只合并两个子数组。这种方法可以显著提高大规模数据集的排序效率。

基本概念

多路归并排序的核心思想是将多个有序的子数组合并成一个有序的大数组。它通常用于处理数据量非常大，以至于无法全部放入内存的情况。与传统的归并排序相比，多路归并排序可以在每个阶段并行处理更多的数据，从而减少整体排序时间。

算法步骤

  1. 初始化：将数据集分割成多个子数组。
  2. 分组归并：将多个子数组合并为较大的有序子数组，直到只剩下一个子数组。
  3. 最终归并：将最后剩余的有序子数组合并成一个最终的有序数组。

伪代码

多路归并排序(A)
    n = A的长度
    k = 子数组的数量  // 通常设置为处理器的数量或数据块的数量
    大小 = 数据集大小 / k
    将A分割成k个子数组，每个大小为大小
    while 子数组的数量 > 1
        合并相邻的子数组对，直到只剩下一个子数组
        子数组的数量 = 子数组数量 / 2
    返回有序的A

C++模板代码实现

template <typename T>
void multiwayMergeSort(vector<T> &arr, int k)
{
    int n = arr.size();
    if (n <= 1)
        return;

    vector<vector<T>> segments(k);
    for (int i = 0; i < n; ++i)
    {
        segments[i % k].push_back(arr[i]);
    }

    for (auto &segment : segments)
    {
        multiwayMergeSort(segment, k);
    }

    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> pq;
    vector<int> indices(k, 0);
    for (int i = 0; i < k; ++i)
    {
        if (!segments[i].empty())
        {
            pq.push({segments[i][0], i});
            indices[i]++;
        }
    }

    arr.clear();
    while (!pq.empty())
    {
        auto [val, idx] = pq.top();
        pq.pop();
        arr.push_back(val);
        if (indices[idx] < segments[idx].size())
        {
            pq.push({segments[idx][indices[idx]], idx});
            indices[idx]++;
        }
    }
}

template <typename T>
void multiway_merge_sort_non_recursive(vector<T> &data)
{
    int k = data.size();
    int current_size = 1; // Start with smallest sub-list size

    // Repeatedly merge sub-lists of increasing size
    while (current_size < k)
    {
        for (int left = 0; left < k; left += current_size * 2)
        {
            // Calculate right and mid indices for the current merge
            int mid = min(left + current_size, k);
            int right = min(left + current_size * 2, k);

            // Merge sub-lists [left, mid) and [mid, right)
            auto left_it = data.begin() + left, mid_it = data.begin() + mid;
            auto right_it = (right < k) ? data.begin() + right : data.end();

            // Create temporary vector for merged elements
            vector<T> merged;

            // Merge elements until one sub-list is exhausted
            while (left_it != data.begin() + mid && mid_it != data.begin() + right)
            {
                if (*left_it <= *mid_it)
                {
                    merged.push_back(*left_it);
                    ++left_it;
                }
                else
                {
                    merged.push_back(*mid_it);
                    ++mid_it;
                }
            }

            // Add remaining elements from the non-exhausted sub-list
            merged.insert(merged.end(), left_it, data.begin() + mid);
            if (right_it != mid_it)
            {
                merged.insert(merged.end(), right_it, data.end());
            }

            // Update the original data with the merged elements
            copy(merged.begin(), merged.end(), data.begin() + left);
        }
        current_size *= 2; // Double the sub-list size for next merge
    }
}

完整代码

#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <string>
#include <vector>
#include <queue>

using namespace std;

class Person
{
public:
    Person() = default;
    Person(string name, int age, int score)
    {
        this->name = name;
        this->age = age;
        this->socre = score;
    }

    // Override the operator> for other function to use.
    bool operator>(const Person &other) const
    {
        // Compare the socre of two Person objects.
        return this->socre > other.socre;
    }

    // Override the operator< for other function to use.
    bool operator<(const Person &other) const
    {
        // Compare the socre of two Person objects.
        return this->socre < other.socre;
    }

    // Override the operator== for other function to use.
    bool operator==(const Person &other) const
    {
        // Compare the socre, age and name of two Person objects.
        return this->socre == other.socre &&
               this->age == other.age &&
               this->name == other.name;
    }

    // Override the operator!= for other function to use.
    bool operator!=(const Person &other) const
    {
        // Compare the socre, age and name of two Person objects.
        return this->socre != other.socre ||
               this->age != other.age ||
               this->name != other.name;
    }

    // Override the operator<= for other fnction to use.
    bool operator<=(const Person &other) const
    {
        // Compare the socre, age and name of two Person objects.
        return this->socre <= other.socre &&
               this->age <= other.age &&
               this->name <= other.name;
    }

    // Override the operator>= for other function to use.
    bool operator>=(const Person &other) const
    {
        // Compare the socre, age and name of two Person objects.
        return this->socre >= other.socre &&
               this->age >= other.age &&
               this->name >= other.name;
    }

    // Now there are some get parameters function for this calss:
    const string &getName() const { return this->name; }
    int getAge() const { return this->age; }
    int getScore() const { return this->socre; }

private:
    string name;
    int age = 0;
    int socre = 0;
};

template <typename T>
vector<T> merge(vector<T> &left, vector<T> &right)
{
    vector<T> merged;
    while (!left.empty() && !right.empty())
    {
        // Compare the first elements of the two sublists
        if (left[0] <= right[0])
        {
            // If left sublist's element is smaller, add it to the merged sublist
            merged.push_back(left[0]);
            // Erase the element from the sublist
            left.erase(left.begin());
        }
        else
        {
            // If right sublist's element is smaller, add it to the merged sublist
            merged.push_back(right[0]);
            // Erase the element from the sublist
            right.erase(right.begin());
        }
    }
    // Add the remaining elements of the left sublist to the merged sublist
    merged.insert(merged.end(), left.begin(), left.end());
    // Add the remaining elements of the right sublist to the merged sublist
    merged.insert(merged.end(), right.begin(), right.end());
    return merged;
}

template <typename T>
vector<T> mergeSort(const vector<T> &list)
{
    // If the list has one or less elements, it is already sorted
    if (list.size() <= 1)
    {
        return list;
    }
    // Find the midpoint of the list
    int mid = list.size() / 2;
    // Create two sublists, one from the beginning to the midpoint, and one from the midpoint to the end
    vector<T> left = mergeSort(vector<T>(list.begin(), list.begin() + mid));
    vector<T> right = mergeSort(vector<T>(list.begin() + mid, list.end()));
    // Merge the two sublists and return the sorted list
    return merge(left, right);
}

void mergeSortTestCase()
{
    vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};
    mergeSort<int>(data);
    for (int i : data)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};
    mergeSort<double>(dData);
    for (double i : dData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<char> cData = {'a', 'c', 'b', 'd', 'e'};
    mergeSort<char>(cData);
    for (char i : cData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};
    mergeSort<Person>(pData);
    for (Person i : pData)
    {
        cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;
    }
    cout << endl;
}

template <typename T>
vector<T> mergeOther(const vector<T> &left, const vector<T> &right)
{
    vector<T> result;
    unsigned left_it = 0, right_it = 0;

    while (left_it < left.size() && right_it < right.size())
    {
        // compare the current elements of the left and right vectors
        if (left[left_it] < right[right_it])
        {
            // if the element of the left vector is less than the element of the right vector, add it to the result vector
            result.push_back(left[left_it]);
            left_it++;
        }
        else
        {
            // if the element of the left vector is greater than or equal to the element of the right vector, add it to the result vector
            result.push_back(right[right_it]);
            right_it++;
        }
    }

    // add the remaining elements of the left vector to the result vector
    while (left_it < left.size())
    {
        result.push_back(left[left_it]);
        left_it++;
    }

    // add the remaining elements of the right vector to the result vector
    while (right_it < right.size())
    {
        result.push_back(right[right_it]);
        right_it++;
    }

    return result;
}

template <typename T>
vector<T> mergeSortOther(vector<T> &arr)
{
    // if the vector is empty or contains only one element, return the vector
    if (arr.size() <= 1)
    {
        return arr;
    }

    // create two vectors, one to store the elements of the original vector before the split and one to store the elements after the split
    vector<T> left, right, result;
    int middle = ((int)arr.size() + 1) / 2;

    // copy the elements of the original vector into the left vector
    for (int i = 0; i < middle; i++)
    {
        left.push_back(arr[i]);
    }

    // copy the elements of the original vector into the right vector
    for (int i = middle; i < arr.size(); i++)
    {
        right.push_back(arr[i]);
    }

    // call the mergeSortOther function on the left and right vectors
    left = mergeSortOther(left);
    right = mergeSortOther(right);
    // call the mergeOther function to merge the sorted left and right vectors
    result = mergeOther(left, right);

    // return the merged sorted vector
    return result;
}

void mergeSortOtherTestCase()
{
    vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};
    mergeSortOther<int>(data);
    for (int i : data)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};
    mergeSortOther<double>(dData);
    for (double i : dData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<char> cData = {'a', 'c', 'b', 'd', 'e'};
    mergeSortOther<char>(cData);
    for (char i : cData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};
    mergeSortOther<Person>(pData);
    for (Person i : pData)
    {
        cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;
    }
    cout << endl;
}

template <typename T>
void mergeSortNonRecursive(vector<T> &arr)
{
    // 1. Find the size of the array
    int n = arr.size();
    // 2. Iterate through the array
    for (int size = 1; size < n; size *= 2)
    {
        // 3. Iterate through the array
        for (int leftStart = 0; leftStart < n - size; leftStart += 2 * size)
        {
            // 4. Find the mid point
            int mid = min(leftStart + size, n);
            // 5. Find the right start point
            int rightStart = min(leftStart + 2 * size, n);
            // 6. Create a temporary array
            int i = leftStart;
            int j = mid;
            int k = leftStart;
            vector<T> temp(arr.begin(), arr.end());
            // 7. Compare the elements and move them to the temporary array
            while (i < mid && j < rightStart)
            {
                if (arr[i] <= arr[j])
                {
                    temp[k++] = arr[i++];
                }
                else
                {
                    temp[k++] = arr[j++];
                }
            }
            // 8. Move the remaining elements to the temporary array
            while (i < mid)
            {
                temp[k++] = arr[i++];
            }
            while (j < rightStart)
            {
                temp[k++] = arr[j++];
            }
            // 9. Copy the elements from the temporary array to the original array
            copy(temp.begin(), temp.end(), arr.begin());
        }
    }
}

void mergeSortNonRecursiveTestCase()
{
    vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};
    mergeSortNonRecursive<int>(data);
    for (int i : data)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};
    mergeSortNonRecursive<double>(dData);
    for (double i : dData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<char> cData = {'a', 'c', 'b', 'd', 'e'};
    mergeSortNonRecursive<char>(cData);
    for (char i : cData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};
    mergeSortNonRecursive<Person>(pData);
    for (Person i : pData)
    {
        cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;
    }
    cout << endl;
}

template <typename T>
void Merge(vector<T> &A, int p, int q, int r)
{
    // n1 is the size of the left sub array
    int n1 = q - p + 1;
    // n2 is the size of the right sub array
    int n2 = r - q;
    // Create two sub arrays L and R of size n1 and n2 respectively
    vector<T> L(n1);
    vector<T> R(n2);
    // Copy the elements of A from p to q into L
    for (int i = 0; i < n1; i++)
    {
        L[i] = A[p + i];
    }
    // Copy the elements of A from q+1 to r into R
    for (int j = 0; j < n2; j++)
    {
        R[j] = A[q + 1 + j];
    }
    // Initialize indexes i and j to 0
    int i = 0, j = 0;
    // Merge the elements of L and R into A
    for (int k = p; k <= r; k++)
    {
        // If the element at index i of L is less than or equal to the element at index j of R
        if (i < n1 && (j >= n2 || L[i] <= R[j]))
        {
            // Copy the element at index i of L into A
            A[k] = L[i];
            // Increment i
            i++;
        }
        else
        {
            // Copy the element at index j of R into A
            A[k] = R[j];
            // Increment j
            j++;
        }
    }
}

template <typename T>
void MergeSortBottomUp(vector<T> &A)
{
    // n is the size of the array A
    int n = A.size();
    // Iterate through the array A in a bottom up manner
    for (int size = 1; size < n; size *= 2)
    {
        // Iterate through the array A in a pair of sub arrays
        for (int leftStart = 0; leftStart < n - size; leftStart += 2 * size)
        {
            // mid is the mid point of the left sub array
            int mid = leftStart + size - 1;
            // rightEnd is the rightmost element of the right sub array
            int rightEnd = min(leftStart + 2 * size - 1, n - 1);
            // Merge the elements of the left and right sub arrays into A
            Merge<T>(A, leftStart, mid, rightEnd);
        }
    }
}

void mergeSortBottomUpTestCase()
{
    vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};
    MergeSortBottomUp<int>(data);
    for (int i : data)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};
    MergeSortBottomUp<double>(dData);
    for (double i : dData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<char> cData = {'a', 'c', 'b', 'd', 'e'};
    MergeSortBottomUp<char>(cData);
    for (char i : cData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};
    MergeSortBottomUp<Person>(pData);
    for (Person i : pData)
    {
        cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;
    }
    cout << endl;
}

// Helper function for merging sub-lists
template <typename T>
void merge_bottom_up_sublist(vector<T> &data, size_t left, size_t mid, size_t right)
{
    // Create temporary vector for holding merged elements
    vector<T> temp(right - left);

    // Copy elements from left and right sub-lists to the temp vector
    size_t i = left, j = mid, k = 0;
    while (i < mid && j < right)
    {
        if (data[i] <= data[j])
        {
            temp[k++] = data[i++];
        }
        else
        {
            temp[k++] = data[j++];
        }
    }

    // Copy remaining elements from left sub-list
    while (i < mid)
    {
        temp[k++] = data[i++];
    }

    // Copy remaining elements from right sub-list
    while (j < right)
    {
        temp[k++] = data[j++];
    }

    // Copy merged elements back to the original vector
    copy(temp.begin(), temp.end(), data.begin() + left);
}

template <typename T>
void merge_sort_bottom_up_non_recursive(vector<T> &data)
{
    size_t n = data.size();

    // Iterate through sub-list sizes from 1 to n/2
    for (size_t sub_size = 1; sub_size <= n / 2; sub_size *= 2)
    {
        // Iterate through the data starting from left index
        for (size_t left = 0; left < n - sub_size; left += 2 * sub_size)
        {
            // Calculate right and mid indices for the merge
            size_t mid = min(left + sub_size, n);
            size_t right = min(left + 2 * sub_size, n);

            // Perform the merge operation
            merge_bottom_up_sublist<T>(data, left, mid, right);
        }
    }
}

void merge_sort_bottom_up_non_recursive_test_case()
{
    vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};
    merge_sort_bottom_up_non_recursive<int>(data);
    for (int i : data)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};
    merge_sort_bottom_up_non_recursive<double>(dData);
    for (double i : dData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<char> cData = {'a', 'c', 'b', 'd', 'e'};
    merge_sort_bottom_up_non_recursive<char>(cData);
    for (char i : cData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};
    merge_sort_bottom_up_non_recursive<Person>(pData);
    for (Person i : pData)
    {
        cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;
    }
    cout << endl;
}

template <typename T>
void multiwayMergeSort(vector<T> &arr, int k)
{
    int n = arr.size();
    if (n <= 1)
        return;

    vector<vector<T>> segments(k);
    for (int i = 0; i < n; ++i)
    {
        segments[i % k].push_back(arr[i]);
    }

    for (auto &segment : segments)
    {
        multiwayMergeSort(segment, k);
    }

    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> pq;
    vector<int> indices(k, 0);
    for (int i = 0; i < k; ++i)
    {
        if (!segments[i].empty())
        {
            pq.push({segments[i][0], i});
            indices[i]++;
        }
    }

    arr.clear();
    while (!pq.empty())
    {
        auto [val, idx] = pq.top();
        pq.pop();
        arr.push_back(val);
        if (indices[idx] < segments[idx].size())
        {
            pq.push({segments[idx][indices[idx]], idx});
            indices[idx]++;
        }
    }
}

void multiWayMergeSortTestCase()
{
    int mutilWayConunt = 4;
    vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};
    multiwayMergeSort<int>(data, mutilWayConunt);
    for (int i : data)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};
    multiwayMergeSort<double>(dData, mutilWayConunt);
    for (double i : dData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<char> cData = {'a', 'c', 'b', 'd', 'e'};
    multiwayMergeSort<char>(cData, mutilWayConunt);
    for (char i : cData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};
    multiwayMergeSort<Person>(pData, mutilWayConunt);
    for (Person i : pData)
    {
        cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;
    }
    cout << endl;
}

template <typename T>
void multiway_merge_sort_non_recursive(vector<T> &data)
{
    int k = data.size();
    int current_size = 1; // Start with smallest sub-list size

    // Repeatedly merge sub-lists of increasing size
    while (current_size < k)
    {
        for (int left = 0; left < k; left += current_size * 2)
        {
            // Calculate right and mid indices for the current merge
            int mid = min(left + current_size, k);
            int right = min(left + current_size * 2, k);

            // Merge sub-lists [left, mid) and [mid, right)
            auto left_it = data.begin() + left, mid_it = data.begin() + mid;
            auto right_it = (right < k) ? data.begin() + right : data.end();

            // Create temporary vector for merged elements
            vector<T> merged;

            // Merge elements until one sub-list is exhausted
            while (left_it != data.begin() + mid && mid_it != data.begin() + right)
            {
                if (*left_it <= *mid_it)
                {
                    merged.push_back(*left_it);
                    ++left_it;
                }
                else
                {
                    merged.push_back(*mid_it);
                    ++mid_it;
                }
            }

            // Add remaining elements from the non-exhausted sub-list
            merged.insert(merged.end(), left_it, data.begin() + mid);
            if (right_it != mid_it)
            {
                merged.insert(merged.end(), right_it, data.end());
            }

            // Update the original data with the merged elements
            copy(merged.begin(), merged.end(), data.begin() + left);
        }
        current_size *= 2; // Double the sub-list size for next merge
    }
}

void multiway_merge_sort_non_recursive_test_case()
{
    vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};
    multiway_merge_sort_non_recursive<int>(data);
    for (int i : data)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};
    multiway_merge_sort_non_recursive<double>(dData);
    for (double i : dData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<char> cData = {'a', 'c', 'b', 'd', 'e'};
    multiway_merge_sort_non_recursive<char>(cData);
    for (char i : cData)
    {
        cout << i << " ";
    }
    cout << endl;

    vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};
    multiway_merge_sort_non_recursive<Person>(pData);
    for (Person i : pData)
    {
        cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;
    }
    cout << endl;
}

int main()
{
    mergeSortTestCase();
    mergeSortNonRecursiveTestCase();
    mergeSortOtherTestCase();
    mergeSortBottomUpTestCase();
    multiWayMergeSortTestCase();
    multiway_merge_sort_non_recursive_test_case();
    merge_sort_bottom_up_non_recursive_test_case();
    return 0;
}

个人格言

追寻与内心共鸣的生活，未来会逐渐揭晓答案。
Pursue the life that resonates with your heart, and the future will gradually reveal the answer.
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/404717.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

最简单方式把jar打包成Windows服务

最简单方式把jar打包成Windows服务

废话 &#x1f622; 将JAR文件转化为Windows服务是一种高效且常见的Java应用部署策略。这种转变赋予了Java应用程序在Windows操作系统上以无界面后台服务模式运行的能力&#xff0c;从而实现了持续、稳定且可靠的功能提供。这种部署方式不仅提升了应用的可用性&#xff0c…
阅读更多...
TreeData 数据查找

TreeData 数据查找

TreeData 数据查找 最近做需求的时候遇到了这样的一个需求&#xff0c;Tree组件数据支持查找&#xff0c;而且TreeData的数据层级是无限级的 开始想的事借助UI组件库&#xff08;Ant-design-vue&#xff09;中的Tree组件的相关方法直接实现,看了下api 发现没法实现&#xff0c;…
阅读更多...
Java SpringBoot测试OceanBase

Java SpringBoot测试OceanBase

对上篇mysql导入到OceanBase中的数据库进行代码测试&#xff0c;写了个demo包含测试方法&#xff0c;在原mysql库中成功执行&#xff0c;迁移到OceanBase时看是否能不修改业务代码而成功执行测试方法&#xff1a; 代码基于SpringBoot MyBastis测试增删改查、批量新增、多表联…
阅读更多...
onnx 1.16 doc学习笔记一：ONNX概念

onnx 1.16 doc学习笔记一：ONNX概念

onnx作为一个通用格式&#xff0c;很少有中文教程&#xff0c;因此开一篇文章对onnx 1.16文档进行翻译与进一步解释&#xff0c; onnx 1.16官方文档&#xff1a;https://onnx.ai/onnx/intro/index.html](https://onnx.ai/onnx/intro/index.html)&#xff0c; 如果觉得有收获&am…
阅读更多...
【Redis服务搭建】

【Redis服务搭建】

目录 Redis的修改配置启动以及参数调优Redis的常用基本操作Redis运维监控命令Redis的配置的动态更新和写入Redis的多用户管理Redis的慢日志Redis禁用危险命令和压测工具Redis持久化存储1.Redis的RDB持久化存储2.Redis的AOF持久化存储 Redis的主从复制redis的哨兵实现主从自动切…
阅读更多...
信号信号槽

信号信号槽

三、信号槽 概念 信号和槽是两种函数&#xff0c;这是Qt在C基础上新增的特性&#xff0c;类似于其他技术中的回调的概念。 信号槽通过程序员提前设定的“约定”&#xff0c;可以实现对象之间的通信&#xff0c;有两个先决条件。 通信的对象都是在QOBject类中派生出来的。 QOBje…
阅读更多...
提升App推广效果，从优化落地页开始

提升App推广效果，从优化落地页开始

在App推广过程中&#xff0c;落地页的转化率一直是推广运营者关注的重点。然而&#xff0c;很多运营者发现&#xff0c;即使使用了相同的工具和模板&#xff0c;别人的效果却远远超出自己。那么&#xff0c;问题到底出在哪里呢&#xff1f;今天&#xff0c;我们就来聊聊如何提升…
阅读更多...
便携式气象站的安装注意事项

便携式气象站的安装注意事项

型号推荐&#xff1a;云境天合TH-BQX9】便携式气象站的安装注意事项包括以下几点&#xff1a; 安装前检查&#xff1a;在安装前&#xff0c;应对便携式气象站进行检查&#xff0c;确保设备的包装完好无损&#xff0c;配件齐全&#xff0c;如气象站传感器、支架、采集器和传输模…
阅读更多...
链表和顺序表的优劣分析及其时间、空间复杂度分析

链表和顺序表的优劣分析及其时间、空间复杂度分析

链表和顺序表的优劣分析及其时间、空间复杂度分析 一、链表和顺序表的优劣分析二、算法复杂度<font face "楷体" size 5 color blue>//上面算法的执行次数大致为&#xff1a;F&#xff08;N&#xff09; N^22*N10;   N 10,F(10) 1002010 130次   N 1…
阅读更多...
提高学习效率和速度的方法

提高学习效率和速度的方法

如下是一些策略和方法来帮助提高学习效率和速度&#xff1a; 1. **主动学习**&#xff1a;主动寻找信息并提出问题&#xff0c;而不是被动接受。这样可以提高您的学习动力和效率。 2. **分块学习**&#xff1a;将复杂的知识点分解成小块&#xff0c;逐一理解和掌握。这种方法可…
阅读更多...
unity屏幕受伤特效

unity屏幕受伤特效

//使用用途&#xff1a;同于屏幕掉血的后处理特效 //请结合和脚本&#xff1a;BloodScreen 挂载至摄像机使用本特效 //本特效设计之初未考虑兼容移动设备&#xff0c;请注意//使用说明&#xff1a; //掉血获取此脚本&#xff0c;将showBlood设置为true&#xff0c;如果您需要更…
阅读更多...
Js的 Promise的 then catch 笔记240222

Js的 Promise的 then catch 笔记240222

Js的 Promise的 then catch 笔记240222 基本用法 new Promise(f>{setTimeout(ev>{f("一秒后输出控制台");},1000); }).then(f的参数>{console.log(f的参数); }); // 控制台输出: 一秒后输出控制台上面代码中, f 的标准名叫做 resolve , 所以应该写成 new …
阅读更多...
函数栈帧的创建及销毁（超详解）

函数栈帧的创建及销毁（超详解）

目录 1.预备知识 1.1内存区的划分 1.2认识相关寄存器和汇编指令 1.2.1寄存器 1.2.2相关汇编指令 2.测试前 2.1测试代码及环境 2.2 main函数也是被其他函数调用的 3.函数栈帧的创建 4.进入函数内部 5.形参与实参 6.call/jump add函数 7.函数栈帧的销毁 7.1保存…
阅读更多...
使用python查看官网是否发布新的内容

使用python查看官网是否发布新的内容

目录 前言 第一章、python介绍和使用pip install下载包 1.python介绍 2.使用vscode编写python 3.pip install的使用 第二章、查看官网是否发布新的内容 第三章、代码实现 目录结构 代码实现 check_new_news.py files.py news.py main.py file.txt 运行演示 前言 也…
阅读更多...
【已解决】@tableid can‘t more than one

【已解决】@tableid can‘t more than one

实体里面不能有两个TableId&#xff0c;只留一个就好了
阅读更多...
SpringBoot对于SpringMVC的支持

SpringBoot对于SpringMVC的支持

创建项目 版本说明这里使用的 SpringBoot 2.0.0.Release SpringBoot对于SpringMVC的支持 在之前的开发中很多场景下使用的是基于xml配置文件或者是Java配置类的方式来进行SpringMVC的配置。一般来讲&#xff0c;初始的步骤如下所示 1、初始化SpringMVC的DispatcherServlet2、…
阅读更多...
[OpenAI]继ChatGPT后发布的Sora模型原理与体验通道

[OpenAI]继ChatGPT后发布的Sora模型原理与体验通道

前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家&#xff1a;https://www.captainbed.cn/z ChatGPT体验地址 文章目录 前言OpenAI体验通道Spacetime Latent Patches 潜变量时空碎片, 建构视觉语言系统…
阅读更多...
kettle计算增长率

kettle计算增长率

kettle计算增长率 问题描述处理方法 问题描述 读取一段时间内的数据记录&#xff0c;计算相邻记录的比率 iddatevalue12024-01-0110012024-01-0211012024-01-0312012024-01-0490 处理方法 1.使用统计中的分析查询节点能在每一行中添加前后行的数据 2.使用计算器节点计算比…
阅读更多...
音视频基础概念笔记

音视频基础概念笔记

RGB 色彩空间更适合图像采集和显示&#xff0c; YUV 空间用于编码和存储则比较好。 无论是 RGB 还是 YUV &#xff0c;他们都是 表达 色彩信息的一种方式。 &#xff08;Human Visual System&#xff09;人类视觉系统 色度感知 包含两个维度&#xff1a;色调&#xff08;Hue&…
阅读更多...
ELK入门(四)-logstash

ELK入门(四)-logstash

Logstash Logstash 是开源的服务器端数据处理管道&#xff0c;能够同时从多个来源采集数据&#xff0c;转换数据&#xff0c;然后将数据发送到您最喜欢的存储库中。 Logstash 能够动态地采集、转换和传输数据&#xff0c;不受格式或复杂度的影响。利用 Grok 从非结构化数据中…
阅读更多...
最新文章

Copyright @ 2022~2023