【初阶数据结构】冒泡排序和选择排序（用C语言实现，主要讲思维）-2. 选择排序

老规矩（以升序为例），先上动图：

2.1 算法思想

选择排序的单趟排序是选择待排序数组中最小的数，将它与待排序数组中的开头的位置的数交换位置。这样单趟排序就完成了。

接下来讲一下完整的选择排序，可以看到的是每当我们完成了一个选择排序算法的单趟排序是将待排序的数组中最小的数放到正确的位置上。直到最后只剩最后一个数字时，排序终止。

2.2 选择排序的代码实现

选择排序算法的第一种写法：

void SelectSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int mini = a[i];
		for (int j = i; j < n; j++)
		{
			if (a[mini] > a[j])
			{
				mini = j;
			}
		}
		Swap(&a[mini],&a[i]);
	}
	
}

选择排序算法的第二种写法：

void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;
	int maxi = 0, mini = 0;


	while (left < right)
	{
		for (int i = left; i <= right; i++)
		{
			if (a[maxi] < a[i])
			{
				maxi = i;
			}

			if (a[mini] > a[i])
			{
				mini = i;
			}

		}

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

		if (left == maxi)
		{
			maxi = mini;
		}
		Swap(&a[right], &a[maxi]);

		left++;
		right--;
	}
	
}

上面的写法比较难以理解，如果实在理解不了的话，第一种写法也是可以的。因为这两种写法的效率是差不多的，时间复杂度都为O(N^2)。