[算法沉淀记录] 排序算法 —— 选择排序

排序算法 —— 选择排序

基本概念

选择排序是一种简单的排序算法，它的工作原理是每次从待排序的列表中选择最小（或最大）的元素，将其与列表中的第一个位置交换，然后继续对剩余的元素进行排序，直到整个列表排序完成。选择排序的时间复杂度为O(n^2)，是一种不高效的排序算法，但在某些情况下，由于其简单性和稳定性，仍然被广泛使用。

算法基本思想

选择排序的基本思想是每次从待排序的列表中选择最小（或最大）的元素，将其与列表中的第一个位置交换，然后继续对剩余的元素进行排序，直到整个列表排序完成。

算法步骤

  1. 首先，将第一个元素设为最小值（或最大值）。
  2. 然后，将列表中的每个元素与最小值（或最大值）进行比较，如果找到更小的（或更大的）值，则更新最小值（或最大值）的索引。
  3. 最后，将最小值（或最大值）与列表中的第一个位置交换。
  4. 重复步骤1-3，直到整个列表排序完成。
  5. 返回排序后的列表。

伪代码描述

function selectionSort(arr):
    for i from 0 to length(arr) - 1:
        minIndex = i
        for j from i + 1 to length(arr):
            if arr[j] < arr[minIndex]: # 寻找最小的元素
                minIndex = j # 更新最小元素的索引
        swap arr[minIndex] and arr[i] # 交换最小元素和第一个位置的元素
    return arr # 返回排序后的列表

优缺点

优点

  1. 简单易懂，易于实现。
  2. 适用于小规模的数据集。
  3. 可以在部分有序的数据集上进行优化。
  4. 适用于数据集的顺序与最终排序结果的顺序相同的情况。
  5. 适用于对内存要求严格的场景。
  6. 适用于对稳定性要求不高的场景。
  7. 适用于对时间要求不高的场景。
  8. 适用于对空间要求不高的场景。
  9. 适用于对数据集的顺序不敏感的情况。
  10. 适用于对数据集的顺序敏感的情况。

缺点

  1. 效率较低，时间复杂度为O(n^2)。
  2. 需要进行多次交换操作，不适合大规模的数据集。
  3. 不适用于对稳定性要求较高的场景。
  4. 不适用于对时间要求较高的场景。
  5. 不适用于对空间要求较高的场景。

应用场景

  1. 当数据集较小且对时间要求不高时，可以选择使用选择排序。
  2. 当数据集的顺序与最终排序结果的顺序相同且对稳定性要求不高时，可以选择使用选择排序。
  3. 当对内存要求严格时，可以选择使用选择排序。

时间复杂度

  • 最好情况时间复杂度：O(n^2)，当列表已经有序时。
  • 最坏情况时间复杂度：O(n^2)，当列表逆序时。
  • 平均情况时间复杂度：O(n^2)。

为什么时间复杂度是O(n^2)?

时间复杂度分析：

  • 外层循环需要n-1次迭代。
  • 内层循环需要n-1次迭代。
  • 总的时间复杂度为O(n^2)。

如何避免最坏情况下的时间复杂度?

可以使用随机化选择的方法来避免最坏情况下的时间复杂度。每次选择最小值或最大值时，随机选择一个元素进行比较。这样可以保证在最坏情况下，时间复杂度为O(n^2)。但在平均情况下，时间复杂度为O(n)。因此，随机化选择是一种优化方法。但在实际应用中，随机化选择并不常用。因为随机化选择需要额外的空间来存储随机数。并且随机化选择的时间复杂度为O(n)。因此，随机化选择并不常用。

空间复杂度

  • 空间复杂度：O(1)，不需要额外的空间。
  • 原地排序：是。

为什么空间复杂度是O(1)?

空间复杂度分析：

  • 只需要常数个额外的空间来存储临时变量。
  • 总的空间复杂度为O(1)。

代码实现

template <typename T>
void selectionSort(vector<T> &arr)
{
    // n is the size of the array
    int n = arr.size();
    // loop through the array n-1 times
    for (int i = 0; i < n - 1; i++)
    {
        // set the minimum index to i
        int min_index = i;
        // loop through the array from i+1 to n
        for (int j = i + 1; j < n; j++)
        {
            // if the current element is less than the minimum index element
            if (arr[j] < arr[min_index])
            {
                // set the minimum index to the current element
                min_index = j;
            }
        }
        // if the minimum index is not equal to i
        if (min_index != i)
        {
            // swap the elements at index i and min_index
            swap(arr[i], arr[min_index]);
        }
    }
}

这段代码是C++中一个选择排序算法的实现。选择排序是一种简单的排序算法，它的工作原理是不断地选择剩余元素中的最小（或最大）元素，然后将其放到已排序部分的末尾。下面是该算法的详细解释：

  1. 模板参数:
    template <typename T>
    这使得selectionSort函数可以接受任何类型的元素数组，例如整数、浮点数、字符或自定义对象。
  2. 函数参数:
    void selectionSort(vector<T> &arr)
    该函数接受一个类型为T的vector的引用，这意味着任何传入此函数的数组都将在排序过程中被修改。
  3. 获取数组大小:
    int n = arr.size();
    这里，我们获取数组的长度，这样我们就可以在后续的循环中使用它。
  4. 外部循环:
    for (int i = 0; i < n - 1; i++)
    外部循环从数组的第一个元素运行到倒数第二个元素。这是因为最后一个元素将在每次迭代中被正确放置（因为它将是剩余元素中的最大元素）。
  5. 设置最小索引:
    int min_index = i;
    我们假设当前索引i处的元素是未排序部分的最小元素。
  6. 内部循环:
    for (int j = i + 1; j < n; j++)
    内部循环从i+1开始，到数组的末尾结束。这是为了比较未排序部分的每个元素，以找到实际的最小元素。
  7. 找到最小元素:
    if (arr[j] < arr[min_index])
{
    min_index = j;
}
    如果我们发现一个元素小于当前认为的最小元素，我们就更新min_index以指向这个新的最小元素。
  8. 交换元素:
    if (min_index != i)
{
    swap(arr[i], arr[min_index]);
}
    如果我们在未排序部分找到了一个比当前索引i处的元素更小的元素，我们就交换这两个元素。这确保了最小元素被放置在已排序部分的末尾。
  9. 重复:
    外部循环继续，重复此过程，直到数组完全排序。
    选择排序的时间复杂度是 O ( n 2 ) O(n^2) O(n2)，因为它涉及双重循环。这使得它在处理大型数据集时效率不高，但对于小型数据集或几乎已经排序的数据集，它可以相当快速。

上述代码的Python版本：

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]

完整的代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cassert>

using namespace std;

class Person
{
public:
    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;
    int socre;
};

template <typename T>
void selectionSort(vector<T> &arr)
{
    // n is the size of the array
    int n = arr.size();
    // loop through the array n-1 times
    for (int i = 0; i < n - 1; i++)
    {
        // set the minimum index to i
        int min_index = i;
        // loop through the array from i+1 to n
        for (int j = i + 1; j < n; j++)
        {
            // if the current element is less than the minimum index element
            if (arr[j] < arr[min_index])
            {
                // set the minimum index to the current element
                min_index = j;
            }
        }
        // if the minimum index is not equal to i
        if (min_index != i)
        {
            // swap the elements at index i and min_index
            swap(arr[i], arr[min_index]);
        }
    }
}

void basicTypeSelectionSortCase()
{
    vector<int> intArr = {5, 2, 8, 1, 3};
    vector<double> doubleArr = {5.5, 2.2, 8.8, 1.1, 3.3};
    vector<char> charArr = {'g', 'e', 'o', 'r', 'g'};

    selectionSort<int>(intArr);
    selectionSort<double>(doubleArr);
    selectionSort<char>(charArr);

    cout << "Sorted int array: ";
    for (int i : intArr)
    {
        cout << i << " ";
    }
    cout << endl;

    cout << "Sorted double array: ";
    for (double i : doubleArr)
    {
        cout << i << " ";
    }
    cout << endl;

    cout << "Sorted char array: ";
    for (char i : charArr)
    {
        cout << i << " ";
    }
    cout << endl;
}

void personSelecttionSortCase()
{
    // Now I want to write some Person class's quick sort examples in here:
    vector<Person> personArr = {Person("John", 25, 88), Person("Alice", 30, 77), Person("Bob", 20, 66)};
    selectionSort<Person>(personArr);
    cout << "Sorted Person array: ";
    const auto &personSize = personArr.size();
    for (size_t i = 0; i < personSize; i++)
    {
        const auto &person = personArr[i];
        cout << person.getName() << " " << person.getAge() << " " << person.getScore() << endl;
    }
    cout << endl;

    // Now I want to write some Person class's quick sort examples in here:
    vector<Person> personArrNew = {Person("Tom", 35, 77), Person("Panda", 22, 88), Person("Alex", 50, 99)};
    const auto &personSizeNew = personArrNew.size();
    selectionSort<Person>(personArrNew);
    cout << "Sorted Person array: " << endl;
    for (size_t i = 0; i < personSizeNew; i++)
    {
        const auto &person = personArrNew[i];
        cout << person.getName() << " " << person.getAge() << " " << person.getScore() << endl;
    }
    cout << endl;
}

void testSelectionSort()
{
    vector<int> arr1 = {64, 25, 12, 22, 11};
    selectionSort(arr1);
    assert(arr1 == vector<int>({11, 12, 22, 25, 64}));

    vector<int> arr2 = {5, 2, 8, 12, 4};
    selectionSort(arr2);
    assert(arr2 == vector<int>({2, 4, 5, 8, 12}));

    vector<int> arr3 = {9, 3, 1, 6, 5, 2};
    selectionSort(arr3);
    assert(arr3 == vector<int>({1, 2, 3, 5, 6, 9}));

    vector<int> arr4 = {1, 2, 3, 4, 5, 6};
    selectionSort(arr4);
    assert(arr4 == vector<int>({1, 2, 3, 4, 5, 6}));

    vector<int> arr5 = {6, 5, 4, 3, 2, 1};
    selectionSort(arr5);
    assert(arr5 == vector<int>({1, 2, 3, 4, 5, 6}));
}

int main()
{
    testSelectionSort();
    basicTypeSelectionSortCase();
    personSelecttionSortCase();
    return 0;
}

这段C++代码定义了一个Person类，并自定义了比较操作符。Person类有三个成员变量：name、age和score。它还有比较操作符（>、<、==、!=、<=和>=），允许它与其他Person对象根据它们的分数进行比较。

selectionSort函数是一个通用的排序函数，它接受一个向量，并使用选择排序算法对其进行排序。它的原理是遍历向量，找到剩余未排序部分的最小元素，然后将其与未排序部分的第一个元素交换。这个过程会重复，直到整个向量都被排序。

basicTypeSelectionSortCase函数演示了如何使用selectionSort函数，对不同数据类型（int、double和char）进行排序。它创建了整数、双精度浮点数和字符类型的向量，使用selectionSort函数进行排序，然后打印排序后的数组。

personSelecttionSortCase函数演示了如何使用selectionSort函数，对Person类进行排序。它创建了一个Person对象的向量，使用selectionSort函数进行排序，然后打印排序后的数组。

testSelectionSort函数是selectionSort函数的一个测试用例。它创建了一个整数类型的向量，使用selectionSort函数进行排序，然后检查排序后的向量是否与预排序的向量相等。如果排序后的向量与预排序的向量相等，测试通过；否则，测试失败。

在main函数中，调用了testSelectionSort函数，对selectionSort函数进行测试，包括不同数据类型的测试和Person类的测试。如果所有测试都通过，程序将输出"所有测试通过"。

以下是这个代码的Python版本：

class Person:
    def __init__(self, name: str, age: int, score: int):
        self.name = name
        self.age = age
        self.score = score

    def __lt__(self, other):
        return self.score < other.score

    def __le__(self, other):
        return self.score <= other.score

    def __eq__(self, other):
        return self.score == other.score and self.age == other.age and self.name == other.name

    def __ne__(self, other):
        return self.score != other.score or self.age != other.age or self.name != other.name

    def __gt__(self, other):
        return self.score > other.score

    def __ge__(self, other):
        return self.score >= other.score

    def get_name(self):
        return self.name

    def get_age(self):
        return self.age

    def get_score(self):
        return self.score

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]

def test_selection_sort():
    arr1 = [64, 25, 12, 22, 11]
    selection_sort(arr1)
    assert arr1 == [11, 12, 22, 25, 64]

    arr2 = [5, 2, 8, 12, 4]
    selection_sort(arr2)
    assert arr2 == [2, 4, 5, 8, 12]

    arr3 = [9, 3, 1, 6, 5, 2]
    selection_sort(arr3)
    assert arr3 == [1, 2, 3, 5, 6, 9]

    arr4 = [1, 2, 3, 4, 5, 6]
    selection_sort(arr4)
    assert arr4 == [1, 2, 3, 4, 5, 6]

    arr5 = [6, 5, 4, 3, 2, 1]
    selection_sort(arr5)
    assert arr5 == [1, 2, 3, 4, 5, 6]

def basic_type_selection_sort_case():
    int_arr = [5, 2, 8, 1, 3]
    double_arr = [5.5, 2.2, 8.8, 1.1, 3.3]
    char_arr = ['g', 'e', 'o', 'r', 'g']

    selection_sort(int_arr)
    selection_sort(double_arr)
    selection_sort(char_arr)

    print("Sorted int array:", int_arr)
    print("Sorted double array:", double_arr)
    print("Sorted char array:", char_arr)

def person_selection_sort_case():
    person_arr = [Person("John", 25, 88), Person("Alice", 30, 77), Person("Bob", 20, 66)]
    selection_sort(person_arr)
    print("Sorted Person array:")
    for person in person_arr:
        print(person.get_name(), person.get_age(), person.get_score())

    person_arr_new = [Person("Tom", 35, 77), Person("Panda", 22, 88), Person("Alex", 50, 99)]
    selection_sort(person_arr_new)
    print("Sorted Person array:")
    for person in person_arr_new:
        print(person.get_name(), person.get_age(), person.get_score())

if __name__ == "__main__":
    test_selection_sort()
    basic_type_selection_sort_case()
    person_selection_sort_case()

总结

在本文档中，我们学习了如何使用选择排序算法对数组进行排序。我们首先定义了一个选择排序函数，然后使用该函数对不同类型的数组进行排序。最后，我们展示了排序后的数组。希望这个文档对你有所帮助！

扩展阅读

优化时间复杂度的思路

选择排序是一种简单直观的排序算法。它的工作原理是在未排序的序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，因为它需要进行 n − 1 n-1 n−1 轮的比较，每轮比较中需要比较剩余未排序的元素数量，这个数量从 n − 1 n-1 n−1 递减到 1。因此，选择排序并不是一种高效的排序算法，尤其是在处理大数据集时。
尽管如此，选择排序算法的优化主要集中在减少比较次数上，但它的基本时间复杂度很难有大的改进。下面是一些优化选择排序的尝试：

  1. 跳跃选择排序（Jump Selection Sort）:
    在每一轮选择最小（或最大）元素时，可以跳过一些元素。例如，第一轮跳过1个元素，第二轮跳过2个元素，以此类推。这样可以稍微减少比较次数，但时间复杂度仍然是 O ( n 2 ) O(n^2) O(n2)。
  2. 双向选择排序（Bidirectional Selection Sort）:
    也称为双边选择排序，这种方法每一轮同时找到最大和最小元素，并放到序列的两端。这样可以将排序过程减半，但每轮的比较次数仍然是 O ( n ) O(n) O(n)，因此总体的时间复杂度仍然是 O ( n 2 ) O(n^2) O(n2)。
  3. 使用更高效的交换方法:
    在某些情况下，可以优化交换两个元素的方法，例如使用异或运算。但这种方法对时间复杂度的改善有限。
  4. 并行化:
    选择排序的一个潜在优化是并行化处理。每一轮可以并行地找到最小（或最大）元素，特别是在多核处理器上。但这种方法的主要限制是并行处理本身的复杂性，以及可能存在的并行开销。
    总的来说，选择排序的优化主要是减少比较次数，但它们并不能改变其 O ( n 2 ) O(n^2) O(n2) 的时间复杂度。对于大多数实际应用，更高效的排序算法（如快速排序、归并排序或堆排序）通常是更好的选择。

跳跃选择排序（Jump Selection Sort）

跳跃选择排序（Jump Selection Sort）是选择排序的一种变种，它通过减少比较的次数来提高效率。在跳跃选择排序中，不是每次都只比较相邻的两个元素，而是每次跳过多个元素，比较剩余未排序元素中的最小（或最大）元素，并将其放到正确的位置。
跳跃选择排序的基本步骤如下：

  1. 计算跳跃长度:
    确定每次跳跃的长度。这通常是通过分析数据集的特性来完成的。例如，如果数据已经部分排序，跳跃长度可以从1逐渐增加到数据集的大小。
  2. 跳跃选择:
    从第一个元素开始，跳过跳跃长度个元素，然后找到剩余未排序元素中的最小（或最大）元素，并将其放到当前位置。
  3. 重复:
    继续跳跃选择，直到所有元素都被处理。
    以下是跳跃选择排序的伪代码：
function jump_selection_sort(arr):
    n = length(arr)
    
    # 初始化跳跃长度为数据集大小
    for step in range(n):
        # 假设最小元素在当前元素
        min_index = step
        
        # 跳过跳跃长度个元素
        for i in range(step + 1, step + jump_length + 1):
            # 检查是否找到更小的元素
            if arr[i] < arr[min_index]:
                min_index = i
        
        # 交换元素
        swap(arr[step], arr[min_index])

对于C++的模板实现，我们可以使用以下代码：

// The jump selection sort function.
template <typename T>
void jumpSelectionSort(vector<T> &arr)
{
    // n is the size of the array
    int n = arr.size();
    // step is the jump size
    int step = n / 2;
    // while step is greater than 0
    while (step > 0)
    {
        // for each element in the array
        for (int i = 0; i + step < n; i++)
        {
            // min_index is the index of the minimum element
            // in the sub array from i to i + step

            int min_index = i;
            // for each element in the sub array from i to i + step
            for (int j = i + 1; j <= i + step && j < n; j++)
            {
                // if the element at j is less than the element at min_index
                if (arr[j] < arr[min_index])
                {
                    // set min_index to j
                    min_index = j;
                }
            }

            // if the element at min_index is not equal to i
            if (min_index != i)
            {
                // swap the elements at i and min_index
                swap(arr[i], arr[min_index]);
            }
        }

        // set step to be half of the previous step
        step = step / 2;
    }
}

template <typename T>
void testJumpSelectionSort(vector<T> &testVec)
{
    auto sortedArr = testVec;
    sort(sortedArr.begin(), sortedArr.end());
    jumpSelectionSort<T>(testVec);

    if (testVec == sortedArr)
    {
        cout << "Test passed for the given test case!" << endl;
    }
}

void jumpSelectionSortCase()
{
    vector<int> arr{3, 7, 9, 1, 2, 6, 8, 4, 5};
    testJumpSelectionSort<int>(arr); // Test case 1: Passed.
    // ... other test cases ...
    vector<double> dArr{3.0, 7.0, 9.0, 1.0, 2.0, 6.0, 8.0, 4.0, 5.0};
    testJumpSelectionSort<double>(dArr); // Test case 2: Passed.
    vector<float> fArr{3.0f, 7.0f, 9.0f, 1.0f, 2.0f, 6.0f, 8.0f, 4.0f, 5.0f};
    testJumpSelectionSort<float>(fArr); // Test case 3: Passed.
    vector<char> cArr{'c', 'a', 'b'};
    testJumpSelectionSort<char>(cArr); // Test case 4: Passed.
    vector<Person> personArr{Person("Alice", 25, 80), Person("Bob", 20, 65), Person("Charlie", 22, 77)};
    testJumpSelectionSort<Person>(personArr); // Test case 5: Passed.
}

请注意，跳跃选择排序的性能改进依赖于跳跃长度的选择。在某些情况下，它可能比基本的 O ( n 2 ) O(n^2) O(n2)选择排序要快，但通常情况下，它仍然不如 O ( n log ⁡ n ) O(n \log n) O(nlogn)的排序算法，如快速排序、归并排序或堆排序。

双向选择排序（Bidirectional Selection Sort）

双向选择排序（Bidirectional Selection Sort）是选择排序的一种变体，它在每一步排序中同时找到最大值和最小值，并将它们放到已排序部分的正确位置。这样，每一步可以减少两次交换操作，从而在某些情况下比传统的选择排序稍微高效一些。

双向选择排序的基本思想是：

  1. 在未排序的部分找到最小元素，并将其放到已排序部分的起始位置。
  2. 在未排序的部分找到最大元素，并将其放到已排序部分的末尾位置。
  3. 重复上述步骤，每次减少未排序部分的边界，直到整个数组被排序。

伪代码如下：

function bidirectionalSelectionSort(arr):
    n = length(arr)
    for i from 0 to n/2:
        # 找到[i, n-i-1]区间内的最小元素的索引
        min_index = i
        for j from i+1 to n-i-1:
            if arr[j] < arr[min_index]:
                min_index = j
        # 将找到的最小元素交换到位置i
        swap(arr[i], arr[min_index])
        # 如果最大元素的索引小于当前的最小元素索引，需要调整
        if min_index == i:
            max_index = min_index
        else:
            max_index = i
        # 找到[i, n-i-1]区间内的最大元素的索引
        for j from i+1 to n-i-1:
            if arr[j] > arr[max_index]:
                max_index = j
        # 将找到的最大元素交换到位置n-i-1
        swap(arr[n-i-1], arr[max_index])

下面是C++模板的实现代码：

template <typename T>
void bidirectionalSelectionSort(vector<T> &arr)
{
    // n is the size of the array
    int n = arr.size();
    // loop from 0 to n/2
    for (int i = 0; i < n / 2; ++i)
    {
        // set the min and max index to i
        int min_index = i, max_index = i;
        // loop from i+1 to n-i-1
        for (int j = i + 1; j <= n - i - 1; ++j)
        {
            // if arr[j] is less than arr[min_index]
            if (arr[j] < arr[min_index])
            {
                // set min_index to j
                min_index = j;
            }
            // if arr[j] is greater than arr[max_index]
            if (arr[j] > arr[max_index])
            {
                // set max_index to j
                max_index = j;
            }
        }

        // if min_index is not equal to i
        if (min_index != i)
        {
            // swap arr[i] and arr[min_index]
            swap(arr[i], arr[min_index]);
        }

        // if max_index is equal to i
        if (max_index == i)
        {
            // set max_index to min_index
            max_index = min_index;
        }

        // if max_index is not equal to n-i-1
        if (max_index != n - i - 1)
        {
            // swap arr[n-i-1] and arr[max_index]
            swap(arr[n - i - 1], arr[max_index]);
        }
    }
}

template <typename T>
void printResult(vector<T>& data)
{
    bidirectionalSelectionSort(data);
    cout << "Sorted array: \n";
    for (T value : data)
    {
        cout << value << " ";
    }
    cout << endl;
}

void bidirectionalSelectionSortCase()
{
    // Sort a double array
    vector<double> doubleData = {64.0, 34.0, 25.0, 12.0, 22.0, 11.0, 90.0};
    printResult(doubleData);

    // Sort an int array
    vector<int> intData = {64, 34, 25, 12, 22, 11, 90};
    printResult(intData);

    // Sort a char array
    vector<char> charData = {'d', 'b', 'a', 'c'};
    printResult(charData);
}

在这个C++实现中，我们使用模板使得bidirectionalSelectionSort函数可以接受任何类型的vector，只要该类型支持比较操作。在main函数中，我们展示了如何使用这个模板化的函数来排序double和int类型的数组。

个人格言

追寻与内心共鸣的生活，未来会逐渐揭晓答案。

Pursue the life that resonates with your heart, and the future will gradually reveal the answer.

在这里插入图片描述

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

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

相关文章

【Java程序员面试专栏 算法思维】四 高频面试算法题：回溯算法

【Java程序员面试专栏 算法思维】四 高频面试算法题：回溯算法

一轮的算法训练完成后，对相关的题目有了一个初步理解了，接下来进行专题训练，以下这些题目就是汇总的高频题目，本篇主要聊聊回溯算法，主要就是排列组合问题，所以放到一篇Blog中集中练习 题目关键字解题思路时间空间岛屿数量网格搜索分别向上下左右四个方向探索，遇到海洋…
阅读更多...
R绘图 | 单列数据的分布图，对A变量分bin求B变量的平均值

R绘图 | 单列数据的分布图，对A变量分bin求B变量的平均值

问题1&#xff1a;单个向量的 density 分布图&#xff1f; (1) 模拟数据 set.seed(202402) datdiamonds[sample(nrow(diamonds), 1000),]> head(dat) # A tibble: 6 10carat cut color clarity depth table price x y z<dbl> <ord> &l…
阅读更多...
迎元宵，守平安 |《一颗汤圆的历险记》

迎元宵，守平安 |《一颗汤圆的历险记》

阅读更多...
数据可视化引领智慧仓储新时代

数据可视化引领智慧仓储新时代

随着科技的飞速发展&#xff0c;数据可视化已然成为智慧仓储领域的璀璨明珠&#xff0c;其强大的功能和多面的作用让智慧仓储焕发出勃勃生机。让我们一同探索&#xff0c;数据可视化究竟在智慧仓储中起到了怎样的作用。下面我就以可视化从业者的角度来简单谈谈这个话题。 在这…
阅读更多...
Linux——进程概念

Linux——进程概念

目录 冯诺依曼体系结构 操作系统 管理 系统调用和库函数 进程的概念 进程控制块——PCB 查看进程 通过系统调用获取进程标示符 通过系统调用创建进程 进程状态 运行状态-R ​编辑 浅度睡眠状态-S 深度睡眠状态-D 暂停状态-T 死亡状态-X 僵尸状态-Z 僵尸进程…
阅读更多...
详解顺序结构滑动窗口处理算法

详解顺序结构滑动窗口处理算法

&#x1f380;个人主页&#xff1a; https://zhangxiaoshu.blog.csdn.net &#x1f4e2;欢迎大家&#xff1a;关注&#x1f50d;点赞&#x1f44d;评论&#x1f4dd;收藏⭐️&#xff0c;如有错误敬请指正! &#x1f495;未来很长&#xff0c;值得我们全力奔赴更美好的生活&…
阅读更多...
WPF 附加属性+控件模板，完成自定义控件。建议观看HandyControl源码

WPF 附加属性+控件模板，完成自定义控件。建议观看HandyControl源码

文章目录 相关连接前言需要实现的效果附加属性添加附加属性&#xff0c;以Test修改FontSize为例依赖属性使用触发器使用直接操控 结论 控件模板&#xff0c;在HandyControl的基础上面进行修改参考HandyControl的源码控件模板原型控件模板 控件模板触发器完整样式简单使用 结论 …
阅读更多...
光学3D表面轮廓仪微纳米三维形貌一键测量

光学3D表面轮廓仪微纳米三维形貌一键测量

光学3D表面轮廓仪(白光干涉仪)利用白光干涉原理&#xff0c;以0.1nm分辨率精准捕捉物体的表面细节&#xff0c;实现三维显微成像测量&#xff0c;被广泛应用于材料学领域的研究和应用。 了解工作原理与技术 材料学领域中的光学3D表面轮廓仪&#xff0c;也被称为白光干涉仪&am…
阅读更多...
低价对品牌渠道的危害

低价对品牌渠道的危害

品牌价值的体现主要在价格&#xff0c;比如要与竞品体现差异&#xff0c;除了产品功能上有做出差异&#xff0c;价格上也需要设置不同的阶梯&#xff0c;但如果经销商不遵守这个体系&#xff0c;或者非授权店铺随意低价&#xff0c;对于品牌来说都是非常不好的事情&#xff0c;…
阅读更多...
Django后台管理（二）

Django后台管理（二）

一、自定义注册管理类介绍 官网：Django 管理站点 | Django 文档 | Django 注册模型除了使用 Django 默认的管理类admin，也可以自定义，比如： class StudentAdmin(admin.ModelAdmin):pass admin.site.register(Student, StudentAdmin)ModelAdmin 类是管理界面中模型的表示。…
阅读更多...
微信小程序 wxs内联与外联的写法

微信小程序 wxs内联与外联的写法

内联写法 <!-- 内联wxs --> <view>大写字母{{m1.toUpper("xmly")}}</view> <wxs module"m1">module.exports.toUpperfunction(str){return str.toUpperCase()} </wxs> 外联写法 新建一个wxs文件 写一个函数&#xff0c;将…
阅读更多...
架构（十五）Java字节码增强

架构（十五）Java字节码增强

一、引言 一般如果需要做增强类的架构工具会使用SpringBoot提供的切面&#xff0c;但是这逃不开两个问题&#xff1a;1、使用方需要加注解代码&#xff1b;2、版本更新导致的发布。 所以java还提供了字节码层面的增强方案&#xff0c;对使用的系统是无感的。 二、字节码增强选…
阅读更多...
BLEU: a Method for Automatic Evaluation of Machine Translation

BLEU: a Method for Automatic Evaluation of Machine Translation

文章目录 BLEU: a Method for Automatic Evaluation of Machine Translation背景和意义技术原理考虑 n n n - gram中 n 1 n1 n1 的情况考虑 n n n - gram中 n > 1 n\gt 1 n>1 的情况考虑在文本中的评估初步实验评估和结论统一不同 n n n 值下的评估数值考虑句子长度…
阅读更多...
Ubuntu上Jenkins自动化部署Gitee上SpringBoot项目

Ubuntu上Jenkins自动化部署Gitee上SpringBoot项目

文章目录 安装安装JDK安装Maven安装GitNodeJS安装&#xff08;可选&#xff09;安装Jenkins 配置Jenkins为Jenkins更换插件源设置jenkins时区安装插件全局工具配置添加Gitee凭证Gitee项目配置 部署后端1.新建任务2.配置源码管理3.构建触发器4.到Gitee中添加WebHook5.构建环境6.…
阅读更多...
C++——基础语法（3）：内联函数、auto关键字、基于范围的for循环、空指针nullptr

C++——基础语法（3）：内联函数、auto关键字、基于范围的for循环、空指针nullptr

6. 内联函数 在函数前加入inline修饰即可将函数变为内联函数。所谓内联函数&#xff0c;就是在编译时C编译器会将函数体在调用内联函数的地方展开&#xff0c;从而省去了调用函数的栈帧开销&#xff0c;提高程序运行效率。 inline int Add(int a, int b) {return a b; } int …
阅读更多...
十一、计算机视觉-膨胀操作

十一、计算机视觉-膨胀操作

文章目录 前言一、什么是膨胀二、膨胀操作的实现1.引入库 三、膨胀的原理 前言 上节我们学习了腐蚀操作&#xff0c;本节我们讲一下膨胀操作&#xff0c;膨胀和腐蚀实际上是相反的操作。上节我们把云峰这2个字周围没用的像素去掉了&#xff0c;但是云峰这2个字也变细了&#x…
阅读更多...
Protocol Buffer-nanopb介绍

Protocol Buffer-nanopb介绍

文章目录 一、需求二、环境三、相关概念3.1 protocol buffer介绍3.2 nanopb&#xff08;支持C语言&#xff09;3.3 proto文件 四、proto基本语法4.1 proto文件的定义4.2 字段规则4.3 字段类型4.4 字段编号4.5 proto语法4.6 进阶语法4.6.1 message嵌套4.6.2 enum关键字4.6.3 one…
阅读更多...
【Flink精讲】Flink状态及Checkpoint调优

【Flink精讲】Flink状态及Checkpoint调优

RocksDB大状态调优 RocksDB 是基于 LSM Tree 实现的&#xff08;类似 HBase&#xff09; &#xff0c;写数据都是先缓存到内存中&#xff0c; 所以 RocksDB 的写请求效率比较高。 RocksDB 使用内存结合磁盘的方式来存储数据&#xff0c;每 次获取数据时&#xff0c;先从内存中 …
阅读更多...
什么是高可用架构

什么是高可用架构

一、什么是高可用 在运维中&#xff0c;经常听到高可用&#xff0c;那么什么是高可用架构呢&#xff1f;通俗点讲&#xff0c;高可用就是在服务故障&#xff0c;节点宕机的情况下&#xff0c;业务能够保证不中断&#xff0c;服务正常运行。 举个例子&#xff0c;支付宝&#…
阅读更多...
GS069——直流有刷电机调速电路 通过外接电阻网络，改变与之相接的 VMOS 管的输出，达到控制电动工具 转速的作用。 功耗小，电源电压范围宽。

GS069——直流有刷电机调速电路 通过外接电阻网络，改变与之相接的 VMOS 管的输出，达到控制电动工具 转速的作用。 功耗小，电源电压范围宽。

GS069电动工具直流调速电路是CMOS专用集成电路&#xff0c;具有电源电压范 围宽、功耗小、抗干扰能力强等特点。通过外接电阻网络&#xff0c;改变与之相接 的VMOS 管的输出&#xff0c;达到控制电动工具转速的作用。该电路输出幅值宽&#xff0c; 频率变化小&#xff0c;占空比…
阅读更多...
最新文章

Copyright @ 2022~2023