本帖最后由 叶子和大人 于 2015-10-25 14:24 编辑
把折半查找和直接插入排序结合在一起,能减少比较的次数。- private static int[] binaryInsertSort(int[] arr) {
- for (int i = 1; i < arr.length; i++) {
- int temp = arr[i];
- int low = 0;
- int high = i - 1;
- while (low <= high) {
- int mid = (low + high) / 2;
- if (temp < arr[mid]) {
- high = mid - 1;
- } else {
- low = mid + 1;
- }
- }
- for (int j = i; j >= low + 1; j--) {
- arr[j] = arr[j - 1];
- }
- arr[low] = temp;
- }
- return arr;
- }
复制代码
|
|