写出下面问题的伪代码 对于给定的一组元素a1,a2，，an(两两不等),随机快速排序(random Quick sort)的原理是随机选择一 个元素ai，之后元素按小于ai与大于ai，分别列于a的左边与右边;并对左右了个子数组递归快速排序 请写出随机快速排序的主要代码

### 回答1：
以下是随机快速排序的伪代码：

procedure quick_sort(list)
  if length(list) <= 1
    return list
  pivot_index = random_integer(0, length(list) - 1)
  pivot = list[pivot_index]
  left_list = []
  right_list = []
  for i = 0 to length(list) - 1
    if i != pivot_index
      if list[i] < pivot
        left_list.append(list[i])
      else
        right_list.append(list[i])
  return quick_sort(left_list) + [pivot] + quick_sort(right_list)

该算法的主要思路是：

1. 如果待排序的列表长度小于等于 1，则直接返回该列表。
2. 从列表中随机选取一个元素作为枢纽元。
3. 初始化两个空列表 left_list 和 right_list，用于存储比枢纽元小的元素和比枢纽元大的元素。
4. 遍历列表中的所有元素，如果该元素不是枢纽元，则将其放入 left_list 或 right_list 中。
5. 对 left_list 和 right_list 分别递归调用 quick_sort 进行排序，并将排序后的 left_list、枢纽元和排序后的 right_list 拼接在一起，作为函数的返回值。

在上述伪代码中，random_integer 函数用于生成一个在给定范围内的随机整数。

### 回答2：
伪代码如下：

function randomQuickSort(arr, low, high) {
  if (low < high) {
    pivotIndex = partition(arr, low, high);
    randomQuickSort(arr, low, pivotIndex - 1);
    randomQuickSort(arr, pivotIndex + 1, high);
  }
}

function partition(arr, low, high) {
  // 选择随机的主元素
  randomPivotIndex = random(low, high);
  swap(arr[randomPivotIndex], arr[high]);

  pivot = arr[high];
  i = low - 1;

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

  swap(arr[i + 1], arr[high]);
  return i + 1;
}

function swap(a, b) {
  temp = a;
  a = b;
  b = temp;
}

解释：首先，randomQuickSort是主函数，用来递归地快速排序数组arr。它接受三个参数：arr表示待排序的数组，low表示数组的最小下标，high表示数组的最大下标。

在randomQuickSort函数中，首先判断low是否小于high，如果是，则调用partition函数来选择主元素，并将数组分为两部分。之后，再分别对主元素的左边和右边的子数组进行递归调用randomQuickSort函数，以实现对整个数组的快速排序。

在partition函数中，首先从low和high之间随机选择一个主元素，并将其与数组的最后一个元素进行交换。然后，以这个主元素为基准，将数组进行划分，使左边的元素都小于主元素，右边的元素都大于主元素。最后，返回主元素的位置。

最后，swap函数用于交换两个元素的值。

### 回答3：
伪代码如下：

function randomQuickSort(array):
    if length(array) <= 1:
        return array
    pivot_index = random(0, length(array)-1)
    pivot = array[pivot_index]
    less = []
    greater = []
    for i = 0 to length(array)-1:
        if i != pivot_index:
            if array[i] < pivot:
                append array[i] to less
            else:
                append array[i] to greater
    sorted_less = randomQuickSort(less)
    sorted_greater = randomQuickSort(greater)
    return concatenate(sorted_less, [pivot], sorted_greater)

说明：
1. 首先，判断给定数组的长度，如果长度小于等于1，则直接返回数组本身，因为长度为1的数组可以认为是已经排序好的数组。
2. 随机选择一个元素作为基准值（pivot），通过`random(0, length(array)-1)`生成一个随机索引，然后取出该索引对应的元素。
3. 创建两个空数组`less`和`greater`，用来存储小于基准值和大于基准值的元素。
4. 遍历数组中的元素，跳过基准值所在索引，如果元素小于基准值，则将其添加到`less`数组中，否则添加到`greater`数组中。
5. 递归调用`randomQuickSort`函数对`less`和`greater`数组进行排序，得到排序好的`sorted_less`和`sorted_greater`数组。
6. 最后将`sorted_less`、基准值`pivot`和`sorted_greater`按顺序连接起来，得到排序好的数组，并将其返回。