当前位置：网站首页>选择排序—直接选择排序和堆排序

选择排序—直接选择排序和堆排序

2022-08-01 06:36:00 【Fan~Fan】

一、直接选择排序

基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
动态演示：
实现思路：
选择排序的实现比较简单，其就是依次遍历数组，找出最小或者最大的元素与最前面或者最后面元素进行交换，然后遍历剩下的数据，再找再换，直到遍历完毕。
排序优化：
对于传统选择排序，我们每次只找最大或者最小的进行排序，这样有点浪费时间，为了提高效率，我们可以每次选出最大的和最小的，最小的放前面，最大的放后面，不断缩小区间，直到完成排序。
存在缺陷：
提高了效率的同时也可能会带来风险，比如我们要对数组arr[5]={9,1,2,5,7}进行排序。
第一次遍历我们得到最大元素为a[0],最小元素为a[1],最小元素要放在最左边，所以a[0]与a[1]进行交换，此时a[0]位置放的是元素1，为最小元素符合排序。但此时最大元素要放在最右边，最大元素为9，我们记录的是a[0]位置，但此时a[0]位置元素已不是9，所以这就导致排序失败，出现这种重叠情况，我们需要修正下max。
代码演示：
void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

//直接选择排序
void SelectSort(int* a, int n)
{
	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int mini = left, maxi = left;
		for (int i = left + 1; i <= right; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;//遍历数组找出最小值下标
			}
			if (a[i] > a[maxi])
			{
				maxi = i;//遍历数组找出最大值下标
			}
		}
		//升序小值放左，大值放右
		Swap(&a[left], &a[mini]);
		//如果left和maxi重叠,修正maxi
		if (left == maxi)
		{
			maxi = mini;
		}
		Swap(&a[right], &a[maxi]);
		//交换完缩小区间
		left++;
		right--;
	}
}