数据结构(13) – 折半排序(二分排序)

折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

 1 /**
 2  * C data structure binary sort example.
 3  * 
 4  * License - MIT.
 5 */
 6 
 7 #include <stdio.h>
 8 
 9 
10 #define DISPLAY_ARRAY(i, buf, len) /
11         do { /
12             for (i = 0; i < len; i++) /
13                 printf("%d ", buf[i]); /
14             printf("/n"); /
15         } while(0)
16 
17 
18 /**
19  * binary_sort - Binary sort.
20 */
21 int binary_sort(int *buf, int len)
22 {
23     int i   = -1,
24         j   = -1,
25         tmp = -1,
26         low = -1,
27         mid = -1,
28         high= -1;
29 
30     for (i = 0; i < len; i++) {
31         tmp = buf[i];
32 
33         for (low = 0, high = i - 1; low <= high;) {
34             mid = (low + high) / 2;
35 
36             if (tmp > buf[mid])
37                 low = mid + 1;
38             else
39                 high = mid - 1;
40         }
41 
42         /* Move data. */
43         for (j = i; j > low; j--)
44             buf[j] =  buf[j - 1];
45 
46         buf[low] = tmp;
47     }
48 
49     return 0;
50 }
51 
52 
53 /**
54  * Main function.
55 */
56 int main(void)
57 {
58     int i = 0;
59     int buf[] = {30, 99, 85, 11, 75, 57, 59, 15, 78, 67};
60     int len = sizeof(buf) / sizeof(int);
61 
62     printf("The original array:/n");
63     DISPLAY_ARRAY(i, buf, len);
64 
65     binary_sort(buf, len);
66 
67     printf("The sort array:/n");
68     DISPLAY_ARRAY(i, buf, len);
69 
70     return 0;
71 }

详情请参考Github: [Link] [https://github.com/Phoebus-Ma/C-Helper/tree/main/Class-1/Sort.C].