09-排序1 排序

作为电子专业的学生，我所用的C语言教材上关于冒泡排序就算是重点和难点了，看了这题就知道那就是小菜一碟，冒泡排序测试点4、6、8超时，插入排序测试点6超时，最后用了希尔排序，还是在使用最原始的增量序列的条件下，测试点全过了

 1 #include <stdio.h>
 2 //#include <stdbool.h>
 3 
 4 //void Bubble_Sort(int * a, int n);
 5 //void Insert_Sort(int * a, int n);
 6 void Shell_Sort(int * a, int n);
 7 
 8 int main()
 9 {
10     int N;
11     scanf("%d", &N);
12     int a[N];
13     
14     for(int i = 0; i < N; i++)
15     {
16         scanf("%d", &a[i]);
17     }
18 //    Bubble_Sort(a, N);
19 //    Insert_Sort(a, N);
20     Shell_Sort(a, N);
21     
22     return 0;
23 }
24 
25 //void Bubble_Sort(int * a, int n)
26 //{
27 //    int i, j;
28 //    bool flag;
29 //    
30 //    for(i = n - 1; i > 0; i--)
31 //    {
32 //        flag = true;
33 //        for(j = 0; j < i; j++)
34 //        {
35 //            if(a[j] > a[j + 1])
36 //            {
37 //                flag = false;
38 //                a[j] += a[j + 1];
39 //                a[j + 1] = a[j] - a[j + 1];
40 //                a[j] -= a[j + 1];
41 //            }
42 //        }
43 //        if(flag)
44 //            break;
45 //    }
46 //    for(i = 0; i < n; i++)
47 //    {
48 //        printf("%d", a[i]);
49 //        if(i != n - 1)
50 //            printf(" ");
51 //        else
52 //            printf("
");
53 //    }
54 //}
55 
56 //void Insert_Sort(int * a, int n)
57 //{
58 //    int i, j, tmp;
59 //    
60 //    for(i = 1; i < n; i++)
61 //    {
62 //        tmp = a[i];
63 //        for(j = i; j > 0 && a[j - 1] > tmp; j--)
64 //            a[j] = a[j - 1];
65 //        a[j] = tmp;
66 //    }
67 //    for(i = 0; i < n; i++)
68 //    {
69 //        printf("%d", a[i]);
70 //        if(i != n - 1)
71 //            printf(" ");
72 //        else
73 //            printf("
");
74 //    }
75 //}
76 
77 void Shell_Sort(int * a, int n)
78 {
79     int i, j, k, tmp;
80     for(i = n / 2; i > 0; i /= 2)
81     {
82         for(j = i; j < n; j++)
83         {
84             tmp = a[j];
85             for(k = j; k >= i && a[k - i] > tmp; k -= i)
86                 a[k] = a[k - i];
87             a[k] = tmp;
88         }
89     }
90     for(i = 0; i < n; i++)
91     {
92         printf("%d", a[i]);
93         if(i != n - 1)
94             printf(" ");
95         else
96             printf("
");
97     }
98 }

题目如下

给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。

本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：

数据0：只有1个元素；
数据1：11个不相同的整数，测试基本正确性；
数据2：10³个随机整数；
数据3：10⁴个随机整数；
数据4：10⁵个随机整数；
数据5：10⁵个顺序整数；
数据6：10⁵个逆序整数；
数据7：10⁵个基本有序的整数；
数据8：10⁵个随机正整数，每个数字不超过1000。

输入格式：

输入第一行给出正整数N（<= 10⁵），随后一行给出N个（长整型范围内的）整数，其间以空格分隔。

输出格式：

在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。

输入样例：

11
4 981 10 -17 0 -20 29 50 8 43 -5

输出样例：

-20 -17 -5 0 4 8 10 29 43 50 981