二分法排序实例（递归与非递归实现）--MyEclipse, Maven, Junit

蔚落 2022-09-25 09:19 83阅读 0赞

若有疑问，可参考http://blog.csdn.net/yongaini10/article/details/52230186博文

SecondDivideSort:

package club.younge.demo;
    
    public class SecondDivideSort {
    
    	public int[] secondDivide(int[] data){
    		int left, right, middle, j;
    		int comp;
    		for (int i = 1; i < data.length; i++) {
    			left = 0;
    			right = i - 1;
    			comp = data[i];
    			//寻找left插入点
    			while (right >= left) {
    				middle = (left + right) / 2;
    				if (comp >= data[middle]) {
    					left = middle + 1;
    				}else {
    					right = middle - 1;
    				}
    			}
    			//left插入点（含）至比较点前一元素整体后移一个单位
    			for (j = i - 1; j >= left; j--) {
    				data[j + 1] = data[j];
    			}
    			//left插入点插入比较点元素
    			data[left] = comp;
    		}
    		return data;
    		
    	}
    }

TestSort:

package club.younge.demo;
    
    import org.apache.commons.lang.math.RandomUtils;
    import org.junit.Test;
    
    public class TestSort {
    
    	@Test
    	public void testDivideSort() {
    		int[] data = new int[20];
    		int[] result = new int[20];
    		for (int i = 0; i < data.length; i++) {
    			data[i] = RandomUtils.nextInt(20);
    		}
    		System.out.println("Before sort:");
    		for (int i = 0; i < data.length; i++) {
    			System.out.print(data[i] + "  ");
    		}
    		SecondDivideSort secondDivideSort = new SecondDivideSort();
    		result = secondDivideSort.secondDivide(data);
    		System.out.println("\nAfter sort:");
    		for (int i = 0; i < result.length; i++) {
    			System.out.print(result[i] + "  ");
    		}
    	}
    }

单元测试结果：

Before sort:  
16 3 16 13 5 5 10 7 18 18 13 3 1 3 17 19 19 2 19 11  
After sort:  
1 2 3 3 3 5 5 7 10 11 13 13 16 16 17 18 18 19 19 19

今天去面试，笔试题，出了二分法排序（递归和非递归实现），现给出源码：

SortEntity,排序实体类：

package club.younge.sort;
    
    import java.util.Random;
    
    /** 
     * @className:SortEntity 
     * @function: 排序实体类抽离数组和数组长度  
     * @reason:   TODO ADD REASON. 
     * @date:     2016年8月23日 下午1:54:19
     * @author   Younge 
     * @version   
     * @since    JDK 1.8 
     * @see       
     */
    public class SortEntity {
    	private int[] data;
    	private int len;
    	public SortEntity(int[] data){
    		this.data = data;
    		this.len = data.length;
    		this.generateRandomData();
    	}
    	public int[] getData() {
    		return data;
    	}
    	public void setData(int[] data) {
    		this.data = data;
    	}
    	public int getLen() {
    		return len;
    	}
    	public void setLen(int len) {
    		this.len = len;
    	}
    	
    	public final void generateRandomData(){
    		Random random = new Random(20l);
    		for (int i = 0; i < len; i++) {
    			data[i] = Math.abs(random.nextInt()%20);
    			System.out.print(" "+ data[i]);
    		}
    	}
    	
    	public  final void printData(){
    		for (int i = 0; i < len; i++) {
    			System.out.print(" "+ data[i]);
    		}
    	}
    	
    	public void println(String message){
    		System.out.println(message);
    	}
    	//非递归查找插入点
    	public final int[] secondDivide() {
    		int left, right, middle, j;
    		int comp;
    		for (int i = 1; i < len; i++) {
    			left = 0;
    			right = i - 1;
    			comp = data[i];// 比较点
    			// 二分法寻找left插入点
    			while (right >= left) {
    				middle = (left + right) / 2;
    				if (comp >= data[middle]) {
    					left = middle + 1;
    				} else {
    					right = middle - 1;
    				}
    			}
    			// left插入点（含）至比较点前一元素整体后移一个单位
    			for (j = i - 1; j >= left; j--) {
    				data[j + 1] = data[j];
    			}
    			// left插入点插入比较点元素
    			data[left] = comp;
    		}
    		return data;
    
    	}
    	
    	//递归查找插入点
    	public int[] secondDivideTraverse() {
    		int left, right, j;
    		int comp;
    		for (int i = 1; i < len; i++) {
    			left = 0;
    			right = i - 1;
    			comp = data[i];// 比较点
    			// 二分法寻找left插入点
    			left = this.findLeft(left, right, data, comp);
    			// left插入点（含）至比较点前一元素整体后移一个单位
    			for (j = i - 1; j >= left; j--) {
    				data[j + 1] = data[j];
    			}
    			// left插入点插入比较点元素
    			data[left] = comp;
    		}
    		return data;
    	}
    
    	public int findLeft(int left, int right, int[] data, int comp) {
    		int m = (left + right) / 2;
    		if (left > right) {
    			return left;
    		} else {
    			if (comp >= data[m]) {
    				return findLeft(m + 1, right, data, comp);
    			} else {
    				return findLeft(left, m - 1, data, comp);
    			}
    		}
    	}
    	
    }

SortEntityTest, 测试类：

package club.younge.test;
    
    import club.younge.sort.SortEntity;
    
    /** 
     * @className:SortEntityTest 
     * @function: 排序实体类测试 
     * @reason:    
     * @date:     2016年8月23日 下午2:01:43
     * @author   Younge 
     * @version   
     * @since    JDK 1.8 
     * @see       
     */
    public class SortEntityTest {
    	public static void main(String[] args) {
    		int[] data = new int[20];
    		System.out.println("Before second divide sort(traverse):");
    		SortEntity entity = new SortEntity(data);
    		entity.println("\nAfter second divide sort(traverse):");
    		entity.secondDivideTraverse();
    		entity.printData();
    		
    		entity.println("\n\nBefore second divide sort(none traverse):");
    		entity.generateRandomData();
    		entity.println("\nAfter second divide sort(none traverse):");
    		entity.secondDivide();
    		entity.printData();
    		
    	}
    }