2021-04-10_二分排序的时间复杂度

二分

二分排序的期望复杂度是O(nlgn)，最差情况是O(n^2)
二分思想：二分法时间复杂度为O(logn)，主要思想就是不断缩小区间范围，最后找到要找的那个数。

1.二分排序法

二分排序的工作原理是不断的依次将元素插入前面已排好序的序列中。在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。这样做相对与暴力枚举来说时间复杂度会低许多，主要思想就是上面所说，代码如下（我用的是java来写的）：

import java.util.Scanner;
public class 二分法排序 {
	public static void sort(int[] sum,int N) {
		Scanner in=new Scanner(System.in);
		System.out.println("请输入十个数字：");
		for(int i=0;i<N;i++)
			sum[i]=in.nextInt();
		//二分排序（核心思想）
		for(int i=0;i<N;i++)
		{
			int start=0;         //定义初始位置
			int end=i-1;         //开始插入第i个元素，此时数组长度end为i-1
			int mid=0;           
			int ex=sum[i];       //要插入的数ex
			while(start<=end)    //判断循环结束条件，即左边大于右边时结束。
			{
				mid=end+start;   //取中间数
				if(sum[mid]>ex)  //比较中间的值和插入的值，前者大于后者说明应该插在左边
					end=mid-1;	 //将界限缩小
				else             //比较中间的值和插入的值，前者小于后者说明应该插在在右边
					start=mid+1; //将界限缩小
			}
			for ( int j=i-1;j>end;j--)//找到了插入的位置，然后将这个位置以后的所有元素向后移动  
			{  
				sum[j + 1] = sum[j];  
			}  
			sum[end+1]=ex;       //将改元素插入数组
		}
		for(int i=0;i<N;i++)     //循环输出
		System.out.print(sum[i]+" ");
	}
	public static void main(String[] args) {
		final int N=10,M=15;
		int sum[]=new int[M];
		sort(sum,N);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

在这里我只举了十个数排序的例子，可以修改，主要的排序的思想。

2.二分查找法（折半查找法）

第一步：首先找到中间位置，即左边界、右边界的和除以2
第二步：判断要的数位于那个区间，如果在左边界和中间位置之间，那么右边界就要移到中间位置；如果在右边界和中间位置之间，那么左边界就要移到中间位置
第三步：再次确定中间位置，重复1,2步，直到找到要找的那个数

date int v[5];
int right=4,left=0;
while(left<right)
{
	int mid=(left+right)>>1;
	if(v[mid]<x)
		left=mid+1;
	else
		right=mid;
	...
}
return v[left]

1
2
3
4
5
6
7
8
9
10
11
12
13

同时我们要特别注意边界问题，如果数组中一定有要查找的数字可以这样写：

date int v[5];
int right=4,left=0;
while(left<=right)
{
	int mid=(left+right)>>1;
	if(v[mid]<x)
		left=mid+1;
	else
		right=mid-1;
	...
}
return v[left]
1
2
3
4
5
6
7
8
9
10
11
12