七大排序之希尔排序

 1 void ShellSort(int* arr, int length) {
 2     int increasement = length; 
 3     do
 4     {
 5         //分组数
 6         increasement /= 3 + 1;
 7         int i, j;
 8         //i 表示的是每一个分组的最前面一个数，10个数分成四组，则第一组第一个数下标为0，
 9         //第二组下标为1，第三组下标为2，第四组下标为3，从这里可以看出，他是在前一组完成插入排序后
10         //再进行下一组插入排序的。
11         for (i = 0; i < increasement; i += 1) {
12             int temp;
13             for ( j = i+increasement; j < length; j+=increasement)
14             {
15                 if (arr[j] < arr[j - increasement]) {
16                     temp = arr[j];
17                     int k;
18                     //这里k>=i可以，k>=0也可以，思考一下为什么？
19                     for ( k = j-increasement; k>=0&&arr[k]>temp; k-=increasement)
20                     {
21                         arr[k + increasement] = arr[k];
22                     }
23                     //不能改成arr[i]因为不一定到最前面
24                     arr[k+increasement] = temp;
25                 }
26             }
27         }
28 
29     } while (increasement>1);
30 }

 1 #include<iostream>
 2 #include<time.h>
 3 #include<stdlib.h>
 4 #include<sys/timeb.h>
 5 using namespace std;
 6 const int Max = 10000;
 7 
 8 void swap(int& a, int& b) {
 9     int temp = a;
10     a = b;
11     b = temp;
12 }
13 
14 long getSystemTime() {
15     struct timeb tb;
16     ftime(&tb);
17     return tb.time * 1000 + tb.millitm;
18 }
19 void Print(const int* arr, int length) {
20     for (int i = 0; i < length; i++) {
21         cout << arr[i] << " ";
22     }
23 }
24 void InsertSort(int* arr, int length) {
25     for (int i = 1; i < length; i++) {
26         if (arr[i - 1] > arr[i]) {
27             int temp = arr[i];
28             int k = i - 1;
29             for (; k >= 0; k--) {
30                 if (arr[k] > temp)
31                     arr[k + 1] = arr[k];
32                 else
33                 {
34                     break;
35                 }
36             }
37             arr[k + 1] = temp;
38         }
39     }
40 }
41 void ShellSort(int* arr, int length) {
42     int increasement = length; 
43     do
44     {
45         //分组数
46         increasement /= 3 + 1;
47         int i, j;
48         //i 表示的是每一个分组的最前面一个数，10个数分成四组，则第一组第一个数下标为0，
49         //第二组下标为1，第三组下标为2，第四组下标为3，从这里可以看出，他是在前一组完成插入排序后
50         //再进行下一组插入排序的。
51         for (i = 0; i < increasement; i += 1) {
52             int temp;
53             for ( j = i+increasement; j < length; j+=increasement)
54             {
55                 if (arr[j] < arr[j - increasement]) {
56                     temp = arr[j];
57                     int k;
58                     //这里k>=i可以，k>=0也可以，思考一下为什么？
59                     for ( k = j-increasement; k>=0&&arr[k]>temp; k-=increasement)
60                     {
61                         arr[k + increasement] = arr[k];
62                     }
63                     //不能改成arr[i]因为不一定到最前面
64                     arr[k+increasement] = temp;
65                 }
66             }
67         }
68 
69     } while (increasement>1);
70 }
71 int main() {
72     int arr[Max];
73     int arr2[Max];
74     srand((unsigned)time(NULL));
75     for (int i = 0; i < Max; i++) {
76         arr[i] = rand() % Max;
77         arr2[i] = arr[i];
78     }
79     //cout << "排序前：\n";
80     //Print(arr, Max);
81     long pt = getSystemTime();
82     ShellSort(arr, Max);
83     long at = getSystemTime();
84     //cout << "\n排序后：\n";
85     //Print(arr, Max);
86     cout << "\ntime of Shellsort:" << at - pt << "ms\n";
87     pt = getSystemTime();
88     InsertSort(arr2, Max);
89     at = getSystemTime();
90     cout << "\ntime of Insertsort:" << at - pt << "ms\n";
91     return 0;
92 }