用链表写插入排序

插入排序

时间限制: 1 Sec 内存限制: 128 MB
提交: 454 解决: 312
[提交][状态][讨论版]

题目描述

输入10个数，按照插入排序方法进行排序。

输入

输出

注意：输出最有一个数值后有个空格

2 4 6 6 7 9 9 10 10 25
25后面有一个空格

样例输入

4 6 7 2 6 9 10 25 9 10

样例输出

2 4 6 6 7 9 9 10 10 25

提示

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 #include <queue>
 5 using namespace std;
 6 typedef struct treenode *tree;
 7 struct treenode
 8 {
 9     int num;
10     tree nxt;
11 };
12 tree root;
13  
14 void build(tree p,int x)
15 {
16     while (p->nxt!= NULL && p->num < x)
17     {
18         p = p->nxt;
19     }
20     if (p->nxt == NULL&&p->num<x)
21     {
22         p->nxt = (tree)malloc(sizeof(treenode));
23         p = p->nxt;
24         p->nxt = NULL;
25         p->num = x;
26     }
27     else
28     {
29         tree temp;
30         temp = (tree)malloc(sizeof(treenode));
31         temp->nxt = p->nxt;
32         temp->num = p->num;
33         p->num = x;
34         p->nxt = temp;
35     }
36 }
37 int main()
38 {
39     int i;
40     for (i = 1; i <=10; i++)
41     {
42         int x;
43         cin >> x;
44         if (!root)
45         {
46             root = (tree)malloc(sizeof(treenode));
47             root->num = x;
48             root->nxt = NULL;
49             continue;
50         }
51         build(root, x); 
52     }
53     tree p = root;
54     for(i=1;i<=10;i++)
55     {
56         cout << p->num<<" ";
57         p = p->nxt;
58     }
59     return 0;
60 }