二分实现的插入排序

最近在研究Java数据结构和算法

练习写了一个用插入排序的算法

查找部分使用二分查找实现的

和大家分享一下 呵呵

还请各位大牛多指教啊

呵呵

import java.util.Random;public class InsertSort {/** * 插入排序算法实现 * @author Jason * @param arr * @return */public static int[] insertSort(int[] arr) {int searchCount = 0;for (int out = 1; out < arr.length; out++) {outPrint(arr);if (arr[out]>arr[out-1]) {continue;}//普通查找算法/*for (int inn = 0; inn < out; inn++) {searchCount++;if (arr[out]<arr[inn]) {move(arr,out,inn);break;}else {continue;}}*///使用二分查找算法找到要插入的位置int start = 0;int end = out - 1;while (start <= end) {searchCount++;int searchIndex = (start + end) / 2;if (arr[out] > arr[searchIndex]) {start = searchIndex + 1;} else if (arr[out] < arr[searchIndex]) {if (searchIndex == 0|| (searchIndex != 0 && arr[out] > arr[searchIndex - 1])) {move(arr, out, searchIndex);break;} else {end = searchIndex - 1;continue;}} else {move(arr, out, searchIndex);break;}}}check(arr);System.out.println("Search Count:" + searchCount);return arr;}/** * 移动数据 */private static void move(int[] arr, int out, int inn) {int changeTemp = arr[out];for (int i = out; i > inn; i--) {arr[i] = arr[i - 1];}arr[inn] = changeTemp;}/** * 输出 */private static void outPrint(int[] arr) {System.out.println();for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + "|");}}/** * 结果检查 */private static boolean check(int[] arr) {System.out.println();for (int i = 1; i < arr.length; i++) {if (arr[i] < arr[i - 1]) {System.out.println("Sort Error!");return false;}}System.out.println("Sort Success!");return true;}/** * 测试方法 * @param args */public static void main(String[] args) {// TODO Auto-generated method stubRandom ran = new Random();int[] arr = new int[60];for (int i = 0; i < arr.length; i++) {arr[i]=ran.nextInt(300000);}System.out.println("Befor sort:");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+"|");}arr = InsertSort.insertSort(arr);System.out.println("After sort:");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+"|");}}}

package com.ncsi.straight_insertion_sort;/** * 折半插入排序 Binary Insertion Sort * 折半查找的时间复杂度为O(logN)，但定位后循环数据后移仍然要花费O(N)的代价。 * 因此时间复杂度仍然是O(N^2)，空间复杂度为O(1) * @author baiwei * */public class BISortion {/** * * @param arrays 需要排序的数组 * @param size 需要排序的大小 */void sort(int[] arrays,int size){int key;//保存关键值int i = 1;//从第二位开始for(;i<size;i++){key = arrays[i];int low = 0,hight = i-1;//折半查找while(low <= hight){int middle = (low+hight)/2;if(key < arrays[middle]){hight = middle-1;}else{low = middle+1;}}//移动位置for(int j = i-1;j>=hight+1;j--){arrays[j+1] = arrays[j];}arrays[hight+1] = key;}//打印数组for(int data:arrays){System.out.print(" "+data);}}/** * @param args */public static void main(String[] args) {int[] arrays = {49,38,65,97,76,13,27,49};new BISortion().sort(arrays, arrays.length);}}