二分法排序

以你之姓@ 2022-08-26 03:52 145阅读 0赞

算法思想简单描述：   
在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们   
中间的那个元素比，如果小，则对前半再进行折半，否则对后半   
进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间   
的所有元素后移，再把第i个元素放在目标位置上。  
  
  
    二分法排序最重要的一个步骤就是查找要插入元素的位置，也就是要在哪一个位置上放我们要准备排序的这个元素。  
当我们查找到位置以后就很好说了，和插入排序一样，将这个位置以后的所有元素都向后移动一位。这样就实现了二分法排序。  
　　然后是怎么查找着一个位置呢，就是不断的比较已排序的序列中的中间元素和要排序元素，如果大于的话，说明这个要排  
序的元素在已排序序列中点之前的序列。

折半插入排序其实就是直接插入排序的一种改进，引入了二分查找算法，这样关键字的比较次数就会减少，

数量级为O(nlog^2n)，但是元素移动次数还是O(n^2)，所以折半插入排序的时间复杂度是O(n^2)。

另外，折半插入排序是稳定的排序算法；

C++代码：

\#include <stdio.h>  
\#include <iostream>

using  namespace std;

//二分排列  
void binarySort(int \*a,int len)  
\{  
 int start=0,mid=0,end=0;  
 int tmp = 0;

for(int i =1;i<len;i++)  
 \{  
  start=0,mid=0,end=i-1;  
  tmp = a\[i\];

while(start<=end)  
  \{  
   mid = (start+end)/2;  
   if(a\[mid\]>a\[i\])  
    end = mid-1;  
   else  
    start = mid+1;

\}  
  for(int j=i-1;j>=end+1;j--)  
  \{  
   a\[j+1\] = a\[j\];  
  \}  
  a\[end+1\] = tmp;

int main()  
\{

int input\[5\] = \{13, 97, 176, 13, 13\};  
 binarySort(input,5);  
 for(int i = 0;i<5;i++)  
  printf("%d,",input\[i\]);  
 printf("\\n");  
 int t;  
 cin >>t;

Java代码

package sort;

import java.util.Arrays;

public class BinarySearch2 \{  
 public static void main(String args\[\])  
 \{  
  int array\[\]=\{49,38,65,97,76,13,27\};  
  binaryInsertSort(array,array.length);  
  System.out.println("------------排序后的结果-------------");  
  System.out.println(Arrays.toString(array));  
 \}  
   
 /\*\*  
  \*  
  \* @param array 要排序的数组  
  \* @param size 数组的大小  
  \*/  
 public static void binaryInsertSort(int \[\]array,int size)  
 \{  
  int i,j,temp;  
  int low,high,mid;  
  for(i=1;i<size;i++)  
  \{  
   //将待插入的元素赋给temp，这个元素前面是有序数组，用于插入到有序数组中  
   temp=array\[i\];  
   low=0;  
   high=i-1;  
   while(low<=high)  
   \{  
    //有序数组的中间坐标，此时用于二分查找，减少查找次数  
    mid = (low+high)/2;  
    //如果有序序列中的中间元素大于待排序的元素，则有序序列的中间坐标向前搜索，否则向后搜索  
    if(array\[mid\]>array\[i\])  
     high=mid-1;  
    else  
     low = mid + 1;  
   \}  
   /\*\*  
    \* j首先赋值为要插入值的前一个元素的最后的坐标，也就是有序数组中最后一个元素的坐标  
    \* 然后依次向前扫描有序数组，然后如果满足条件则向后移动数据  
    \*/  
     
   for(j=i-1;j>=low;j--)  
   \{  
    array\[j+1\]=array\[j\];  
   \}  
   //将待排序的元素插入到array数组中  
   array\[low\]=temp;  
   System.out.println(Arrays.toString(array));  
  \}  
 \}  
   
\}