C++ 实现常用算法
排序、二分查找、树(高度、前中后层序遍历)、图的遍历、最短路径、最小生成树、求最大公约数、数制转换、水仙花数、
分治算法、贪心算法、动态规划算法、回溯算法、朴素贝叶斯分类算法、斐波那契数列、N皇后、快速幂、汉诺塔问题、
回文检查、判质数

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

//快排
//void Fastsort(vector<int> &nums,int l,int r) {
//	if (l >= r) return;
//	
//	int x = l, y = r, base = nums[l];
//
//	while(x < y){
//		while (x < y && nums[y] >= base) y--;  //后 向 前找比base小的
//		if (x < y) nums[x++] = nums[y]; 
//
//		while (x < y && nums[x] <= base) x++; //从前面找比 base 大的
//		if (x < y) nums[y--] = nums[x];
//	}
//	nums[x] = base;
//	Fastsort(nums, l, x - 1);
//	Fastsort(nums, x + 1, r);
//}

//冒泡
//void Bubblesort(vector<int> &nums,int len) {
//	for (int i = 0; i < len;i++) {
//		for (int j = len - 1; j >= i;j--) {  //第二层循环每次找一个最小的
//			if (nums[i] > nums[j]) {
//				int temp = 0;
//				temp = nums[i];
//				nums[i] = nums[j];
//				nums[j] = temp;
//			}
//		}
//	}//for
//	return;
//}


//插入排序 --O(n^2)  稳定，当n比较小时，效率较高
/* 首先初始化第一个元素有序，然后逐渐把后面的元素插入到已经排好的序列中 */
//void Insertsort(vector<int> &nums,int len) {
//	for (int j = 1; j < len;j++) {
//		int key = nums[j];
//		int i = j - 1;
//		while (i >= 0 && nums[i] > key) {
//			nums[i + 1] = nums[i]; //往后移动
//			i--;
//		}
//		nums[i + 1] = key; //退出循环，找到了比key小的元素
//	}//for
//	return ;
//}

//归并排序 -- O(nlgn) 稳定的排序
//假设初始序列是有n个记录，则可以看成是n个长度1有序的子序列，然后两两合并，得到n/2个长度为2或者1的子序列，
//再两两合并，如此重复，直到得到一个长度为n的序列
//void Merge(vector<int> &nums, int start, int mid, int end) {
//	int n = end - start + 1;//临时数组存储合并后的有序序列
//	int* temp = new int[n];  //动态的申请内存
//	int i = 0;
//	int left = start;
//	int right = mid + 1;
//	while (left <= mid && right <= end) //原来的两个区间是按照mid分开的，所以每次按照mid为基准合并
//		temp[i++] = nums[left] <= nums[right] ? nums[left++] : nums[right++];
//	while (left <= mid)
//		temp[i++] = nums[left++];
//	while (right <= end)
//		temp[i++] = nums[right++];
//	for (int j = 0; j<n; ++j)
//		nums[start + j] = temp[j];
//	delete[] temp;//删掉堆区的内
//}

//void Mergesort(vector<int> &nums,int start,int end) {
//	if (start == end) return;
//	int mid = start + (end - start) / 2;
//	Mergesort(nums, start, mid);
//	Mergesort(nums, mid + 1, end);
//	Merge(nums, start, mid, end);  //合并区间函数
//}

/* 堆排序 -- O(nlogn) -- 不稳定的排序 */
//堆排序分为：小顶堆和大顶堆；小顶堆：每个节点的值都小于或等于其子节点的值；大顶堆：每个节点的值都大于或等于其子节点的值
//void swap(vector<int> &nums,int i,int j) {
//	int temp = nums[i];
//	nums[i] = nums[j];
//	nums[j] = temp;
//}
//
2、调整树结构  -- 每次调整的是三个节点的子结构
//void heapify(vector<int> &nums,int n,int i) {  //n代表元素个数，i代表从第i个节点开始调整
//	if (i >= n) return;
//	int c1 = i * 2 + 1;//当前节点左节点在数组中的位置
//	int c2 = i * 2 + 2;//右节点
//	int max = i; //max记录的是最大值的下标
//	if (c1 < n && nums[c1] > nums[max]) max = c1;
//	if (c2 < n && nums[c2] > nums[max]) max = c2;
//
//	if (max != i) {  //最大值下标发生变化
//		swap(nums, max, i); //让最大值在根节点
//		heapify(nums, n, max);  //因为树的结构改变，需要继续从max的位置修改，使得符合堆结构
//	}
//}
//
//
1、建堆
//void build_heap(vector<int> &nums, int n) {
//	int last_node = n - 1; //最后一个节点再数组中的位置
//	int parents = (last_node - 1) / 2;
//	int i;
//	for (i = parents; i >= 0;i--) { //从倒数第二层开始调整树结构
//		//2、调整树结构，使得满足堆的性质
//		heapify(nums, n, i); //对所有节点做heapify
//	}
//}
//
//void Heap_sort(vector<int> &nums,int n) {
//	//1、建堆
//	build_heap(nums,n);
//
//	int i;
//	for (int i = n - 1; i >= 0;i--) {
//		swap(nums, i, 0);//堆排序思想：将 最后一个节点和根节点交换，然后砍断最后一个叶子节点
//
//		heapify(nums, i, 0);  //通过传入的参数i来达到砍断节点的效果，i代表 "树结构" 剩下的节点数量
//	}
//}


//希尔排序 --shell
/*
	1、首先，从数组的首元素开始每隔 步长 个元素就挑选一个元素出来作为子数组元素；
	2、然后每个子数组各自进行比较，比较好后，每个子数组都有顺序，进入下一轮，步长减少
	   再根据步长分组进行比较
	3、重复以上操作，直到步长为1
*/
//void Shellsort(vector<int> &nums,int n) {
//	int i, j, step;
//	for (step = n / 2; step > 0; step = step / 2) {
//		for (i = 0; i < step;i++) {  //i是子数组的编号
//			for (j = i + step; j < n;j = j + step) {  //数组下标j,数组步长下标j+step
//				if (nums[j] < nums[j - step]) {
//					int temp = nums[j];
//					int k = j - step;
//
//					while (k >= 0 && temp < nums[k]) {
//						nums[k + step] = nums[k];  //把大的往后插入
//						k = k - step;
//					}
//					nums[k + step] = temp; //小的往前插入
//				} //if
//			} //for j
//		}  //for i
//	}// for step
//}

//二分查找排序数组  找到返回下标，找不到返回-1
int binarysearch(vector<int> &nums,int target) {
	sort(nums.begin(), nums.end());
	int left = 0, right = nums.size()-1, mid;
	while (left <= right) {
		mid = left + (right - left) / 2;
		if (target == nums[mid]) {
			return mid;
		}
		if (target > nums[mid])
			left = mid + 1;
		if (target < nums[mid]) right = mid - 1;
	}
	return -1;
}

int main() {

	//给定数组实现排序算法
	vector<int> nums = {2,1,4,3,5,6};

	//快排
	//Fastsort(nums,0,nums.size()-1);

	//冒泡
	//Bubblesort(nums,nums.size());

	//插入排序
	//Insertsort(nums,nums.size());

	//归并排序
	//Mergesort(nums,0,nums.size()-1);

	
	//堆：是一个完全二叉树
	/*
		堆排序：
		1、首先应该有个堆，利用bulid_heap创建堆(实质可以看作是创建一颗完全二叉树)
		2、对上面创建的堆的结构进行调整，使之符合堆的特点 heapify
		3、对调整好的堆进行堆排序(就是输出一个有序的排列) Heap_sort
	*/
	//Heap_sort(nums,nums.size());

	//希尔排序
	//Shellsort(nums,nums.size());

	 
	//二分查找   O(logN)
	int target = 2;
	int index = binarysearch(nums,target);
	cout << index << endl;

	system("pause");
	return 0;
}