二分实现的插入排序

最近在研究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 stub
		Random 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]+"|");
		}
		
	}
}

评论

10 楼 baiweiyll 2011-03-04  

折半查找的时间复杂度为O(logN)，但定位后循环数据后移仍然要花费O(N)的代价,因此时间复杂度仍然是O(N^2).
我也贴一个二分插入排序的

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);
	}

}

9 楼 qjtttt 2011-03-03  

(start + end) >>>1

8 楼 piao_bo_yi 2011-03-03  

(start + end) / 2
溢出怎么办？

7 楼 liuningbo 2011-03-03  

dsjt 写道

Arrays有个方法可以直接返回格的数组字符串
好像是Arrays.toString

collections类已经有二分发的直接实现了，直接调用就好了

6 楼 teacher1998 2011-03-03  

现成的东西就不应该温习了？我敢保证大把的人不会，挺楼主

5 楼 mfkvfn 2011-03-03  

move()可以使用System.arraycopy()代替，这个是本志方法(Native Method)，效率比你写的好一些。

4 楼 dsjt 2011-03-03  

Arrays有个方法可以直接返回格的数组字符串
好像是Arrays.toString

3 楼 wangdongjie03 2011-03-02  

不过也挺费劲的

2 楼 julysohu 2011-03-01  

fastbo 写道

这些都是很成型的东西，应该没有什么好指教的了。哈哈。

呵呵 我是看到有人问这个算法的java实现才写的

1 楼 fastbo 2011-03-01  

这些都是很成型的东西，应该没有什么好指教的了。哈哈。