编写快速排序算法程序，要求至少实现两种不同的支点元选取方法

快速排序是一种高效的排序算法，它采用分治策略，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，直到整个序列有序。关于支点元选取方法，常见的有两种：

1. **随机选择** (Random Pivot)：这是最常见的方法之一。每次从待排序数组中随机选择一个元素作为支点元。这样做可以避免最坏情况的发生，即输入数组已经完全有序或逆序，保证了平均时间复杂度接近 O(n log n)。

   import random
   def quicksort(arr):
       if len(arr) <= 1:
           return arr
       pivot_index = random.randint(0, len(arr) - 1)
       pivot = arr[pivot_index]
       arr.remove(pivot)
       less = [x for x in arr if x < pivot]
       equal = [x for x in arr if x == pivot]
       greater = [x for x in arr if x > pivot]
       return quicksort(less) + equal + quicksort(greater)

2. **三数取中** (Median of Three)：这种方法会选择待排序区间的首、尾和中间三个元素的中位数作为支点。这能减少极端情况下的性能波动，因为中位数通常不会位于最大值或最小值的位置。

   def median_of_three(arr, low, high):
       mid = (low + high) // 2
       if arr[low] > arr[mid]:
           arr[low], arr[mid] = arr[mid], arr[low]  # 交换首部和中间
       if arr[mid] > arr[high]:
           arr[mid], arr[high] = arr[high], arr[mid]  # 如果中间大，则换到尾部
       if arr[low] > arr[mid]:  # 首部大于中间，再次交换
           arr[low], arr[mid] = arr[mid], arr[low]
       pivot = arr[mid]  # 返回中位数作为支点
       return pivot

   def quicksort_with_median(arr):
       if len(arr) <= 1:
           return arr
       pivot = median_of_three(arr, 0, len(arr) - 1)
       # ... 其他步骤与随机选择支点版本相似