The sorting algorithm in STl is analyzed in detail

1. List of names of all STL sort algorithm functions:

The function name       Functional description

sort   Sort all elements of a given interval

Stable_sort performs a stable sort for all elements in a given interval

The partial_sort sorts all element parts of a given interval

partial_sort_copy       Copy and sort the given interval

Nth_element finds the element corresponding to a position in a given interval

is_sorted                             Determines whether an interval is ordered

partition       The element that meets a condition is placed first

stable_partition           Relatively stable so that the elements that meet certain conditions are put in front

2. Comparison function:

When you need to sort in a particular way, you need to specify a comparison function for sort, otherwise the program will automatically provide you with a comparison function

The vector < int > Vect;

Sort (vect. The begin (), vect end ()); // is the equivalent of a call

Sort (vect. The begin (), vect end (), less < int > ());

Other comparison functions in sort

Equal_to equal

Not_equal_to unequal

Less than

Greater than the

Less_equal is less than or equal to

Greater_equal is greater than or equal to

In the example above, the system itself provides the less functor for sort. Other functors are provided in the STL, and here is a list of functors: instead of writing the name of the functor directly, write its overloaded () function: less < int > (a);

You can use these function templates directly when your container has elements of some standard type (int float char) or string. But if you define your own type or if you need to sort it in some other way, you can do it in two ways: you can write your own comparison function. The other is' of an overloaded type < 'operation.

3. Full sorting:

Full sort is the ordering of all elements in a given range in order of size. Sort USES a mature "quicksort algorithm" (most current versions of STL don't use a simple quicksort, but instead use an interpolation sort algorithm). N times log n. Stable_sort USES merge sort, n*log(n) for allocating enough memory, or n*log(n)*log(n), with the advantage of keeping the relative positions of equal elements consistent before and after sorting.

The functions for full sort are:

1. Void sort(RandomAccessIterator first, RandomAccessIterator last);

2. Void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);

3. Void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

4. Void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

4. Local sorting:

The partial_sort takes the heapsort, which in any case is n*log(n).

Local sort is a sort provided to reduce unnecessary operations.

Its function prototype is:

4.1 Void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

4.2 Void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering comp);

4.3 RandomAccessIterator partial_sort_copy (InputIterator first, InputIteratorlast RandomAccessIteratorresult_first, RandomAccessIterator result_last);

4.4 RandomAccessIterator partial_sort_copy (InputIterator first, InputIteratorlast RandomAccessIteratorresult_first, RandomAccessIterator result_last, Compare comp);

There are 1000 students in the class, and I want to know who are the five with the lowest marks.

Partial_sort (vect. The begin (), vect. The begin () + 5, vect. The end (), less < student > ());

5. Nth_element specifies the element sort

5.1 Void nth_element(RandomAccessIterator first, RandomAccessIterator NTH, RandomAccessIterator last);

5.2 Void nth_element(RandomAccessIterator first, RandomAccessIterator NTH,RandomAccessIterator last,

StrictWeakOrdering comp);

There are 1000 students in the class, and I want to know the student whose mark is the fourth from the bottom.

Nth_element (vect. The begin (), vect. The begin () + 3, vect. The end (), less < student > ());

6. Partition and stable_partition

Partition is to divide the elements of an interval into two categories according to certain conditions without sorting them.

Its function prototype is:

6.1 ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)

6.2 ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);

For example: 10 students in the class, count all the students who failed (below 60) :

Student exam (" pass ", 60);

Stable_partition (vect. The begin (), vect. The end (), bind2nd (less < student > (), exam));

7. From high efficiency to low efficiency (from small time to large time) :

partion

stable_partition

nth_element

partial_sort

sort

stable_sort

8. Effective STL has a good summary of how to select sorting functions:

8.1 To fully sort a vector, string, deque, or array container, you can select sort or stable_sort;

8.2 Partial sorting partial_sort is preferred if you only need to get top n elements in a vector, string, deque, or array container.

8.3 If for a vector, string, deque, or array container, you need to find the element in the NTH position or you need to get top n and not the inner order in top n, nth_element is ideal;

8.4 Partition or stable_partition is best if you need to separate elements that meet or do not meet a condition from the standard sequence container or array.

8.5 If you use a list container, you can use the partition and stable_partition algorithms directly. You can use list::sort instead of sort and stable_sort.