三路快速排序算法的 C++ 和 Python 实现 & 原理
三路快排即是一种对带有大量重复键值的数组进行快速排序的算法, 避免了重复操作相同元素
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);
}