随机十个数,分别使用选择排序、希尔排序、快速排序、归并排序和基数排序使数据集有序。写代码
时间: 2023-12-19 22:05:52 浏览: 79
随机产生若干个数,并插入排序
好的,以下是 Python 代码实现:
```python
import random
# 生成随机数
nums = [random.randint(0, 100) for _ in range(10)]
print("原始数据:", nums)
# 选择排序
def selection_sort(nums):
for i in range(len(nums)):
min_index = i
for j in range(i+1, len(nums)):
if nums[j] < nums[min_index]:
min_index = j
nums[i], nums[min_index] = nums[min_index], nums[i]
return nums
sorted_nums = selection_sort(nums)
print("选择排序结果:", sorted_nums)
# 希尔排序
def shell_sort(nums):
gap = len(nums) // 2
while gap > 0:
for i in range(gap, len(nums)):
j = i
while j >= gap and nums[j-gap] > nums[j]:
nums[j], nums[j-gap] = nums[j-gap], nums[j]
j -= gap
gap //= 2
return nums
sorted_nums = shell_sort(nums)
print("希尔排序结果:", sorted_nums)
# 快速排序
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = nums[len(nums)//2]
left, right, mid = [], [], []
for num in nums:
if num < pivot:
left.append(num)
elif num > pivot:
right.append(num)
else:
mid.append(num)
return quick_sort(left) + mid + quick_sort(right)
sorted_nums = quick_sort(nums)
print("快速排序结果:", sorted_nums)
# 归并排序
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
def merge(left, right):
i, j = 0, 0
merged = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged += left[i:]
merged += right[j:]
return merged
sorted_nums = merge_sort(nums)
print("归并排序结果:", sorted_nums)
# 基数排序
def radix_sort(nums):
max_num = max(nums)
digit = 1
while max_num // digit > 0:
nums = counting_sort(nums, digit)
digit *= 10
return nums
def counting_sort(nums, digit):
count = [0] * 10
for num in nums:
count[(num // digit) % 10] += 1
for i in range(1, 10):
count[i] += count[i-1]
output = [0] * len(nums)
for i in range(len(nums)-1, -1, -1):
index = (nums[i] // digit) % 10
output[count[index]-1] = nums[i]
count[index] -= 1
return output
sorted_nums = radix_sort(nums)
print("基数排序结果:", sorted_nums)
```
注意,基数排序中的实现方式是 LSD(最低位优先)的基数排序。
阅读全文