随机数快速排序python

以下是使用随机数快速排序的 Python 代码示例：

import random

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    left, mid, right = [], [], []
    for i in arr:
        if i < pivot:
            left.append(i)
        elif i == pivot:
            mid.append(i)
        else:
            right.append(i)
    return quick_sort(left) + mid + quick_sort(right)

# 示例
arr = [3, 1, 4, 2, 5]
print(quick_sort(arr))  # 输出 [1, 2, 3, 4, 5]

该实现中，我们通过 `random.choice(arr)` 随机选取一个元素作为枢轴（pivot），并将数组中小于、等于、大于枢轴的元素分别存储在左、中、右三个数组中。接着对左、右两个数组递归进行快速排序，最后将三个数组拼接起来即可。

相关问题

python三万个随机数用快速排序,堆排序,归并排序,选择排序,冒泡排序,插入排序,谁的用时最短

对于三万个随机数的排序，不同排序算法的用时可能会受到不同的因素影响，比如硬件配置、编程语言等。不过一般来说，快速排序和堆排序的平均时间复杂度比较低，而冒泡排序和选择排序的时间复杂度比较高，因此选择排序和冒泡排序的用时可能会比较长。以下是一个简单的Python代码示例，用于比较不同排序算法的用时：

import random
import time

# 生成随机数列表
nums = [random.randint(1, 100000) for _ in range(30000)]

# 快速排序
def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[len(nums) // 2]
    left_nums = [num for num in nums if num < pivot]
    mid_nums = [num for num in nums if num == pivot]
    right_nums = [num for num in nums if num > pivot]
    return quick_sort(left_nums) + mid_nums + quick_sort(right_nums)

start_time = time.time()
quick_sort(nums)
end_time = time.time()
print("快速排序用时：", end_time - start_time)

# 堆排序
def heapify(nums, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and nums[i] < nums[l]:
        largest = l
    if r < n and nums[largest] < nums[r]:
        largest = r
    if largest != i:
        nums[i], nums[largest] = nums[largest], nums[i]
        heapify(nums, n, largest)

def heap_sort(nums):
    n = len(nums)
    for i in range(n, -1, -1):
        heapify(nums, n, i)
    for i in range(n-1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        heapify(nums, i, 0)

start_time = time.time()
heap_sort(nums)
end_time = time.time()
print("堆排序用时：", end_time - start_time)

# 归并排序
def merge_sort(nums):
    if len(nums) > 1:
        mid = len(nums) // 2
        left_nums = nums[:mid]
        right_nums = nums[mid:]
        merge_sort(left_nums)
        merge_sort(right_nums)
        i = j = k = 0
        while i < len(left_nums) and j < len(right_nums):
            if left_nums[i] < right_nums[j]:
                nums[k] = left_nums[i]
                i += 1
            else:
                nums[k] = right_nums[j]
                j += 1
            k += 1
        while i < len(left_nums):
            nums[k] = left_nums[i]
            i += 1
            k += 1
        while j < len(right_nums):
            nums[k] = right_nums[j]
            j += 1
            k += 1

start_time = time.time()
merge_sort(nums)
end_time = time.time()
print("归并排序用时：", end_time - start_time)

# 选择排序
def selection_sort(nums):
    for i in range(len(nums)):
        min_idx = i
        for j in range(i+1, len(nums)):
            if nums[min_idx] > nums[j]:
                min_idx = j
        nums[i], nums[min_idx] = nums[min_idx], nums[i]

start_time = time.time()
selection_sort(nums)
end_time = time.time()
print("选择排序用时：", end_time - start_time)

# 冒泡排序
def bubble_sort(nums):
    for i in range(len(nums)-1):
        for j in range(len(nums)-i-1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]

start_time = time.time()
bubble_sort(nums)
end_time = time.time()
print("冒泡排序用时：", end_time - start_time)

# 插入排序
def insertion_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j+1] = nums[j]
            j -= 1
        nums[j+1] = key

start_time = time.time()
insertion_sort(nums)
end_time = time.time()
print("插入排序用时：", end_time - start_time)

需要注意的是，由于Python本身的执行效率不高，因此以上代码的运行时间并不具有参考意义，仅供参考。实际应用时，可以使用其他更高效的编程语言或工具来进行测试。

python三万个随机数用快速排序，堆排序，归并排序，选择排序，冒泡排序，插入排序，谁的用时最短

这个问题需要具体分析，因为不同排序算法的时间复杂度不同，而且在实际应用中，不同的数据集大小和数据分布也会影响排序算法的效率。一般来说，快速排序、堆排序、归并排序的时间复杂度都是 O(nlogn)，而选择排序、冒泡排序、插入排序的时间复杂度都是 O(n^2)。在数据量较小的时候，选择排序、冒泡排序、插入排序可能比较快，但是数据量增加后，它们的效率会明显下降。因此，对于这个问题，最好的做法是实际编写程序进行测试，比较各种排序算法的用时。