Detailed explanation of sorting function in C++

The sort function in C is a functional function used to sort the elements in an array or container. Sorting can be in ascending or descending order, and various types of data such as integer, floating point, and character types can be sorted. C language provides multiple sorting functions. This article will introduce the usage and characteristics of these sorting functions in detail.

1. sort() function

The sort() function is one of the most commonly used sorting functions in C STL. Its function is to arrange the elements in an array or container. . The basic usage of the sort() function is as follows:

sort(begin, end);

Among them, begin is the address of the first element in the array or container, and end is the address 1 of the last element, so end points to the empty address after the last element. . The sort() function sorts in ascending order by default. If you need to sort in descending order, you can pass in a function pointer or lambda expression as the third parameter.

The following is a sample code that demonstrates how to use the sort() function to sort an integer array:

#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;
}

The result of running the above code is as follows:

1 2 3 4 5 6 7 8 9

2. stable_sort() function

stable_sort() function is similar to sort() function, but it ensures that the relative positions of elements with the same value remain unchanged after sorting. The usage of the stable_sort() function is similar to the sort() function. You can also pass in a function pointer or lambda expression as the third parameter. The following is a sample code:

#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;
}

The result of running the above code is as follows:

1 2 3 4 5 6 7 8 9

3. partial_sort() function

partial_sort() function can convert an array or The elements in the container are partially sorted, that is, the top k smallest elements are sorted in front of the array (or the top k largest elements are sorted in front of the array). The usage is as follows:

partial_sort(begin, middle, end);

where begin is the address of the first element in the array or container, end is the address 1 of the last element, and middle is an iterator pointing to the k-th element. It should be noted that the partial_sort() function only guarantees that the first k elements are in order, and the order of the remaining elements is undefined. The following is a sample code:

#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;
}

The result of running the above code is as follows:

1 2 3

4. nth_element() function

nth_element() function is used to select an array Or the kth smallest (or kth largest) element in the container and arrange it at the kth position in the array. The usage is as follows:

nth_element(begin, middle, end);

where begin is the address of the first element in the array or container, end is the address 1 of the last element, and middle is an iterator pointing to the k-th element. It should be noted that the nth_element() function only guarantees that the first k elements of the array are ordered, while the kth element is unsorted. The following is a sample code:

#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;
}

The result of running the above code is as follows:

第 3 小的数是：3

5. make_heap() function

make_heap() function can convert an array or The container is converted into a heap, that is, the elements in the array are sorted according to the rules of the binary heap to support heap operations. The usage is as follows:

make_heap(begin, end);

where begin is the address of the first element in the array or container, and end is the address of the last element 1. The following is a sample code:

#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;
}

The result of running the above code is as follows:

9 7 8 6 4 3 5 1 2

6. push_heap() function

push_heap() function can push a new Elements are inserted into the heap and the structure of the heap is restructured to suit the properties of the heap. The usage is as follows:

push_heap(begin, end);

where begin is the address of the first element in the array or container, and end is the address of the last element. It should be noted that the inserted new element should be placed at the last position of the heap. The following is a sample code:

#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;
}

The result of running the above code is as follows:

9 7 8 6 4 3 5 1 2 0

7. pop_heap() function

pop_heap() function is used to convert the heap The top element pops out and the heap is restructured to suit the nature of the heap. The usage is as follows:

pop_heap(begin, end);

where begin is the address of the first element in the array or container, and end is the address of the last element. It should be noted that after popping the top element of the heap, the size of the heap should be reduced by 1. The following is a sample code:

#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;
}

The result of running the above code is as follows:

8 7 5 6 4 3 2 1

8. sort_heap() function

sort_heap() function is used to sort the heap Sort and ensure that the sorted array is in ascending order. The usage is as follows:

sort_heap(begin, end);

where begin is the address of the first element in the array or container, and end is the address of the last element. It should be noted that the sort_heap() function will first call the pop_heap() function to pop the top element of the heap before sorting the heap, so the size of the sorted array should be reduced by 1. The following is a sample code:

#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;
}

The result of running the above code is as follows:

1 2 3 4 5 6 7 8 9

Summary

This article introduces in detail the common sorting functions in C, including sort(), stable_sort (), partial_sort(), nth_element(), make_heap(), push_heap(), pop_heap() and sort_heap() functions. Each of these sorting functions has its own characteristics and can meet different sorting needs. In actual programming, it is very important to choose the appropriate sorting function according to the specific situation.

The above is the detailed content of Detailed explanation of sorting function in C++. For more information, please follow other related articles on the PHP Chinese website!