手撕希尔排序和快排
2021-10-28 15:32:37

 1 #include <stdio.h>
 2 
 3 #define DATA_ARRAY_LENGTH       12
 4 
 5 // 
 6 int shell_sort(int *data, int length) {
 7 
 8     int gap = 0; //分组的跨度
 9     int i = 0, j = 0;
10 
11     for (gap = length / 2; gap >= 1;gap /= 2) { // 分组的次数
12 
13         for(i = gap; i < length; i ++) { // 每组遍历 
14 
15             int temp = data[i];
16             for (j = i - gap; j >= 0 && temp < data[j];j = j - gap) { //组内排序
17 
18                 data[j+gap] = data[j];
19 
20             }
21 
22             data[j+gap] = temp;
23         }
24 
25     }
26     return 0;
27 }
28 
29 // 
30 int sort(int *data, int left, int right) { //每一次递归， 每调用一次， 确定一个值得正确位置
31 
32     if (left >= right) return 0;
33 
34     int i = left;
35     int j = right;
36     int key = data[left];
37 
38     while (i < j) { //
39 
40         while (i < j && key < data[j]) { // 
41             j --;
42         }
43         data[i] = data[j];
44 
45         while (i < j && key >= data[i]) {
46             i ++;
47         }
48         data[j] = data[i];
49     }
50     // i == j
51     data[i] = key;
52 
53     //
54     sort(data, left, i-1);
55     sort(data, i+1, right);
56 
57 }
58 
59 
60 int quick_sort(int *data, int length) { //
61 
62     sort(data, 0, length-1);
63 
64 
65 }
66 
67 
68 int main() {
69 
70     int i = 0;
71     int data[DATA_ARRAY_LENGTH] = {23, 64, 24, 12, 9, 16, 53, 57, 71, 79, 87, 97};
72 #if 0
73     shell_sort(data, DATA_ARRAY_LENGTH);
74 #else
75 
76     quick_sort(data, DATA_ARRAY_LENGTH);
77 
78 #endif 
79 
80 
81     for (i = 0;i < DATA_ARRAY_LENGTH;i ++) {
82         printf("%4d", data[i]);
83     }
84     printf("
");
85 }