三路快速排序算法的 C++ 实现 & 原理

三路快排即是一种对带有大量重复键值的数组进行快速排序的算法, 避免了重复操作相同元素

void Quicksort(int l, int r) 
{
    if (l >= r) return;

    int key = arr[rand() % (r - l + 1) + l];
    int i = l, j = l, k = r;

    while (i <= k) 
	{
        if (arr[i] < key) 
		{
            swap(arr[i++], arr[j++]);
        } 
		else if (arr[i] > key) 
		{
            swap(arr[i], arr[k--]);
        } 
		else 
		{
            ++i;
        }
    }

    Quicksort(l, j - 1);
    Quicksort(k + 1, r);  
}