算法排序----二分排序法

小咪咪 2022-05-23 12:52 152阅读 0赞

现在我来简单叙述一下二分法排序的思想，在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

实际上我们看到，这是用一种方式来查找最合适的数值应该插入的位置。这个和快速排序有些相像之处但是也不完全相同。它实际上也是通过折半查找找到每个元素应该存放的位置。

下面我将根据我的代码来具体解释一下。

/**
 * 二分法排序 
 * 根据排序原则，每次我们都是在一个有序序列中插入一个新的数字 
 * 那么我们可以将这个有序序列进行二分。 
 * 左游标left为0，右游标right为i-1(i是这个数字在原数组中的位置) 
 * middle初始为。 
 * 当left<=right时 
 * middle是left和right的中值。 
 * 我们作如下操作。如果array[i]的值比array[middle]值大。 
 * 那么我们就移动左游标令值为middle+1 
 * 负责就移动右游标为middle-1 
 * 移动完成后,我们需要将i-1到left之间的值进行依次向后移动给array[i]空出一个位置然后将array[i]插入
 * 时间复杂度n
 */
 public int[] binaryInsertSort(int[] array){
 	for(int i = 0;i<array.length;i++){
 		int temp = array[i];//待插入到前面有序序列的值
 		int left = 0;//有序序列的左侧
 		int right = i-1;//有序序列的右侧
 		int middle = 0;//有序序列的中间
 		while(left <= right){
 			middle = (left + right)/2;//赋值
 			if(temp<array[middle]){
 				right = middle-1;
 			}else{
 				left = middle + 1;
 			}
 		}
 		for(int j = i-1;j>=left;j--){
 			//从i-1到left依次向后移动一位,等待temp值插入
 			array[j+1] = array[j];
 		}
 		if(left != i ){
 			array[left] = temp;
 		}
 	}
 	return array;
 }

首先我们看到，我们需要left 和 right 的值。将left的值设置为0，right的值设置为查找的位置的前一个（i-1）。

首先确定中间值middle = (left+right)/2.如果这个值比目标值大，则从右侧开始去查找。令left = middle+1;

否则令right = middle -1 ; 这个地方需要说明一下， i是不断递增的，所以每次插入的新数字都是在一个已经排好序列的数组中进行的。如果查到合适的位置，就令然后再把第i个元素前1位与目标位置（left）之间的所有元素后移，再把第i个元素放在目标位置上。

if(left != i ){
    			array[left] = temp;
    		}

这个是为了让目标位置的值赋值为temp（目标值）