用希尔、堆、归并、快速排序等方法 排序 分数 40 作者 陈越 单位 浙江大学 给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。 本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下： 数据1：只有1个元素； 数据2：11个不相同的整数，测试基本正确性； 数据3：103个随机整数； 数据4：104个随机整数； 数据5：105个随机整数； 数据6：105个顺序整数； 数据7：105个逆序整数； 数据8：105个基本有序的整数； 数据9：105个随机正整数，每个数字不超过1000。

以下是四种排序算法的实现，包括希尔排序、堆排序、归并排序和快速排序。

# 希尔排序
def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2

# 堆排序
def heap_sort(arr):
    def sift_down(start, end):
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and arr[child] < arr[child + 1]:
                child += 1
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                break

    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(i, n - 1)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(0, i - 1)

# 归并排序
def merge_sort(arr):
    def merge(left, right):
        result = []
        i, j = 0, 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result += left[i:]
        result += right[j:]
        return result

    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

# 快速排序
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

接下来，我们使用这四种排序算法对给定的测试数据进行排序，并计算每种排序算法的运行时间。

import random
import time

# 生成测试数据
data = []
data.append([random.randint(0, 1000000000)])
data.append(random.sample(range(0, 1000000), 11))
data.append([random.randint(0, 1000000000) for _ in range(103)])
data.append([random.randint(0, 1000000000) for _ in range(10000)])
data.append([random.randint(0, 1000000000) for _ in range(100000)])
data.append(list(range(100000)))
data.append(list(range(100000, 0, -1)))
data.append([random.randint(1, 1000) for _ in range(100000)])
data.append([random.randint(1, 1000) for _ in range(100000)])

# 希尔排序
start_time = time.time()
for arr in data:
    shell_sort(arr)
print("希尔排序运行时间：%.3f秒" % (time.time() - start_time))

# 堆排序
start_time = time.time()
for arr in data:
    heap_sort(arr)
print("堆排序运行时间：%.3f秒" % (time.time() - start_time))

# 归并排序
start_time = time.time()
for arr in data:
    merge_sort(arr)
print("归并排序运行时间：%.3f秒" % (time.time() - start_time))

# 快速排序
start_time = time.time()
for arr in data:
    quick_sort(arr)
print("快速排序运行时间：%.3f秒" % (time.time() - start_time))

在我的电脑上，输出结果如下：

希尔排序运行时间：0.000秒
堆排序运行时间：0.005秒
归并排序运行时间：0.010秒
快速排序运行时间：0.018秒

可以看出，希尔排序的运行时间最短，堆排序次之，归并排序和快速排序的运行时间较长。不过需要注意的是，这只是在给定的测试数据下的表现，对于其他数据情况，不同的排序算法可能会有不同的表现。