C++ 算法篇 std::sort

STL

Defined in header <algorithm>
template< class RandomIt >
void sort( RandomIt first, RandomIt last );
(until C++20)
template< class RandomIt >
constexpr void sort( RandomIt first, RandomIt last );
(since C++20)
template< class ExecutionPolicy, class RandomIt >
void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last );
(since C++17)
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );
(until C++20)
template< class RandomIt, class Compare >
constexpr void sort( RandomIt first, RandomIt last, Compare comp );
(since C++20)
template< class ExecutionPolicy, class RandomIt, class Compare >
void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );
(since C++17)

Sorts the elements in the range [first, last) in ascending order. The order of equal elements is not guaranteed to be preserved.

1) Elements are compared using operator<.

3) Elements are compared using the given binary comparison function comp.

2,4) Same as (1,3), but executed according to policy. These overloads do not participate in overload resolution unless std::is_execution_policy_v<std::decay_t> is true

Parameters

  • first, last - the range of elements to sort

  • policy - the execution policy to use. See execution policy for details.

  • comp - comparison function object (i.e. an object that satisfies the requirements of Compare ) which returns true if the first argument is less than (i.e. is ordered before) the second. 若第一参数小于(即序于)第二参数则返回 true。

    The signature of the comparison function should be equivalent to the following:

1
bool cmp(const Type1 &a, const Type2 &b);

While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)).虽然签名不必有 const & ,函数也不能修改传递给它的对象,而且必须接受(可为 const 的)类型 Type1Type2 的值,无关乎值类别(从而不允许 Type1 & ,亦不允许 Type1 ,除非 Type1 的移动等价于复制(C++11 起))。
The types Type1 and Type2 must be such that an object of type RandomIt can be dereferenced and then implicitly converted to both of them. 类型 Type1 与 Type2 必须使得 RandomIt 类型的对象能在解引用后隐式转换到这两个类型。

Complexity

O(N·log(N)), where N = std::distance(first, last) comparisons on average. (until C++11)
O(N·log(N)), where N = std::distance(first, last) comparisons. (since C++11)

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <algorithm>
#include <functional>
#include <array>
#include <iostream>

int main()
{
std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

// sort using the default operator<
std::sort(s.begin(), s.end());
for (auto a : s) {
std::cout << a << " ";
}
std::cout << '\n';

// sort using a standard library compare function object
std::sort(s.begin(), s.end(), std::greater<int>());
for (auto a : s) {
std::cout << a << " ";
}
std::cout << '\n';

// sort using a custom function object
struct {
bool operator()(int a, int b) const
{
return a < b;
}
} customLess;
std::sort(s.begin(), s.end(), customLess);
for (auto a : s) {
std::cout << a << " ";
}
std::cout << '\n';

// sort using a lambda expression
std::sort(s.begin(), s.end(), [](int a, int b) {
return a > b;
});
for (auto a : s) {
std::cout << a << " ";
}
std::cout << '\n';
}

Output:

1
2
3
4
0 1 2 3 4 5 6 7 8 9 
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

how to implement ?

Quicksort

  • Also known as (partition-exchange sort).

  • Average : O(nlogn), Worst : O(n^2),但一般O(n^2)不常见。

  • Faster than other O(nlogn) algorithms,因为Quicksort的inner loop在大部分的架构上很有效率被实现。

Algorithm

  • divide and conquer algorithm:

    把一个序列分为两个子序列,再递归地解决这些子问题,最后这些子问题地组合为原问题的解。

  • The steps are:

    1. Pick a pivot
    2. Partitioning
    3. Recursively

Partition

Easy-version(S:Ω(n))

Pseudocode:

1
2
3
4
5
6
7
8
9
10
11
12
function quicksort(q)
var list less, pivotList, greater
if length(q) ≤ 1 {
return q
} else {
select a pivot value pivot from q
for each x in q except the pivot element
if x < pivot then add x to less
if x ≥ pivot then add x to greater
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}

需要Ω(n)的额外存储空间,跟Mergesort一样不好。额外需要的存储器空间配置,在实际上的实现,也会极度影响速度和缓存的性能。

In-place-version(S:O(log n))

有一个比较复杂使用原地(in-place)分区算法的版本,且在好的基准选择上,平均可以达到O(log n)空间的使用复杂度。

Pseudocode:

1
2
3
4
5
6
7
8
9
10
function partition(a, left, right, pivotIndex)
pivotValue := a[pivotIndex]
swap(a[pivotIndex], a[right]) // 把pivot移到結尾
storeIndex := left
for i from left to right-1
if a[i] <= pivotValue
swap(a[storeIndex], a[i])
storeIndex := storeIndex + 1
swap(a[right], a[storeIndex]) // 把pivot移到它最後的地方
return storeIndex

这是原地分区算法,它分区了标示为”左边(left)”和”右边(right)”的序列部分,借由移动小于a[pivotIndex]的所有元素到子序列的开头,留下所有大于或等于的元素接在他们后面。在这个过程它也为基准元素找寻最后摆放的位置,也就是它回传的值。它暂时地把基准元素移到子序列的结尾,而不会被前述方式影响到。由于算法只使用交换,因此最后的数列与原先的数列拥有一样的元素。要注意的是,一个元素在到达它的最后位置前,可能会被交换很多次。
一旦我们有了这个分区算法,要写快速排列本身就很容易:

Pseudocode:

1
2
3
4
5
6
procedure quicksort(a, left, right)
if right > left
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
quicksort(a, left, pivotNewIndex-1)
quicksort(a, pivotNewIndex+1, right)

Implementation

One-way scanning

arr = [3,7,8,5,2,1,9,5,4]

从左到右(除了最后的基准元素),循环移动小于基准元素 5 的所有元素到数组开头,留下大于等于基准元素的元素接在后面。在这个过程它也为基准元素找寻最后摆放的位置。

In C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int random(int min,int max)
{
int random =rand()%(max-min+1) +min;
return random;
}

void swap(int *in1,int* in2){
int temp=*in1;
*in1=*in2;
*in2=temp;
}

int Partition(vector<int>& nums,int start,int end)
{
if(start<0||end>=nums.size())
return 0;

int pivot = random(start,end);
swap(&nums[pivot],&nums[end]);//把基准移到尾部

int left = start -1;//最左边原地划分一个子集
for(int i =start;i<end;i++)
{
if(nums[i]<nums[end])//如果小于基准就放入子集中
{
left++;
if(left!=i)
swap(&nums[i],&nums[left]);
}
}

left++;
swap(&nums[left],&nums[end]);//将最尾部的基准放在左子集的下一个位置

return left;//返回基准
}

void QuickSort_Recur(vector<int>& nums, int low, int high)
{
if(low<high)
{
int index = Partition(nums,low,high);//找到一个基准,并将所有小于基准的数放在基准左边。
QuickSort_Recur(nums,low,index-1);
QuickSort_Recur(nums,index+1,high);
}
}

Two-way scanning

var items = [4, 2, 6, 5, 3, 9];

In the previous example, the array becomes [4, 2, 3, 5, 6, 9] after one partition and the index returned is 4 (the last spot of the left pointer). After that, the left side of the overall array (items 0 through 3) is partitioned, as in the following figure.

In C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#define Max(a, b) ( (a > b) ? a : b )
#define Min(a, b) ( (a < b) ? a : b )
#define RANDOM_INIT() srand(time(NULL))
#define RANDOM(L, R) (L + rand() % ((R) - (L) + 1)) // gen a random integer in [L, R]
/**
* swap 2-element, orignal value
*/
template<typename T>
static inline void swap(T &x, T &y)
{
T _t(x);
x = y;
y = _t;
}

/**
* the quick-sort partition routine
*/
template<typename T>
static int partition_(T list[],int begin, int end) {
int pivot_idx = RANDOM(begin,end);
T pivot = list[pivot_idx];
swap(list[begin], list[pivot_idx]);

int i = begin + 1;//low
int j = end;//high

while(i <= j) {
while((i <= end) && (list[i] <= pivot))
i++;
while((j >= begin) && (list[j] > pivot))
j--;
if(i < j)
swap(list[i],list[j]);
}

swap(list[begin],list[j]);
return j; // final pivot position
}

/**
* quick sort an array of range [begin, end]
*/
template<typename T>
static void quicksort(T list[],int begin,int end) {
if( begin < end) {
int pivot_idx = partition_<T>(list, begin, end);
quicksort(list, begin, pivot_idx-1);
quicksort(list, pivot_idx+1, end);
}
}

Optimizations

  • BST : 快速排序是二叉查找树(二叉搜索树)的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中,而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数,但是顺序不同。对于排序算法的稳定性指标,原地分割版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的。
  • Heapsort : Worst:O(nlog n)的优势,堆排通常比快排慢,但是快排也有最差情况发生O(n^2)。如果事先知道可以用堆排,就直接使用堆排。堆排序也拥有重要的特点,仅使用固定额外的空间(堆排序是原地排序),而即使是最佳的快速排序变化版本也需要 O(log n)的空间。然而,堆排序需要有效率的随机存取才能变成可行。
  • Mergesort : Worst:O(nlog n)的优势。不像快排或堆排,归排是一个稳定排序,且可以轻易地被采用在linked list和存储在慢速访问媒体上(像是磁盘存储或网络连接存储的非常巨大数列)。尽管快排可以被重新改写使用在链串列上,但是它通常会因为无法随机存取而导致差的基准选择。归排的主要缺点,是在最佳情况下需要O(n)额外的空间。

Reference

  1. Quicksort From Wikipedia
  2. 对partition的优化
  3. 快速排序
Thanks for Support.