插入排序，折半插入排序，希尔排序性能比较折线图

插入排序、折半插入排序和希尔排序是三种常见的排序算法，它们在不同数据集和不同情况下的性能表现各不相同。为了更好地理解它们之间的性能差异，我们可以绘制一张性能比较折线图。

### 插入排序
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在数据量较小时表现较好，但在数据量较大时效率较低。

### 折半插入排序
折半插入排序是插入排序的一种优化版本。它利用二分查找来确定插入位置，从而减少比较次数。虽然折半插入排序在比较次数上有所减少，但移动元素的次数并没有减少，因此在大数据集上的表现仍然不如更高效的排序算法。

### 希尔排序
希尔排序是一种改进的插入排序算法。它通过比较相隔一定间隔的元素来进行排序，随着间隔的逐渐减少，算法变得更加高效。希尔排序在大多数情况下都比简单的插入排序和折半插入排序更高效，特别是在处理大规模数据时。

### 性能比较折线图
为了绘制一张性能比较折线图，我们可以使用以下步骤：

1. **准备数据**：生成不同规模的数据集（例如，1000、2000、5000、10000、20000个元素）。
2. **运行排序算法**：对每个数据集运行插入排序、折半插入排序和希尔排序，并记录每种算法所需的时间。
3. **绘制折线图**：使用Python的matplotlib库绘制折线图，横轴表示数据规模，纵轴表示时间。

以下是一个简单的Python代码示例，演示如何绘制性能比较折线图：

import matplotlib.pyplot as plt
import time
import random

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >=0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        left = 0
        right = i-1
        while left <= right:
            mid = (left + right) // 2
            if key < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        for j in range(i, left, -1):
            arr[j] = arr[j-1]
        arr[left] = key

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

data_sizes = [1000, 2000, 5000, 10000, 20000]
insertion_times = []
binary_insertion_times = []
shell_times = []

for size in data_sizes:
    arr = list(range(size))
    random.shuffle(arr)

    # Insertion Sort
    start = time.time()
    insertion_sort(arr.copy())
    end = time.time()
    insertion_times.append(end - start)

    # Binary Insertion Sort
    start = time.time()
    binary_insertion_sort(arr.copy())
    end = time.time()
    binary_insertion_times.append(end - start)

    # Shell Sort
    start = time.time()
    shell_sort(arr.copy())
    end = time.time()
    shell_times.append(end - start)

plt.plot(data_sizes, insertion_times, label='Insertion Sort')
plt.plot(data_sizes, binary_insertion_times, label='Binary Insertion Sort')
plt.plot(data_sizes, shell_times, label='Shell Sort')
plt.xlabel('Data Size')
plt.ylabel('Time (seconds)')
plt.legend()
plt.show()

通过上述代码，我们可以生成一张性能比较折线图，直观地展示插入排序、折半插入排序和希尔排序在不同数据规模下的性能表现。