数据结构 ——— 直接选择排序算法的实现

目录

直接选择排序算法的思想

优化直接选择排序算法的思想

代码实现（默认升序） 

直接选择排序算法的思想

直接选择排序算法的思想类似与直接插入排序
区别在于从大到小选择最小的元素或者最大的元素直接放在元素应该停留的位置
每次从待排序的元素中选出最小或者最大的元素（根据降序或者升序选择）
存放在序列的起始位置，直到全部待排序的数据元素排完为止

优化直接选择排序算法的思想

优化前：

每次从待排序的元素中选出最小或者最大的元素，存放到应该停留的位置，再次选出次大或者次小的数，存放到应该停留的位置，这样做的话每次只能选出一个元素

优化后：

而可以优化的是每次在待排序的元素中选出最大和最小的两个元素，放在各自最后应该停留的位置
再选出次大和次小的元素，放在最后改停留的位置

代码实现（默认升序）

代码演示：

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

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

	while (left < right)
	{
		int min = left;
		int max = right;

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

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

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

		if (max == left)
		{
			max = min;
		}

		Swap(&a[right], &a[max]);

		left++;
		right--;
	}
}

代码解析：

left 表示数组首元素的下标，right 表示数组尾元素的下标
以排成升序为例
找到数组中最小的元素时就放在下标为 left 的元素处
注意：这里的放入不是直接覆盖首元素，而是和首元素交换
且找到数组中最大的元素时就放在下标为 right 的元素处，同样是交换
再找到数组中次小的元素和次大的元素进行交换………………
每交换一对元素，那么 left 就递增 1 ，而 right 就递减 1
直到 left == right 时，说明所有元素都停留再了最后应该停留的位置
这时的数组就是升序

min 是数组中最小元素的下标，而 max 是数组中最大元素的下标
再通过 left 和 right 为数组的区间来遍历数组，找到最小元素的下标赋值给 min ，找到最大元素的下标赋值给 max
这样做的原因是：因为最开始 left 是 0 ，right 是 size-1，找到了最小和最大的元素后，放在了首尾位置，那么数组首尾位置就不用再遍历了，而且刚好 left 递增了 1，right 递减了 1，如果找到了次大的元素和次小的元素时同样如此，所以用 left 和 right 控制数组的区间刚好合适

找到最小元素的下标 min 时，和首元素的下标 left 交换
找到最大元素的下标 max 时，和尾元素的下标 right 交换
交换时需要注意一种情况，因为是先把最小的元素交换到数组首元素的位置
当如果首元素就是最大的元素时，就会出问题，因为这时的 max 就在首元素的位置
但是已经把最小的元素交换到这里了，而 max 的位置没有更新，那么如果再交换最大元素和尾元素时，就会发生错乱，就会把最小的元素，交换到尾元素去，这样就不能实现升序了
改正的办法是判断 max 是否和 left 相同，如果相同的话，就更新 max 的位置
因为最开始 min 和 left 交换了，所以此时最大的元素就在 min 处，直接把 min 赋值给 max 即可

代码验证：