1.认识复杂度，对数器二分法

1.认识复杂度，对数器二分法 一.复杂度

• 时间复杂度
• 额外空间复杂度
• 常数时间的 *** 作
  1. 常见的算术运算(+，-，*，/，%)
  2. 常见的位运算(>>，<<，|，&，^)
  3. 赋值，比较，自增，自减
  4. 数组寻址 *** 作

选择排序

    想法：首先在0 ~ n-1范围内找一个最小的数和0位置的数交换，接着在1 ~ n-1范围内找一个最小的数和1位置的数交换，直到在n-2 ~ n-1范围内(即最后两个)完成上面的 *** 作，算法完成。

void select_sort(int* arr,int n)
{
	if (arr == NULL || n < 2)
	{
		return;
	}
	for (int i = 0; i < n-1; i++)		
	{
		int min = i;
		for (int j = i+1; j < n; j++)	
		{
			min = arr[min] > arr[j] ? j : min;
		}
		swap(arr,min,i);
	}
}

冒泡排序

    想法：首先在0~n-1上把大数放在n-1位，直到只剩下0 ~ 1位置的数，把较大的数放在1位置，最后一个自动排好。先把外层循环的下标i卡到n-1位置，内层循环下标j从0开始,但是需要小于i，正好不会越界。

void bubble_sort(int* arr, int n)
{
	if (arr == NULL || n < 2)
	{
		return;
	}
	for (int i = n - 1; i > 0; i--)
	{
		for (int j = 0; j < i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(arr, j, j + 1);
			}
		}
	}
}

插入排序

    想法：首先0~0位置自动排好，接着0 ~1位置，盯着1位置，如果前面的数大就交换，然后往前走一走，如果遇到数不比自己大，就进行下一轮。直到进行到0 ~ n-1位置，算法完成。

void insert_sort(int* arr, int n)
{
	if (arr == NULL || n < 2)
	{
		return;
	}
	for (int i = 1; i < n; i++)
	{
		for (int j = i; j > 0&& arr[j - 1] > arr[j]; j--)
		{
			swap(arr, j - 1, j);
		}
	}
}

二.对数器

1. 生成随机数据。
2. 使用暴力方法实现功能。
3. 与优化的方法进行结果的比对。

//生成随机数据的函数
vector generateRandomArray(int maxSize,int maxValue)
{
	vector vec;
	int length = (rand() % maxSize) + 1;
	for (int i = 0; i < length; i++)
	{
		vec.push_back((rand() % maxValue) + 1);
	}
	return vec;
}
//注意！！！！要在main()中进行srand()的设置

三.二分法

    想法：一般的二分法要求是有序数组，只要数组还有一个元素，就一直干。首先设置一个下标mid指向数组的中点位置，如果要找的数

bool erfen(vector v,int value)
{
	int L = 0;
	int R = v.size()-1;
	int mid = 0;
	while (L <= R)
	{
		mid = L + ((R - L) >> 1);		//防止越界
		if (v[mid] == value)
		{
			return true;
		}
		else if (v[mid] > value)
		{
			R = mid - 1;
		}
		else
		{
			L = mid + 1;
		}
	}
	return false;
}

题目一：在一个有序数组中，找到大于等于某个数最左边的位置。

    想法：采用二分的思想，首先定义变量mid指向中点的位置，如果mid指向的值>=那个数，那么先登记一下mid的位置，然后砍掉mid右边的数；否者砍掉mid左边的数。直到搞完整个数组。

int fun(vector v,int num)
{
	int L = 0;
	int R = v.size() - 1;
	int index = -1;
	while (L <= R)
	{
		int mid = L + ((R - L) >> 1);
		if (v[mid] >= num)
		{
			index = mid;
			R = mid - 1;
		}
		else
		{
			L = mid + 1;
		}
	}
	return index;
}

题目二：局部最小值问题(无序数组，任意相邻的数不等)

    想法：仍然可以采用二分的思想，首先判断0位置是否<1位置的数，如果是则直接返回；否者判断最后两个数的情况，如果倒数第1个数比倒数第2个数小，则直接返回；否者从1位置到n-2位置进行二分，首先定义mid指向中点位置，如果mid指向的数>mid-1指向的数，那么去mid左边去找吧；如果mid指向的数>mid+1指向的数，那么去mid右边找吧。(即哪边小去哪边找)如果不满足以上两种情况，那么mid就是我要找的数。

int fun(vector v)
{
	if (v.size() == 1 || v[0] < v[1])
	{
		return 0;
	}
	if (v[v.size() - 1] < v[v.size() - 2])
	{
		return v.size() - 1;
	}
	int L = 1;
	int R = v.size() - 2;
	int mid = 0;
	while (L <= R)
	{
		mid = L + ((R - L) >> 1);
		if (v[mid] > v[mid - 1])
		{
			R = mid - 1;
		}
		else if (v[mid] > v[mid + 1])
		{
			L = mid + 1;
		}
		else
		{
			return mid;
		}
	}
}