二分插入排序

  1. #include <stdio.h>
  2. // 分类 -------------- 内部比较排序
  3. // 数据结构 ---------- 数组
  4. // 最差时间复杂度 ---- O(n^2)
  5. // 最优时间复杂度 ---- O(nlogn)
  6. // 平均时间复杂度 ---- O(n^2)
  7. // 所需辅助空间 ------ O(1)
  8. // 稳定性 ------------ 稳定
  9. void InsertionSortDichotomy(int A[], int n)
  10. {
  11.     for (int i = 1; i < n; i++)
  12.     {
  13.         int get = A[i];                    // 右手抓到一张扑克牌
  14.         int left = 0;                    // 拿在左手上的牌总是排序好的，所以可以用二分法
  15.         int right = i - 1;                // 手牌左右边界进行初始化
  16.         while (left <= right)            // 采用二分法定位新牌的位置
  17.         {
  18.             int mid = (left + right) / 2;
  19.             if (A[mid] > get)
  20.                 right = mid - 1;
  21.             else
  22.                 left = mid + 1;
  23.         }
  24.         for (int j = i - 1; j >= left; j--)// 将欲插入新牌位置右边的牌整体向右移动一个单位
  25.         {
  26.             A[j + 1] = A[j];
  27.         }
  28.         A[left] = get;                    // 将抓到的牌插入手牌
  29.     }
  30. }
  31. int main()
  32. {
  33.     int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大二分插入排序
  34.     int n = sizeof(A) / sizeof(int);
  35.     InsertionSortDichotomy(A, n);
  36.     printf("二分插入排序结果：");
  37.     for (int i = 0; i < n; i++)
  38.     {
  39.         printf("%d ", A[i]);
  40.     }
  41.     printf("\n");
  42.     return 0;
  43. }

二分查找

  1. public static int binarySearch(Integer[] srcArray, int des) {
  2.     //定义初始最小、最大索引
  3.     int low = 0;
  4.     int high = srcArray.length - 1;
  5.     //确保不会出现重复查找，越界
  6.     while (low <= high) {
  7.         //计算出中间索引值
  8.         int middle = (high + low)>>>1 ;//防止溢出
  9.         if (des == srcArray[middle]) {
  10.             return middle;
  11.         //判断下限
  12.         } else if (des < srcArray[middle]) {
  13.             high = middle - 1;
  14.         //判断上限
  15.         } else {
  16.             low = middle + 1;
  17.         }
  18.     }
  19.     //若没有，则返回-1
  20.     return -1;
  21. }