查看“︁拉斯维加斯算法”︁的源代码

{{unref|time=2015-07-16T07:40:44+00:00}}

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

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

== 特性 ==

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

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

=== 伪代码示例 ===
<syntaxhighlight start="1">
function randomizedQuickSort(A, low, high)
    if low < high then
        pivotIndex = randomizedPartition(A, low, high)
        randomizedQuickSort(A, low, pivotIndex - 1)
        randomizedQuickSort(A, pivotIndex + 1, high)

function randomizedPartition(A, low, high)
    pivotIndex = random(low, high)  // 在 [low, high] 范围内随机选择一个枢轴
    swap(A[pivotIndex], A[high])    // 将随机选择的枢轴与最后一个元素交换
    return partition(A, low, high)

function partition(A, low, high)
    pivot = A[high]
    i = low - 1
    for j = low to high - 1 do
        if A[j] <= pivot then
            i = i + 1
            swap(A[i], A[j])
    swap(A[i + 1], A[high])
    return i + 1

function swap(a, b)
    temp = a
    a = b
    b = temp

function random(low, high)
    // 返回 [low, high] 范围内的一个随机整数
    return low + floor((high - low + 1) * rand())

</syntaxhighlight>

==== 解释 ====

# ''randomizedQuickSort''：这是主函数，用于对数组 <code>A</code> 的子数组 <code>[low, high]</code> 进行排序。
# ''randomizedPartition''：这是随机化的分区函数，它随机选择一个枢轴，并将其与当前子数组的最后一个元素交换，然后调用 <code>partition</code> 函数进行分区。
# ''partition''：这是标准的分区函数，使用最后一个元素作为枢轴，将小于等于枢轴的元素移动到枢轴的左边，大于枢轴的元素移动到右边，最后返回枢轴的位置。
# ''swap''：这是一个简单的交换函数，用于交换数组中的两个元素。
# ''random''：这是一个生成 <code>[low, high]</code> 范围内随机整数的函数。

=== C++ 示例 ===
<syntaxhighlight lang="c++" line="1">
#include <iostream>
#include <cstdlib>
#include <ctime>

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 < high; j++) {
        if (array[j] <= pivot) {
            i++;
            swap(array[i], array[j]);
        }
    }
    swap(array[i + 1], array[high]);
    return i + 1;
}

int randomizedPartition(int array[], int low, int high) {
    int pivotIndex = low + rand() % (high - low + 1); // 在 [low, high] 范围内随机选择一个枢轴
    swap(array[pivotIndex], array[high]); // 将随机选择的枢轴与最后一个元素交换
    return partition(array, low, high);
}

void randomizedQuickSort(int array[], int low, int high) {
    if (low < high) {
        int pivotIndex = randomizedPartition(array, low, high);
        randomizedQuickSort(array, low, pivotIndex - 1);
        randomizedQuickSort(array, pivotIndex + 1, high);
    }
}

int main() {
    srand(time(0)); // 设置随机数种子

    int array[] = {3, 6, 8, 10, 1, 2, 1};
    int n = sizeof(array) / sizeof(array[0]);

    std::cout << "Original array: ";
    for (int i = 0; i < n; i++) {
        std::cout << array[i] << " ";
    }
    std::cout << std::endl;

    randomizedQuickSort(array, 0, n - 1);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << array[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

</syntaxhighlight>

== 参考资料 ==
{{Reflist}}

[[Category:随机化算法]]