#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 10
 
Swap(int *p1, int * p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void Print(int *a)
{
	for (int i=0;i<N;i++)
	{
		printf("%d ",a[i]);
	}
}
void BubbleSort(int* a, int n)
{
	
	for (int j=0;j<n;++j)
	{
		int size = 0;
		for (int i=1;i<N-j;++i)
		{
			if (a[i-1]>a[i])
			{
				Swap(&a[i-1],&a[i]);
				size =1;
			}
		}
		if (size==0)
		{
			break;
		}
	}
}
int main()
{
	int a[N] = {0};
	for (int i=0;i<N;++i)
	{
		a[i] = rand();
	}
	BubbleSort(a,N);
	Print(a);
	
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//打印
void Print(int *a,int n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
}
//挖坑法
void QuickSort(int* a,int left,int right)//升序
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		int pivot = begin;//記錄坑位的下標
		int key = a[begin];//坑值
 
		while (begin < end)
		{
			//右邊找小，放到左邊
			while (begin < end && a[end] >= key)//與坑值比較
			{
				--end;
			}
			//小的放在左邊的坑里，自己形成了新的坑位
			a[pivot] = a[end];
			pivot = end;
 
			//左邊找大，放在右邊
			while (begin < end && a[begin] <= key)//與坑值比較
			{
				++begin;
			}
			//大的放在右邊的坑里，自己形成了新的坑位
			a[pivot] = a[begin];
			pivot = begin;
		}
		//最后將坑值給到坑位
		a[pivot] = key;
		//[left,right]
		//[left,pivot-1]  [pivot+1,right]
		//左子區(qū)間和右子區(qū)間有序，我們就有序了，如何讓他們有序？分治遞歸
		QuickSort(a, left, pivot - 1);
		QuickSort(a, pivot + 1, right);
	}
	else
	{
		return;
	}
}
int main()
{
	int a[10] = {0,9,5,6,3,2,1,7,8,4};
	//挖坑法
	QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);
    //打印
	Print(a,sizeof(a) / sizeof(a[0]));
	return 0;
}

int begin = left;
int end = right;
//使用三數取中選“坑值”，用mid存儲其下標
int mid = GetMidIndex(a, begin, end);
//將區(qū)間首值當作坑位
//坑值與首值交換，避免算法混亂
//一般我們會將區(qū)間首值作為坑值
Swap(&a[begin], &a[mid]);//傳地址調用
//存儲坑值
int key = a[begin];

int GetMidIndex(int *a,int left,int right)
{
    //二分
	int mid = (right - left) / 2;
	if (a[left]<a[mid])
	{
		if (a[left]<a[right])
		{
			if (a[mid]<a[right])
			{
				return mid;
			}
			else  //a[mid]>=a[right]
			{
				return right;
			}
		}
		else   //a[left]>=a[right]
		{
			return left;
		}
	}
	else  //a[left]>=a[mid]
	{
		if (a[mid]<a[right])
		{
			if (a[left]<a[right])
			{
				return left;
			}
			else  //a[left]>=a[right]
			{
				return right;
			}
		}
		else  //a[mid]>=a[right]
		{
			return mid;
		}
	}
}

//交換
void Swap(int* p1, int*p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//區(qū)間[left,right]
//左區(qū)間[left,pivot-1]  右區(qū)間[pivot+1,right]
//左子區(qū)間和右子區(qū)間有序，我們就有序了，如何讓他們有序？分治遞歸
// 小區(qū)間優(yōu)化
if (pivot - 1 - left > 10)//對當待處理數據大于于10的子序列進行快排遞歸排序
{
	//快排
	QuickSort(a,left,pivot-1);
}
else
{
	//采用直接插入排序，對當待處理數據低于10的子序列進行排序，避免遞歸
	InsertSort(a+left,pivot-1-left+1);//為什么最后要加1,例如：區(qū)間[0,9]實際上有10個數
}
 
if (right - (pivot + 1) > 10)
{
	QuickSort(a,pivot+1,right);
}
else
{
	InsertSort(a + pivot+1, right-(pivot+1)+1);
 
}

void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		//選坑位
		int mid = GetMidIndex(a, begin, end);//三數取中
		Swap(&a[begin], &a[mid]);
		int key = begin;
		while (begin < end)
		{
			while (begin < end && a[end] <= a[key])
				--end;
			while (begin < end && a[begin] >= a[key])
				++begin;
			Swap(&a[begin], &a[end]);
		}
		Swap(&a[begin], &a[key]);
		//分治遞歸
		QuickSort(a, left, begin - 1);
		QuickSort(a, begin + 1, right);
	}
}

//左右指針法
void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		//選坑位
		int mid = GetMidIndex(a, left,right);//三數取中
		Swap(&a[left], &a[mid]);
		int key = left;
		//初始化指向
		int prev = left, cur = left + 1;
		while (cur<=right)
		{
			if (a[cur] <= a[key])//&&++prev!=cur
			{
				++prev;
				//避免無效操作
				if(cur!=prev)
				Swap(&a[prev],&a[cur]);
			}
			++cur;
		}
		Swap(&a[key], &a[prev]);
		//分治遞歸
		QuickSort(a, left, prev - 1);
		QuickSort(a, prev + 1, right);
	}
}