数据结构-排序

void InsertSort(int* arr, int n)
{
	//控制整个数组需要比较的次数
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		//控制一个数据要比较的次数
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

void ShellSort(int* arr, int n)
{
	int gap = n;
	//预排序的次数+直接插入排序
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//控制整个数组需要比较的次数
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			//控制一个数据要比较的次数
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n-1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin+1; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		//如果起始位置就是最大值时
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&arr[mini], &arr[begin]);
		Swap(&arr[maxi], &arr[end]);

		begin++;
		end--;
	}
}

//hoare版本
int FindKey(int* arr, int left, int right)
{
	int key = left;
	left++;
	//=是为了解决特殊情况：left与right相遇位置的值要比基准点的值大，如果此时结束循环交换基准点与right的值
	//就会导致左边的值不满足都比基准点小
	while (left <= right)
	{
		//left：从左往右找比基准值大的值
		while(left <= right && arr[left] < arr[key])
		{
			left++;
		}
		//right：从右往左找比基准值小的值
		while(left <= right && arr[right] > arr[key])
		{
			right--;
		}
		//交换此时的left和right的值
		if(left <= right)
		{
			Swap(&arr[left++], &arr[right++]);
		}
	}
	//将基准点与此时right位置的值进行交换，使其放在合适的位置
	Swap(&arr[key], &arr[right]);
	return right;
}

void QuickSort(int* arr, int left, int right)
{
	//递归停止的条件
	if (left >= right)
	{
		return;
	}
	int keyi = FindKey2(arr, left, right);
	//将一个数组分成多个数组进行排序
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}

int FindKey2(int* arr, int left, int right)
{
	int key = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		//从左往右找比基准值小的值
		if (arr[cur] < arr[key] && ++prev != cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[prev], &arr[key]);
	return prev;
}

void QuickSort3(int* arr, int left, int right)
{
	//递归停止的条件
	if (left >= right)
	{
		return;
	}
	
	//三路划分
	//主要针对于数组中有大量与基准值相同的值或数组的值全部一样
	//正常使用会比hoare和前后指针法效率低一些
	int begin = left;
	int end = right;
	int key = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[key])
		{
			Swap(&arr[cur], &arr[left]);
			cur++;
			left++;
		}
		else if (arr[cur] > arr[key])
		{
			Swap(&arr[cur], &arr[right]);
			right--;//因为不知道交换过来的值是否比基准值大还是小，故cur不动
		}
		//遇到和基准值相等的值
		else
		{
			cur++;
		}
	}
	//[begin left-1] [left right] [right+1 end]
	//将一个数组分成多个数组进行排序
	QuickSort(arr, begin, left-1);
	QuickSort(arr, right+1, end);
}

void QuickSort2(int* arr, int left, int right)
{
	//用栈来实现非递归方式的快速排序
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);
	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);

		int end = STTop(&st);
		STPop(&st);

		//把基准值放在合适的位置
		int keyi = FindKey2(arr, begin, end);

		//判断新的数组是否符合标准
		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
		if (keyi+1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi+1);
		}
	}
	STDestory(&st);
}

void _MergeSort(int* arr, int left, int right, int* tmp)
{
	//分解

	//递归结束条件
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;
	//不断将数组拆分为两个区间：[left,mid] [mid+1,right]
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid+1, right, tmp);

	//合并
	//利用合并两个有序数组算法的思想
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;//不等于0是为了避免每次排序都从0开始
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else
		{
			tmp[index++] = arr[begin2++];
		}
	}
	//左序列的数没有排完
	//右序列的数没有排完
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}

	//将临时数组排好序的数传入原数组中
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}

void MergeSort(int* arr, int n)
{
	//利用合并两个有序数组算法的思想
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}

void MergeSort2(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}

	int gap = 1;//定义gap表示此时每个数组有几个数据
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int index = begin1;
			//若数组长度为奇数
			if (begin2 >= n)
			{
				break;//表示没有右序列
			}
			if (end2 >= n)
			{
				end2 = n - 1;//表示此数组数据个数未满gap个
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[index++] = arr[begin1++];
				}
				else
				{
					tmp[index++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[index++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = arr[begin2++];
			}
			//注意！！！
			for (int j = i; j <=end2; j++)
			{
				arr[j] = tmp[j];
			}
		}
		gap =gap * 2;//两两合并，故×2
	}
	free(tmp);
	tmp = NULL;
}

void CountSort(int* arr, int n)
{
	int min = 0;
	int max = 0;
	for (int i = 0; i < n; i++)
	{
		if (arr[i] < min)
		{
			min = arr[i];
		}
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	//得到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);
	//将arr各个数出现的次数存入count数组中
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}
	int index = 0;
	//将count中存入的数据转化为原数据存入到arr数组中
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;
		}
	}
}