数据结构二分法插入排序

二分法插入排序是一种优化的插入排序算法，它利用了二分查找的思想来寻找插入位置，从而减少了比较次数，提高了排序效率。

具体实现步骤如下：

1. 将第一个元素看作有序序列，从第二个元素开始向有序序列插入。

2. 对于第i个元素，使用二分查找在有序序列中找到插入位置j，使得前j个元素仍然有序，但是加上第i个元素后，前j+1个元素也有序。

3. 将第i个元素插入到位置j+1，然后将j+1到i-1位置的元素后移一位，腾出位置给第i个元素。

4. 重复以上步骤，直到所有元素都插入到有序序列中。

二分法插入排序的时间复杂度仍然是O(n^2)，但是因为比较次数减少了，所以实际运行效率要比普通的插入排序要高一些。

相关问题

数据结构二分法插入排序代码

下面是使用二分法实现的插入排序代码：

void binaryInsertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        // 二分查找待插入位置
        int left = 0, right = i - 1;
        int insertIndex = i;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[i] < arr[mid]) {
                right = mid - 1;
                insertIndex = mid;
            } else {
                left = mid + 1;
            }
        }
        // 插入元素
        int temp = arr[i];
        for (int j = i; j > insertIndex; j--) {
            arr[j] = arr[j - 1];
        }
        arr[insertIndex] = temp;
    }
}

该算法的时间复杂度为 $O(n^2)$，但使用二分法查找待插入位置可以减少比较的次数，因此实际效率要比普通的插入排序高一些。

选取一个合适的数据结构存储一批数据，能对数据进行插入、删除和显示操作，还能分别用二分法插入排序、直接选择排序、直接插入排序算法对这些数据进行排序，用C语言表示

一个合适的数据结构是链表，可以通过指针实现节点间的链接，可以进行插入和删除操作。下面是一个简单的链表结构体的定义：

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

其中，`data` 存储节点的数据，`next` 存储下一个节点的地址。

插入操作可以通过在指定位置处插入节点实现，例如：

void insert(Node* head, int position, int data) {
    Node* p = head;
    for (int i = 0; i < position && p->next; ++i) {
        p = p->next;
    }
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = p->next;
    p->next = node;
}

删除操作可以通过找到要删除的节点，然后修改前一个节点的 `next` 指针实现，例如：

void remove(Node* head, int position) {
    Node* p = head;
    for (int i = 0; i < position && p->next; ++i) {
        p = p->next;
    }
    Node* tmp = p->next;
    p->next = tmp->next;
    free(tmp);
}

显示操作可以通过遍历链表，依次输出每个节点的 `data` 值实现，例如：

void display(Node* head) {
    Node* p = head->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

二分法插入排序可以通过遍历链表，然后将每个节点插入到已排好序的节点中的合适位置实现，例如：

void binary_insert_sort(Node* head) {
    Node* p = head->next;
    head->next = NULL;
    while (p) {
        Node* q = head;
        Node* pre = NULL;
        while (q && q->data < p->data) {
            pre = q;
            q = q->next;
        }
        Node* tmp = p->next;
        if (pre) {
            p->next = pre->next;
            pre->next = p;
        } else {
            p->next = head->next;
            head->next = p;
        }
        p = tmp;
    }
}

直接选择排序可以通过遍历链表，找到未排序部分的最小值，然后将其插入到已排好序的节点的尾部实现，例如：

void selection_sort(Node* head) {
    Node* p = head->next;
    head->next = NULL;
    while (p) {
        Node* min = p;
        Node* q = p->next;
        while (q) {
            if (q->data < min->data) {
                min = q;
            }
            q = q->next;
        }
        Node* tmp = min->next;
        min->next = NULL;
        if (head->next) {
            Node* last = head->next;
            while (last->next) {
                last = last->next;
            }
            last->next = min;
        } else {
            head->next = min;
        }
        p = tmp;
    }
}

直接插入排序可以通过将节点依次插入到已排好序的节点中的合适位置实现，例如：

void insertion_sort(Node* head) {
    Node* p = head->next;
    head->next = NULL;
    while (p) {
        Node* q = head;
        Node* pre = NULL;
        while (q && q->data < p->data) {
            pre = q;
            q = q->next;
        }
        Node* tmp = p->next;
        if (pre) {
            p->next = pre->next;
            pre->next = p;
        } else {
            p->next = head->next;
            head->next = p;
        }
        p = tmp;
    }
}

注意，这里的排序算法都是针对单向链表的，对于双向链表或其他数据结构的排序实现可能会有所不同。