void InsertSort(int* arr, int size)//直接插入排序
{
	for (int i = 0; i < size - 1; i++)
	{
		//單趟插入排序
		//基本思想：[0,end]區(qū)間值為有序
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;//在這里break出去再去賦值tmp是為了防止最后一次end = -1進不來賦值
			}
		}
		arr[end + 1] = tmp;
	}
}

void ShellSort(int* arr, int size)//希爾排序
{
	int gap = size;
	//多次預排+最后一次直接插入排序
	while (gap > 1)
	{
		gap = gap / 3 + 1;//控制最后一次進來gap為1進行直接插入排序
		for (int i = 0; i < size - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

void SelectSort(int* arr, int size)//優(yōu)化選擇排序
{
	int begin = 0;
	int end = size - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		Swap(&arr[mini], &arr[begin]);
		//如果maxi = begin，上一步交換了begin和mini的值，會影響maxi指向的值
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&arr[maxi], &arr[end]);
		begin++;
		end--;
	}
}

void BubbleSort(int* arr, int size)//冒泡排序
{
	for (int i = 1; i < size; i++)
	{
		int flag = 0;
		for (int j = 0; j < size - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				flag++;
			}
		}
		if (flag == 0)
		{
			break;
		}
	}
}

void _MergeSort(int* arr, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
	//遞歸找有序區(qū)間
	int mid = (end + begin) / 2;
	//[begin, mid][mid+1,end]
	_MergeSort(arr, begin, mid, tmp);
	_MergeSort(arr,mid + 1, end, tmp);
	//左右區(qū)間歸并有序
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			tmp[i++] = arr[begin1++];
		}
		else
		{
			tmp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	//輔助數(shù)組tmp中數(shù)據(jù)返回拷貝到原數(shù)組
	memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* arr, int size)//歸并排序
{
	int* tmp = (int*)malloc(sizeof(int) * size);
	if (tmp == NULL)
	{
		perror("malloc:fail");
		exit(-1);
	}
	int begin = 0;
	int end = size - 1;
	_MergeSort(arr, begin, end, tmp);
}

//計數(shù)排序只適用于范圍集中且重復數(shù)據(jù)較高的數(shù)據(jù)
void CountSort(int* arr, int size)//計數(shù)排序
{
	int min = arr[0];
	int max = arr[0];
	for (int i = 1; i < size; i++)
	{
		if (arr[i] < min)
		{
			min = arr[i];
		}
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	//計數(shù)數(shù)組count
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc:fail");
		exit(-1);
	}
	memset(count, 0, sizeof(int) * range);
	//開始計數(shù)
	for (int i = 0; i < size; i++)
	{
		count[arr[i] - min]++;
	}
	//回寫排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[j++] = i + min;
		}
	}
}