数据结构(13) - 折半排序(二分排序)
2022/6/25 23:25:00
本文主要是介绍数据结构(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].
这篇关于数据结构(13) - 折半排序(二分排序)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?