1.选择排序

直接遍历数组,找出最大值和最小值,记录下标,将最大值和最小值分别与首位交换

但是由于当begin == maxi时,会导致出错,因此需要 if 特殊判断

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
        //选出最大最小值的位置
		int maxi = end;
		int mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[end] < a[i])
			{
				maxi = i;
			}

			if (a[begin] > a[i])
			{
				mini = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
	
}

2.快速排序

快速排序是一种基于二叉树结构的排序

首先将数组的开头作为关键字key,

并设置左右指针left 和 right 分别从头尾开始寻找比key的值大和小的数,(right先走,left后走)

并将二者交换,直到left >= right,

并将key与 left 和 right 所指向的值(比key小)交换,

注:相遇位置一定比key小

原因:

1.L遇到R:R先走,R在比key小的位置停下,L没有找到比key大的数,L与R就会相遇,相遇位置就比key小

2.R遇到L:

(1).第一轮交换过后先交换了则L位置的值一定小于key,R的位置一定大于key,R继续走,找比key小的数,没找到,与L相遇,相遇位置就是L停的位置,一定比key小

(2).第一轮就没找到比key大的数,R与L相遇,此时L还没有开始走,则L在key的位置,相遇位置就是key的位置

这样key的左边就全是比他小的数,key的右边就全是比key大的数,

即key的位置放对了,

之后将数组以已经放好的key为边界分割

进行递归,直到所有递归完成,每一部分都只剩一个节点,就完成了

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	
	int begin = left, end = right;

	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] > a[keyi])
		{
			right--;
		}

		while (a[left] < a[keyi] && left < right)
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);

	keyi = left;

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}