117.【C语言】数据结构之排序(选择排序)

1.知识回顾

2.分析

设想的思路

代码

执行结果

编辑

错误排查和修复

详细分析出错点

执行结果

3.正确的思路

4.其他问题

1.知识回顾

参见42.5【C语言】选择排序代码点我跳转

2.分析

知识回顾里所提到的文章的选择排序一次循环只比一个数字,和本文接下来要讲的选择排序有所不同,可以一次循环比较两个数字

如果要比较两个数字,那么就要定义两个下标:left和right,

设想的思路

例如排升序,对于一个无序数组而言,

①每次循环遍历数组,找到最大值和最小值的下标.

②将最小值和数组的第一个元素的值互换,最大值和数组的最后一个元素的值互换.

③left++,right--.

④缩小区间,跳到①执行直到left>=right退出循环,完成选择排序.

示意图:

设想的思路是否正确?有无需要改正的地方?

回答在错误排查和修复里讲了

代码

实现下设想思路的代码

Sort.c写入

void SelectSort(int* arr, int n)
{
	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int max_i = left;//max_i为最大元素对应的下标,赋的初始值没有严格要求
		int min_i = left;//min_i为最小元素对应的下标,赋的初始值没有严格要求

		//遍历数组,查最大元素和最小元素对应的下标
		for (int i = left+1; i <= right; i++)//注意i循环的区间!
		{
			if (arr[i] > arr[max_i])
			{
				max_i = i;
			}
			if (arr[i] < arr[min_i])
			{
				min_i = i;
			}
		}
		Swap(&arr[left], &arr[min_i]);
		Swap(&arr[right], &arr[max_i]);
		left++;
		right--;
	}
}

main.c写入

#include "Sort.h"
int main()
{
	int arr[] = { 3,5,1,6,2,3,7,9,0,8 };
	printf("排序前:");
	PrintArray(arr, sizeof(arr) / sizeof(arr[0]));
	SelectSort(arr,sizeof(arr)/sizeof(arr[0]));
	printf("排序后:");
	PrintArray(arr, sizeof(arr) / sizeof(arr[0]));
	return 0;
}

给定数组int arr[]={3,5,1,6,2,3,7,9,0,8}对其使用选择排序

执行结果

选择排序出了问题,"3 5 6 3"并非升序,看来设想的思路是有问题的

错误排查和修复

下断点调试,执行到产生错误之前的状态

-->-->-->-->(问题出在后两步)

即{0,1,2,6,5,3,3,7,8,9}(结束后,下一次循环max_i==,min_i==3)-->{0,1,2,3,5,6,3,7,8,9}

详细分析出错点

从下图的状态开始分析,后面开始单步执行

i从4开始循环,arr[left]恰存储着最大值,最终出循环时,min_i==5,max_i==3,画图可表示为

执行Swap(&arr[left], &arr[min_i])会导致最大值的位置被改变但max_i的下标并没有跟着变,从而导致下一步交换出现问题Swap(&arr[right], &arr[max_i])

因此在下一步交换前先进行判断,如果最大值出现在最左侧(即left==max_i,下标重叠),应该修改max_i的下标

则部分代码改为:

		Swap(&arr[left], &arr[min_i]);
		if (left == max_i)
		{
			max_i = min_i;
		}
		Swap(&arr[right], &arr[max_i]);

这样第一次交换的结果不会影响第二次交换(因此后续的right==min_i不用判断)

执行结果

3.正确的思路

排升序

①每次循环遍历数组,找到最大值和最小值的下标.

②将最小值和数组的第一个元素的值互换,如果出现left等于最大值的下标,应该将最大值的下标赋值为最小值的下标,最大值和数组的最后一个元素的值互换.

③left++,right--.

④缩小区间,跳到①执行直到left>=right退出循环,完成选择排序.