用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语言折半插入排序法双链表

折半插入排序是一种高效的排序算法，而双向链表则是一种支持双向遍历的数据结构。下面是使用折半插入排序法对双链表进行排序的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义双向链表节点
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

// 定义双向链表
typedef struct List {
    Node* head;
    Node* tail;
} List;

// 初始化双向链表
List* initList() {
    List* list = (List*)malloc(sizeof(List));
    list->head = NULL;
    list->tail = NULL;
    return list;
}

// 创建新节点
Node* createNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 在链表尾部插入新节点
void insertNode(List* list, Node* node) {
    if (list->head == NULL) {
        list->head = node;
        list->tail = node;
    } else {
        node->prev = list->tail;
        list->tail->next = node;
        list->tail = node;
    }
}

// 折半插入排序
void insertionSort(List* list) {
    Node* current = list->head->next;
    while (current != NULL) {
        Node *p = list->head, *q = current->prev;
        while (p != current && p->data <= current->data) {
            p = p->next;
        }
        while (q != p) {
            q->next->data = q->data;
            q = q->prev;
        }
        p->data = current->data;
        current = current->next;
    }
}

// 打印链表
void printList(List* list) {
    Node* current = list->head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    List* list = initList();
    insertNode(list, createNode(5));
    insertNode(list, createNode(3));
    insertNode(list, createNode(8));
    insertNode(list, createNode(1));
    insertNode(list, createNode(2));
    printf("Original list: ");
    printList(list);
    insertionSort(list);
    printf("Sorted list: ");
    printList(list);
    return 0;
}

这段代码中，我们首先定义了一个双向链表节点 `Node` 和一个双向链表 `List`。然后，我们实现了双向链表的初始化、创建新节点、在链表尾部插入新节点、折半插入排序、打印链表等功能。在 `insertionSort` 函数中，我们使用了折半插入排序的算法对双向链表进行排序。最后，我们调用 `main` 函数来测试我们的代码。

c++实验环境中，给出含有n个学生的成绩表，每条记录由学号、姓名和分数组成，编写具体函数完成下列操作：设计一个菜单操作界面，实现录入学生基本信息，直接插入排序，折半插入排序，冒泡排序，快速排序，简单选择排序，输出学生信息，退出等基本操作

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

首先，需要定义一个学生结构体，包含学号、姓名和分数三个属性。

struct Student {
    int id;
    char name[20];
    float score;
};

接着，需要定义一个动态数组，来存储学生信息。

Student* studentList = nullptr;
int studentCount = 0;

接下来，我们可以设计菜单操作界面，让用户选择相应的操作。

void showMenu() {
    cout << "1. 录入学生信息" << endl;
    cout << "2. 直接插入排序" << endl;
    cout << "3. 折半插入排序" << endl;
    cout << "4. 冒泡排序" << endl;
    cout << "5. 快速排序" << endl;
    cout << "6. 简单选择排序" << endl;
    cout << "7. 输出学生信息" << endl;
    cout << "8. 退出" << endl;
}

接下来，我们可以实现每个操作对应的具体函数。

// 录入学生信息
void inputStudent() {
    cout << "请输入学生数量：" << endl;
    cin >> studentCount;
    studentList = new Student[studentCount];
    for (int i = 0; i < studentCount; i++) {
        cout << "请输入第" << i + 1 << "个学生的信息：" << endl;
        cout << "学号：";
        cin >> studentList[i].id;
        cout << "姓名：";
        cin >> studentList[i].name;
        cout << "分数：";
        cin >> studentList[i].score;
    }
}

// 直接插入排序
void insertionSort() {
    for (int i = 1; i < studentCount; i++) {
        Student temp = studentList[i];
        int j = i - 1;
        while (j >= 0 && studentList[j].id > temp.id) {
            studentList[j + 1] = studentList[j];
            j--;
        }
        studentList[j + 1] = temp;
    }
}

// 折半插入排序
void binaryInsertionSort() {
    for (int i = 1; i < studentCount; i++) {
        Student temp = studentList[i];
        int left = 0, right = i - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (studentList[mid].id > temp.id) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= left; j--) {
            studentList[j + 1] = studentList[j];
        }
        studentList[left] = temp;
    }
}

// 冒泡排序
void bubbleSort() {
    for (int i = 0; i < studentCount - 1; i++) {
        for (int j = 0; j < studentCount - 1 - i; j++) {
            if (studentList[j].id > studentList[j + 1].id) {
                Student temp = studentList[j];
                studentList[j] = studentList[j + 1];
                studentList[j + 1] = temp;
            }
        }
    }
}

// 快速排序
void quickSort(int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left, j = right;
    Student pivot = studentList[left];
    while (i < j) {
        while (i < j && studentList[j].id >= pivot.id) {
            j--;
        }
        studentList[i] = studentList[j];
        while (i < j && studentList[i].id <= pivot.id) {
            i++;
        }
        studentList[j] = studentList[i];
    }
    studentList[i] = pivot;
    quickSort(left, i - 1);
    quickSort(i + 1, right);
}

// 简单选择排序
void selectionSort() {
    for (int i = 0; i < studentCount - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < studentCount; j++) {
            if (studentList[j].id < studentList[minIndex].id) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            Student temp = studentList[i];
            studentList[i] = studentList[minIndex];
            studentList[minIndex] = temp;
        }
    }
}

// 输出学生信息
void outputStudent() {
    for (int i = 0; i < studentCount; i++) {
        cout << studentList[i].id << "\t" << studentList[i].name << "\t" << studentList[i].score << endl;
    }
}

// 退出程序
void exitProgram() {
    delete[] studentList;
    studentList = nullptr;
    studentCount = 0;
    exit(0);
}

最后，我们可以在主函数中调用菜单操作界面，根据用户选择调用相应的函数。

int main() {
    while (true) {
        showMenu();
        int choice;
        cin >> choice;
        switch (choice) {
            case 1:
                inputStudent();
                break;
            case 2:
                insertionSort();
                break;
            case 3:
                binaryInsertionSort();
                break;
            case 4:
                bubbleSort();
                break;
            case 5:
                quickSort(0, studentCount - 1);
                break;
            case 6:
                selectionSort();
                break;
            case 7:
                outputStudent();
                break;
            case 8:
                exitProgram();
                break;
            default:
                cout << "输入有误，请重新输入！" << endl;
                break;
        }
    }
    return 0;
}

以上就是完整的代码实现，你可以根据自己的需要进行修改和优化。