当前位置：首页 > article >正文

排序算法 —— 直接选择排序

article 2024/10/26 17:24:57

1.直接选择排序思想

2.直接选择排序实现

3.直接选择排序总结

1.直接选择排序思想

思想：每次从剩余的待排序序列中选出最小or最大的元素，放在正确的位置，当把最后一个元素也放在正确的位置的时候，排序完成。

步骤如下：

在元素集合array[i] ~ array[n-1]中选择关键码最大(小)的数据元素。
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个(第一个)元素交换。
在剩余的array[i] ~ array[n-2]（array[i+1] ~ array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

2.直接选择排序实现

#include <stdio.h>

void swap(int* p1, int *p2)
{
	int t = *p1;
	*p1 = *p2;
	*p2 = t;
}

void SelectSort(int *nums, int n)
{
	int i = 0;
	for(i = 0; i < n; ++i) // 枚举起始元素 
	{
		int j = 0;
		int min_i = i;     // 记录最小元素的下标
		 
		// 从起始区间开始寻找最小元素的下标 
		for(j = i; j < n; ++j) 
		{
			min_i = nums[min_i] < nums[j] ? min_i : j;
		}
		swap(&nums[min_i], &nums[i]);
	}
}


int main()
{
	int nums[] = {5,4,8,9,6,3,2,1,7,0};
	
	SelectSort(nums,10);
	
	int i = 0;
	while(i < sizeof(nums) / sizeof(int))
	{
		printf("%d ",nums[i]);
		i++;
	}
	
	return 0;
}

需要注意的是：

我们每次寻找的并不是最小的元素，而是最小元素的下标。

代码优化：上面的代码中，在选择元素的时候，我们每次遍历剩余数据，都只能选出一个最小的数据，然后放在正确的位置上；其实我们不仅仅可以在遍历的时候，选出最小的元素，还能够选出最大的元素，把小的元素从左往右放入正确位置，把大的元素从右到左放入正确位置。

优化后的代码如下：

void swap(int* p1, int *p2)
{
	int t = *p1;
	*p1 = *p2;
	*p2 = t;
}

// 时间复杂度：O(N^2)
void SelectSort(int* nums, int n)
{
	int left = 0, right = n - 1;

	while (left < right)
	{
		// [left, right]
		int min_i = left, max_i = left;
		for (int i = left; i <= right; i++)
		{
			if (nums[i] > nums[max_i])
			{
				max_i = i;
			}

			if (nums[i] < nums[min_i])
			{
				min_i = i;
			}
		}

		swap(&nums[left], &nums[min_i]);
		// max如果被换走了，修正一下
		if (max_i == left)
		{
			max_i = min_i;
		}

		swap(&nums[right], &nums[max_i]);

		++left;
		--right;
	}
}