数据结构算法每日一练（十一）链表直接插入排序

难度：⭐⭐⭐

题目： 在链式存储结构上设计直接插入排序算法

（1）算法思想： 每次将⼀个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插⼊完成。 时间复杂度$O(n^2)$

（2）实现步骤：

• 整个排序过程为n-1趟插入，
• 先将序列中第1个记录看成是一个有序子序列，
• 然后从第2个记录开始，逐个进行插入，直至整个序列有序。

（3）代码实现：

链表实现参考: 力扣

//链式结构
struct LNode {
    int data; //数据域
    struct LNode *next; //指针域
}LNode, *LinkedList;

/**
 * 插入排序
 * @param head  链表头结点
 * @return 
 */
LinkedList InsertSort(LinkedList head) {
    if (head->next == NULL) //若链表为空，则返回
        return;
    LNode *sorted = head->next; //表示已排序链表，指向链表第一个元素
    LNode *curr = sorted->next; //表示待排元素
    while (curr != NULL) {
         if (sorted->data <= curr->data) { //若已排最后一个元素元素小于待排元素，则不需要排序
                sorted = sorted->next;
         } else {
             LNode *prev = head; //头结点
             while (prev->next->data <= curr->data) { //从头结点开始遍历，找到小于待排元素的结点
                 prev = prev->next;
             } //while
             sorted->next = curr->next; //插入待排结点
             curr->next = prev->next;
             prev->next = curr;
         } //else
        curr = sorted->next;
    } //while
    return head;
} //void

//顺式结构
/**
 * 插入排序
 * @param arr  数组
 * @param n  数据个数
 * @return 
 */
bool InsertSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i - 1]) { //若关键字小于前驱
            int t = arr[i]; //暂存关键字
            int j;
            for (j = i - 1; j >= 0 && arr[j] > t ; j--) { //检查前面排序的元素
                arr[j + 1] = arr[j]; //所有大于t的元素完后挪位
            }
            arr[j + 1] = t; //复制到插入位置
        } //if
    } //for
} //bool