链表插入排序#

算法思维#

将第一个元素看作一个有序序列
将后面的元素按升降次序插入有序序列，一直重复直到整个序列有序

设计思维#

用带有头节点的列表 list 方便运算
因为升序和降序只有判断方法不一样，所以可以设置一个mode变量表示排序方式
创建一个新的链表 list_sorted 存放有序序列，按反序放置，此时有序数列的最后一个元素就是此链表的第一个元素
取出一个未排序的元素，找到相应的位置并插入，重复4直到所有结点有序
再按照反序把 list_sorted 中的元素插入 list中，即可得到最后结果

算法实现#

1
// 判断
2
int sort_judgeWithMode(int num1, int num2, int mode)
3
{
4
    return mode? num1<num2:num1>num2;
5
}
6

7

8
// 链表插入排序
9
/*
10
mode: 非0：升序， 0：降序
11
*/
12
void sort_straightInsertionSort_list(SNode* slist, int mode)
13
{
14
    SNode *slist_sorted = createSNode(-1);
15
    SNode *current, *slist_sorted_tmp, *slist_sorted_tmp_next;
16

17
    while(slist->next)
18
    {
19
        // 获得一个未排序的
20
        current = deleteNextSNode(slist);
21
        slist_sorted_tmp = slist_sorted;
22
        while(1)
23
        {
24
            // c语言好像不能直接用->next->value，所以设个变量
25
            slist_sorted_tmp_next = slist_sorted_tmp->next;
26
            if(slist_sorted_tmp_next == NULL ||
27
               sort_judgeWithMode(slist_sorted_tmp_next->value, current->value, mode))
28
            {
29
                addSNodeToTheNext(slist_sorted_tmp, current);
30
                break;
31
            }
32
            slist_sorted_tmp = slist_sorted_tmp_next;
33
        }
34
    }
35

36
  // 将有序链表反序插回
37
    while(slist_sorted->next)
38
    {
39
        addSNodeToTheNext(slist, deleteNextSNode(slist_sorted));
40
    }
41
}

运算结果#

测试代码

1
#define N 11
2

3
int main()
4
{
5
    int arr[N] = {-1,1,3,543,234,65,23,4,23,234,87};
6

7
    SNode* slist = createList(arr,N);
8
    printSNodes(slist,"%d ", "\n");
9
    printf("降序：");
10
    sort_straightInsertionSort_list(slist, 0);
11
    printSNodes(slist,"%d ", "\n");
12
    printf("升序：");
13
    sort_straightInsertionSort_list(slist, 1);
14
    printSNodes(slist,"%d ", "\n");
15

16
    return 0;
17
}

运算结果

原文链接：CSDN