用list 实现折半插入排序

折半插入排序是一种插入排序的改进，它通过在已经排好序的子序列中二分查找插入位置，来减少比较和移动数据的次数。以下是用 Python 中的 list 实现折半插入排序的代码：

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

在这个实现中，我们首先遍历整个数组，对于每个元素，我们使用二分查找来找到它在已经排好序的子序列中的插入位置。然后，我们将这个元素插入到该位置，并将该位置之后的元素向后移动一个位置。

注意，这个实现是在原地进行排序的，因此它不需要额外的空间来存储排序后的结果。

相关问题

C语言使用顺序表实现折半插入排序法，并在主函数中输入元素，再输出排序结果

在C语言中，顺序表通常使用数组结构来实现。对于折半插入排序（也称为二分查找插入），我们首先需要创建一个动态大小的数组来存储数据。以下是简单的步骤：

1. 定义一个结构体表示顺序表节点，包含数据域和指向下一个节点的指针。

typedef struct Node {
    int data;
    struct Node* next;
} ListNode;

2. 创建顺序表结构体并初始化头指针。

ListNode* list = NULL;

3. 主函数中，用户输入元素并添加到列表中，这里假设`getInput()`函数用于获取用户输入。

void insertHalfSort(int input) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = input;

    if (!list || newNode->data <= list->data) {
        newNode->next = list;
        list = newNode;
    } else {
        ListNode* temp = list;
        while (temp->next && temp->next->data < newNode->data) {
            temp = temp->next;
        }
        newNode->next = temp->next;
        temp->next = newNode;
    }
}

4. 插入所有元素后，进行折半插入排序。由于数组排序效率更高，我们可以直接遍历整个数组进行插入操作。

void sortList() {
    for (int i = 1; i < listSize; ++i) {
        ListNode* current = list;
        ListNode* target = list + i;
        
        // 如果目标位置比当前元素大，说明插入位置在其右侧
        while (current != NULL && target->data > current->data) {
            ListNode* temp = current;
            current = current->next;
        }

        // 移动元素
        if (current != NULL) {
            target->next = current->next;
        } else {
            list = target;
        }
        temp->next = target;
    }
}

// 假设listSize是一个全局变量，表示列表长度
void main() {
    int n;
    printf("Enter the number of elements: ");
    scanf("%d", &n);

    listSize = n;
    for (int i = 0; i < n; ++i) {
        insertHalfSort(getInput());
    }

    // 打印排序后的列表
    printList(list);
}

5. `printList()`函数用于遍历并打印顺序表，这里省略了，可以自定义实现。

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

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

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

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

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

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

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()

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