折半插入排序(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].
原创文章,作者:1402239773,如若转载,请注明出处:https://blog.ytso.com/270344.html