#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int order_find(int* arr, size_t len,int key)
{
	for(int i=0;i<len;i++)
	{
		if(arr[i]==key)
		return 1;
	}
	return 0;
}
int dichotomy(int* arr,size_t start,size_t len,int key)
{
	/*if(len<start)return 0;
	if(arr[start+(len-start)/2]==key)return 1;
	else if(arr[start+(len-start)/2]>key)
	 dichotomy(arr,start,len/2-1,key);
	else 
	{
	if(key>arr[len])return 0;
	return dichotomy(arr,len/2-1,len,key);
	
	}*/
	if(key<arr[start]||key>arr[len])
	return 0;
	while(start<=len)
	{
		int pi=(start+len)/2;
		if(arr[pi]>key)
		{
			len=pi-1;
		}
		else if(arr[pi]<key)
		{
			start=pi+1;
		}
		else if(arr[pi]==key)
		{
			return 1;
		}
	}
	return 0;
}
//用宏函数交换数值，#define swap(a,b){typeof(a) t=a;a=b;b=t;}
void swap(int* p1,int* p2)
{
	int temp=*p1;
	*p1=*p2;
	*p2=temp;
	
}
void show_sort(int* arr,int len)
{
	for(int i=0;i<len;i++)
	{
		printf("%d ",arr[i]);
	}
	printf("\n");
}
//冒泡排序（适用于数据基本有序）
void bubble(int* arr,size_t len)
{
	for(int i=len-1;i>0;i--)
	{
		bool flag=true;//设置标志位 用于体现冒泡排序对数有序性的敏感性
		for(int j=0;j<i;j++)
		{
			if(arr[j]>arr[j+1])
			{
				swap(&arr[i],&arr[j]);
				flag=false;
			}	
		}
		if(flag) break;
	}
}
//插入排序（适用于数据部分有序）
void insert_sort(int* arr,size_t len)
{
	for(int i=1;i<len;i++)
	{
		int t=arr[i],k=i;
		for(int j=i-1;j>=0&&arr[j]>t;j--)
		{
			arr[j+1]=arr[j];
			k=j;
			
		}
		arr[k]=t;
	}
}
//选择排序（冒泡的变种，失去了对数据的敏感性，提高了速度）
void select_sort(int* arr,size_t len)
{
	for(int i=len-1;i>0;i--)
	{
		int max=i;
		for(int j=0;j<i;j++)
		{
			if(arr[j]>arr[max])
				max=j;
		}
		if(i!=max)
		{
			swap(&arr[max],&arr[i]);
		}
	}
}
//快速排序 （使用了二分法，平均速度最快的排序）
void _quick_sort(int* arr,size_t left,size_t right)
{
	if(left>=right)return;
	//计算标杆下标
	int pi=(left+right)/2;
	//备份标杆的值
	int pv=arr[pi];
	//备份左右下标
	int l=left,r=right;
	//左右相遇时结束
	while(l<r)
	{//在标杆左边寻找比它大的数据
		while(arr[l]<=pv && l<pi) l++;
		if(l<pi)//如果没有超出范围，说明找到比标杆大的值
		{
			arr[pi]=arr[l];
			pi=l;
		}
		while(pi<r && arr[r]>=pv) r--;
		if(r>pi)
		{
			arr[pi]=arr[r];
			pi=r;
		}
	}
	arr[pi]=pv;
	if(pi-left>1)
	{
		_quick_sort(arr,left,pi-1);
	}
	if(right-pi>1)
	{
		_quick_sort(arr,pi+1,right);
	}
}

void quick_sort(int* arr,size_t len)
{
	_quick_sort(arr,0,len-1);	
}
void show_arr(int* arr,size_t len)
{
	for(int i=0;i<len;i++)
	{
		printf("%d ",arr[i]);
	}
	printf("\n");
}
//堆排序
void creat_heap(int* arr,size_t root,size_t len)
{
	if(len<root) return;
	int left=root*2+1;
	int right=root*2+2;
	creat_heap(arr,left,len);
	creat_heap(arr,right,len);
	int max=root;
	if(left<len)
	{
		if(arr[left]>arr[max])
		{
			max=left;
		}
	}
	if(right<len)
	{
		if(arr[right]>arr[max])
		{
			max=right;
		}
	}
	if(max!=root)
	{
		swap(&arr[max],&arr[root]);
	}
}
void heap_sort(int* arr,size_t len)
{
	for(int i=0;i<len;i++)
	{
		creat_heap(arr,0,len-i);
		swap(&arr[0],&arr[len-1-i]);
	}
}
//归并排序(外部合并)（不用进行数据间的交换）
void merge(int* arr,size_t left,size_t pi,size_t right,int* temp)
{
	int i=left,j=pi+1,k=left;
	while(i<=pi && j<=right)
	{
		if(arr[i]< arr[j])
			temp[k++]=arr[i++];
		else
			temp[k++]=arr[j++];
	}
	while(i<=pi) temp[k++]=arr[i++];
	while(j<=right)temp[k++]=arr[j++];
	for(int i=left;i<=right;i++)
	{
		arr[i]=temp[i];
	}
}
void _merge_sort(int* arr,size_t left,size_t right,int* temp)
{
	if(left>=right)return;
	int pi=(left+right)/2;
	_merge_sort(arr,left,pi,temp);
	_merge_sort(arr,pi+1,right,temp);
	merge(arr,left,pi,right,temp);
}
void merge_sort(int* arr,size_t len)
{
	int temp[len];
	_merge_sort(arr,0,len-1,temp);
}
int main()
{
	int arr[]={1,7,2,5,4,35,86,78};
	merge_sort(arr,8);
	show_sort(arr,8);
	
}