用python编写希尔排序

希尔排序（Shell Sort），也称为缩小增量排序，是一种基于插入排序的高效算法改进版本。它的基本思想是先将待排序数组按照一定增量分组，对每组进行插入排序，然后逐渐减小增量直到为1，最终得到完全有序的序列。

以下是用Python实现希尔排序的一个简单示例：

def shell_sort(arr):
    # 所有元素都是初始增量的一部分
    gap = len(arr) // 2

    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i

            # 使用gap逐步缩小增量，进行插入排序
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap

            # 将temp放在正确的位置
            arr[j] = temp

        # 更新增量，进入下一轮循环
        gap //= 2

    return arr

# 示例
arr = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
sorted_arr = shell_sort(arr)
print("排序后的数组:", sorted_arr)

相关问题

用python写一个希尔排序

以下是使用Python编写的希尔排序代码：

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
    return arr

使用示例：

arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = shell_sort(arr)
print(sorted_arr)  # [11, 12, 22, 25, 34, 64, 90]

该算法的时间复杂度为O(nlogn)，并且具有较好的性能。

（1）编写各种排序算法对测试数据进行排序。基本排序算法共七种：直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序和归并排序。要求至少实现4种排序算法。 （2）在测试数据不少于10000个的情况下比较不同排序算法的时间性能（实际运行时间）。

好的，我可以帮你解决这个问题。

以下是四种排序算法的Python实现代码，包括直接插入排序、冒泡排序、快速排序和归并排序：

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

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

# 快速排序
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = []
    right = []
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quick_sort(left) + [pivot] + quick_sort(right)

# 归并排序
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result += right
    return result

接下来是一个用于比较各种排序算法时间性能的Python代码：

import random
import time

# 生成随机测试数据
data = [random.randint(1, 10000) for _ in range(10000)]

# 测试直接插入排序的时间性能
start = time.time()
insertion_sort(data)
end = time.time()
print("Insertion sort time: %.6f seconds." % (end - start))

# 测试冒泡排序的时间性能
start = time.time()
bubble_sort(data)
end = time.time()
print("Bubble sort time: %.6f seconds." % (end - start))

# 测试快速排序的时间性能
start = time.time()
quick_sort(data)
end = time.time()
print("Quick sort time: %.6f seconds." % (end - start))

# 测试归并排序的时间性能
start = time.time()
merge_sort(data)
end = time.time()
print("Merge sort time: %.6f seconds." % (end - start))

运行结果将会输出每种排序算法的运行时间。你可以通过比较运行时间来了解它们之间的不同。