在电脑运算中，拉斯维加斯算法（Las Vegas algorithm）是一种永远给出正确解的随机化算法；也就是说，它总是给出正确结果，或是返回失败。 换言之，拉斯维加斯算法不赌结果的正确性，而是赌运算所用资源。一个简单的例子是随机快速排序，他的中心点虽然是随机选择的，但排序结果永远一致。

与拉斯维加斯算法相对的是蒙地卡罗算法。蒙地卡罗算法在一定的概率下可能返回错误的结果，但其运行时间是确定的或有上界的。

特性

• 随机性：算法在运行过程中使用随机数来影响其行为。
• 正确性保证：拉斯维加斯算法总是返回正确的结果。也就是说，它不会在计算结果上出错。
• 运行时间不确定：虽然结果总是正确的，但算法的运行时间是随机的，可能会有很大的波动。

使用拉斯维加斯算法的快速排序代码示例
一个经典的拉斯维加斯算法例子是快速排序的随机化版本。在这个版本中，算法随机选择一个枢轴（pivot）元素进行分区。虽然运行时间的期望值是 O(n \log n)，但实际运行时间会因为随机选择而有所不同。然而，无论运行时间如何，最终排序结果总是正确的。

伪代码示例
function randomizedQuickSort(A, low, high)
if low

解释

randomizedQuickSort：这是主函数，用于对数组 A 的子数组 [low, high] 进行排序。

randomizedPartition：这是随机化的分区函数，它随机选择一个枢轴，并将其与当前子数组的最后一个元素交换，然后调用 partition 函数进行分区。

partition：这是标准的分区函数，使用最后一个元素作为枢轴，将小于等于枢轴的元素移动到枢轴的左边，大于枢轴的元素移动到右边，最后返回枢轴的位置。

swap：这是一个简单的交换函数，用于交换数组中的两个元素。

random：这是一个生成 [low, high] 范围内随机整数的函数。

C++ 示例
#include
#include
#include

void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}

int partition(int array[], int low, int high) {
int pivot = array[high];
int i = low - 1;
for (int j = low; j

参考资料