数据结构与算法之随机快排算法

随机快排是一种高效的排序算法，其主要原理如下：

1. 选取随机基准元素：在待排序的数组中随机选择一个元素作为基准值（pivot）。

2. 分割数组：将数组中小于基准值的元素放在基准值左侧，大于基准值的元素放在右侧。

3. 递归排序：对左右两个子数组进行递归排序，直到子数组长度为1或0。

4. 合并数组：将排好序的左右两个子数组合并成一个有序数组。

具体实现时，可以使用双指针法或递归实现。其中双指针法需要使用两个指针分别从数组的首尾开始扫描，直到找到需要交换的两个元素为止，然后进行交换。递归实现则是将数组划分成子数组，然后对子数组进行递归排序。

随机快排的时间复杂度为 O(nlogn)，空间复杂度为 O(nlogn)。同时，由于随机选择基准元素，能够避免最坏情况（即每次选取的基准元素都是数组中的最小值或最大值），因此其平均时间复杂度为 O(nlogn)。

一、C 实现 随机快排算法 及代码详解

随机快排算法是快速排序的一种优化，主要针对某些特定情况下快排时间复杂度退化的问题。该算法的核心思想是在每次分区时，随机选择一个基准值，从而避免了最坏情况的出现。

以下是 C 语言实现随机快排算法的代码及详解：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 10 // 待排序数组的最大长度

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

int partition(int arr[], int left, int right)
{
    srand(time(NULL)); // 随机种子
    int pivotIndex = left + rand() % (right - left + 1); // 随机选择基准值
    int pivotValue = arr[pivotIndex];
    swap(&arr[pivotIndex], &arr[right]); // 将基准值放到最后
    int storeIndex = left;
    for (int i = left; i < right; i++) { // 分区
        if (arr[i] < pivotValue) {
            swap(&arr[storeIndex], &arr[i]);
            storeIndex++;
        }
    }
    swap(&arr[storeIndex], &arr[right]); // 将基准值放回正确位置
    return storeIndex;
}

void quickSort(int arr[], int left, int right)
{
    if (left < right) {
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
}

int main()
{
    int arr[MAX_SIZE];
    printf("Enter %d integers: ", MAX_SIZE);
    for (int i = 0; i < MAX_SIZE; i++) {
        scanf("%d", &arr[i]);
    }
    quickSort(arr, 0, MAX_SIZE - 1);
    printf("Sorted array: ");
    for (int i = 0; i < MAX_SIZE; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

具体实现步骤如下：

1. 定义 swap() 函数，用于交换两个元素的值。

2. 定义 partition() 函数，用于分区。该函数随机选择一个基准值，然后将其放到最后，再从前往后遍历数组，将小于基准值的元素移到左边，大于基准值的元素留在右边。

3. 定义 quickSort() 函数，用于递归调用 partition() 函数进行分区，直到左右两边都排好序。

4. 在 main() 函数中，从标准输入读取待排序数组，然后调用 quickSort() 函数进行排序，最后输出排序结果。

在使用随机快排算法时，需要注意以下几点：

1. 每次分区都要随机选择基准值，在递归过程中不要改变基准值的位置。

2. 随机种子可以使用 time 函数获取当前时间作为种子。同时，为了避免种子相同，应该在每次分区前重新生成随机种子。

3. 当待排序数组长度较小时，快排算法可能不如其他排序算法效率高，因此应该在选择排序算法时考虑待排序数组的长度。

二、C++ 实现 随机快排算法 及代码详解

随机快排算法是快排算法的一种优化，其核心思想是将数组中的元素随机打乱后再进行快排，这样可以避免出现最坏情况，减少了运行时间的波动。

下面是 C++ 实现随机快排算法的代码及其详解。

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

int randomPartition(int arr[], int low, int high) {
    srand(time(NULL)); // 设置随机种子
    int random = low + rand() % (high - low); // 生成随机值
    swap(arr[random], arr[high]); // 将随机值与末尾元素交换
    return partition(arr, low, high);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = randomPartition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    int arr[] = {5, 2, 9, 3, 7, 6, 1, 8, 4};
    int n = sizeof(arr) / sizeof(int);

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

函数 swap：交换两个元素。

函数 partition：对数组中 low 到 high 之间的元素进行划分，以最后一个元素为基准值（pivot），将小于基准值的元素放在左边，大于等于基准值的元素放在右边，返回基准值的索引。

函数 randomPartition：随机生成一个索引，将该索引对应的元素与末尾元素交换，然后调用 partition 函数进行划分。

函数 quickSort：快排的主要递归函数，对数组中 low 到 high 之间的元素进行快排，先调用 randomPartition 函数进行划分，然后递归对划分后的左右两部分分别进行排序。

在 main 函数中，首先定义一个数组 arr，然后调用 quickSort 函数进行排序，最后输出排序结果。

总体来说，随机快排算法与传统快排算法的区别仅在于 randomPartition 函数的实现方式，它将参与排序的元素随机打乱，避免了最坏情况的发生。

三、Java 实现 随机快排算法 及代码详解

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，是一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n 个项目要 O(n log n) 次比较。在最坏状况下则需要 O(n^2) 次比较，但这种状况并不常见。事实上，快速排序 O(n log n) 通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分架构上很有效率地达成。

快速排序使用分治法来把一个序列（list）分为两个子序列（sub-lists）。具体算法描述如下：

1.从数列中挑出一个元素，称为“基准”（pivot）；

2.重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆放在基准的后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3.递归地（recursive）把小于基准值元素的子序列和大于基准值元素的子序列排序。

具体实现代码如下：

public class QuickSort {
    
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left + 1;
        int j = right;
        while (true) {
            while (i <= j && arr[i] <= pivot) {
                i++;
            }
            while (i <= j && arr[j] >= pivot) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
        }
        swap(arr, left, j);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

代码解析：

1. 方法 quickSort 是快速排序算法的入口，接收需要排序的数组和数组的左右索引。

2. 方法 partition 是分区操作，用于将数组分为左右两个部分，左部分小于基准值，右部分大于基准值。

3. 方法 swap 是用于交换数组中两个数字的方法。

4. 在 partition 方法中，定义 pivot 为基准值，i 和 j 分别为左右索引。首先从左向右找到第一个大于基准值的数字，从右向左找到第一个小于基准值的数字，交换两个数字的位置。不断重复该过程，直到 i 和 j 重合，将基准值和 j 交换位置，并返回 j 的索引。

5. 在 quickSort 方法中，递归调用 partition 方法，分别对左右两部分进行排序。

快速排序的时间复杂度为 O(n log n)，空间复杂度为 O(log n)。由于快速排序也是一种分治算法，因此适合处理大规模数据。