欢迎光临我的博客[http://poetize.cn]，前端使用VUE2，聊天室使用VUE3，后台使用Spring Boot
简介
二分排序是指利用二分法的思想对插入排序进行改进的一种插入排序算法，
可以利用数组的特点快速定位指定索引的元素。
二分法排序的思想
必须是有序数组
在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，
如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，找到位置
然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。
复杂度
二分排序的时间复杂度是O(logn)，
空间复杂度O(1)，是稳定排序。
1 class binary { 2 //循环查找 3 public static int search1(int[] arr, int count) { 4 //长度 5 int len = arr.length; 6 //边界 7 int left = 0, right = len - 1; 8 //中间 9 int mid = 0; 10 while (left <= right) { 11 mid = (left + right) / 2; 12 if (arr[mid] > count) { 13 right = mid - 1; 14 } else if (arr[mid] < count) { 15 left = mid + 1; 16 } else { 17 return mid; 18 } 19 } 20 return -1; 21 } 22 23 //递归查找 24 public static int search2(int[] arr, int left, int right, int count) { 25 if (left <= right && arr[left] <= count && arr[right] >= count) { 26 //中间 27 int mid = (left + right) / 2; 28 if (arr[mid] > count) { 29 right = mid - 1; 30 return search2(arr, left, right, count); 31 } else if (arr[mid] < count) { 32 left = mid + 1; 33 return search2(arr, left, right, count); 34 } else if (arr[mid] == count) { 35 return mid; 36 } 37 38 } 39 return -1; 40 } 41 42 //二分排序 43 public static void binarySort(int[] arr) { 44 for (int i = 1; i < arr.length; i++) { 45 //有序的第一个 46 int left = 0; 47 //有序的最后一个 48 int right = i - 1; 49 //中间值 50 int mid = 0; 51 int temp = arr[i]; 52 //寻找位置 53 while (left <= right) { 54 mid = (left + right) / 2; 55 if (arr[mid] > temp) { 56 right = mid - 1; 57 } else if (arr[mid] <= temp) { 58 //若相等，保证新元素插在旧元素后面，保证稳定性 59 left = mid + 1; 60 } 61 } 62 //空出位置，等待temp插入,left位置即是待插入的位置 63 //此步骤用于空出位置 64 for (int j = i - 1; j >= left; j--) { 65 arr[j + 1] = arr[j]; 66 } 67 //i==left的情况left会在right右边，此时要排序的数是最大的，left移在i的位置 68 if (i != left) { 69 arr[left] = temp; 70 } 71 } 72 } 73 }
今天的文章排序算法一二分排序怎么算_二路归并排序递归分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/45913.html
