C++中的排序函数详解

C++ 中的排序函数是用于对数组或容器中的元素进行排序的功能函数。排序可以按升序或降序排列，可以对整型、浮点型、字符型等各种类型的数据进行排序。C++ 语言提供了多个排序函数，本文将对这些排序函数的使用方法和特点进行详细介绍。

1. sort()函数

sort() 函数是 C++ STL 中最常用的排序函数之一，其功能是对数组或容器中的元素进行排列。sort() 函数的基本用法如下：

sort(begin, end);

其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址 + 1，因此 end 指向最后一个元素后面的空地址。sort() 函数默认按升序排序，如果需要按降序排序，则可以传入一个函数指针或 lambda 表达式作为第三个参数。

下面是一个示例代码，演示了如何使用 sort() 函数对整型数组进行排序：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

运行上述代码结果如下：

1 2 3 4 5 6 7 8 9

2. stable_sort() 函数

stable_sort() 函数与 sort() 函数相似，但它保证在排序后，相同值的元素的相对位置不变。stable_sort() 函数的使用方法与 sort() 函数类似，也可以传入一个函数指针或 lambda 表达式作为第三个参数。下面是一个示例代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    stable_sort(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

运行上述代码结果如下：

1 2 3 4 5 6 7 8 9

3. partial_sort() 函数

partial_sort() 函数可以将数组或容器中的元素部分排序，即将前 k 小的元素排在数组前面（或将前 k 大的元素排在数组前面）。使用方法如下：

partial_sort(begin, middle, end);

其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址 + 1，而 middle 是一个指向第 k 个元素的迭代器。需要注意的是，partial_sort() 函数只保证前 k 个元素是有序的，其余元素的顺序是不确定的。下面是一个示例代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    int k = 3;

    partial_sort(arr, arr + k, arr + n);

    for (int i = 0; i < k; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

运行上述代码结果如下：

1 2 3

4. nth_element() 函数

nth_element() 函数用于选取数组或容器中的第 k 小（或第 k 大）元素，并将其排在数组的第 k 个位置。使用方法如下：

nth_element(begin, middle, end);

其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址 + 1，而 middle 是一个指向第 k 个元素的迭代器。需要注意的是，nth_element() 函数只保证数组的前 k 个元素是有序的，而第 k 个元素则是未排序的。下面是一个示例代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    int k = 3;

    nth_element(arr, arr + k - 1, arr + n);

    cout << "第 " << k << " 小的数是：" << arr[k - 1] << endl;

    return 0;
}

运行上述代码结果如下：

第 3 小的数是：3

5. make_heap() 函数

make_heap() 函数可以将数组或容器转化为堆，即将数组中的元素按照二叉堆的规则进行排序，以支持堆操作。使用方法如下：

make_heap(begin, end);

其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址 + 1。下面是一个示例代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

运行上述代码结果如下：

9 7 8 6 4 3 5 1 2

6. push_heap() 函数

push_heap() 函数可以将一个新元素插入到堆中，并重新调整堆的结构，以满足堆的性质。使用方法如下：

push_heap(begin, end);

其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址。需要注意的是，被插入的新元素应当放在堆的最后一个位置。下面是一个示例代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    arr[n] = 0;

    push_heap(arr, arr + n + 1);

    for (int i = 0; i < n + 1; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

运行上述代码结果如下：

9 7 8 6 4 3 5 1 2 0

7. pop_heap() 函数

pop_heap() 函数用于将堆顶元素弹出，并重新调整堆的结构，以满足堆的性质。使用方法如下：

pop_heap(begin, end);

其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址。需要注意的是，弹出堆顶元素后，堆的大小应当减 1。下面是一个示例代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    pop_heap(arr, arr + n);

    n--;

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

运行上述代码结果如下：

8 7 5 6 4 3 2 1

8. sort_heap() 函数

sort_heap() 函数用于将堆排序，并且保证排序后的数组是升序的。使用方法如下：

sort_heap(begin, end);

其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址。需要注意的是，sort_heap() 函数在对堆排序之前会先调用 pop_heap() 函数，弹出堆顶元素，因此排序后的数组大小应当减 1。下面是一个示例代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    sort_heap(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

运行上述代码结果如下：

1 2 3 4 5 6 7 8 9

总结

本文详细介绍了 C++ 中常见的排序函数，包括 sort()、stable_sort()、partial_sort()、nth_element()、make_heap()、push_heap()、pop_heap() 和 sort_heap() 函数。这些排序函数各有特点，可以满足不同的排序需求。在实际编程中，根据具体情况选择适当的排序函数非常重要。

以上是C++中的排序函数详解的详细内容。更多信息请关注PHP中文网其他相关文章！