【排序】插入排序与选择排序详解

📝选择排序是什么？

选择排序是一种简单直观的排序算法。它的工作原理如下：在未排序序列中找到最小(大)元素,交换到起始位置,该元素为已排序序列的起始元素，继续在剩余未排序元素中找到最小(大)元素,交换到未排序序列起始位置，重复第二步,直到所有元素均排序完毕。

🌠选择排序思路

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

简单来说：就是在每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

🌉 直接选择排序

例如：定义一个数组 int a[6] = { 9,5,7,2,3,6 };

1. 首先：遍历第一趟数组，找出数组的最小值，与第一个数据交换

1. 然后遍历第二趟数组，继续找出最小值，与第二个数据交换

1. 然后遍历第三趟数组，继续找出最小值，与第三个数据交换

如此重复，然后当i等于n-1次选择时排完序，最后一个也有序，排序完成。

… 代码： 上方观察： 选择要找几次? 6个数，一次选择1个，然后有序，第五次选择，5个都有序，最后一个有序。 n个数，选择n-1次，最后一个自然有序。 第一趟选择，下标范围是[0 ~ n-1] 第一趟选择，下标范围是[1 ~ n-1] 第一趟选择，下标范围是[2 ~ n-1] . . .

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

 void SelectSort(int*arr,int n) 
 {

	for (int i = 0; i < n - 1; i++)//从0开始选，选到n-2次 
	{
		int mini = i;//设最小值是第1位
		for (int j = i + 1; j < n; j++)//首次从1开始到n-1每次比较 
		{								//查找是否有比最小值小的
			mini = arr[j] < arr[mini] ? j : mini;
			
		}

		Swap(&arr[i], &arr[mini]);
	}
}

思路总结： 在一个有n个元素中，进行排序，下标范围是0 ~ n-1，然后我们要在0 ~ n-1，中找到最小的数与0下标的数进行交换，接着在1 ~ n - 1下标中找最小值与1下标交换，然后下次就是2 ~ n - 1找最小值与2交换，每次找到最小值丢到最前面，接着交换，随即下标3,4，5…直到n - 1次选择都排完序，前n-1之前有序了，最后一个也有序。

特性总结：

时间复杂度: 外层for循环从0到n-2,共执行n-1次。内层for循环每次从i+1到n,共执行n-i-1次。所以总时间复杂度为:T(n) = Σ(n-1)(n-i-1) = Θ(n^2)选择排序的时间复杂度是O(n ^ 2)。 空间复杂度: 该算法只使用了一个临时变量mini来记录每次循环找到的最小元素的下标。且不需要额外的数组空间。所以空间复杂度为O(1)。

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

🌠选择排序优化

🌠优化方法

以上算法是每次找出最小的值放在指定位置，一共要找n-1次。如果我们每次不仅找到最小的值，还找到最大的值，将最小的与左端交换，最大的与右端交换，那么就少了一半的遍历次数，从而提高效率。

1. 变量begin和变量end是数组的两端，Min和Max在0位置，min和max分别找小和大的下标，i=begin+1,让begin+1到end的数都与begin比较。

1. 先交换min与begin位置的数值，再交换max与end位置的数值

1. begin右移，end左移，继续找大找小，继续交换

1. 重复上述操作，直到遍历完所有数组

🌉排序优化后问题

若是max的位置与begin重合,则先让begin与min的位置交换,此时原max位置上的最大值已经被交换走,如果直接让end与现max位置交换,交换的值将是错误的。

1. 当max与begin重合时，min在最小值位置

1. begin先与min的位置交换数据，此时max位置的已经不是最大值了

1. 当max再与end位置交换数据，排序就会出错

解决方法：

当max与begin重合时,先让begin与min交换,此时max原指向的最大值位置已改变,应对max进行修正,让其重新指向数组中真正的最大值位置。然后才能完成end与新max位置元素的交换。

1. 当max与begin重合，并且begin此时完成了交换，此时最大值已经交换到了min所指向的位置

1. 修改max，让max来到min位置

1. 然后再让max与end交换

代码实现：

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{

		int mini = begin, maxi = begin;
		//选出最小值和最大值的位置
		for (size_t i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

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

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

		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

🌠选择排序效率特性

时间复杂度：O(N^2) 空间复杂度：O(1) 稳定性：不稳定

🌉插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：**把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。**实际中我们玩扑克牌时，就用了插入排序的思想

如动图：

步骤：

1. 从第一个元素开始,该元素可以认为已经被排序
2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

通过不断地将当前元素插入到已经排好序的有序序列中,直到全部元素排完,即完成整个排序过程。

🌠插入排序实现

思路：第一个数天然有序，第二个数与代排有序序列第一个比较，小与插入，第三个数与前面两个元素比较，依次比较前面元素，然后比较完依次将后面元素依次插入到前面有序序列中，直到序列停止。

代码如下：

void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		//[0,end]  end+1
		 //end记录当前要插入的元素位置 
		 //end+1就是待插入元素的下标
		int end = i; 
		int temp = arr[end + 1];//temp临时存储arr[end+1]这个待插入元素
		while (end >= 0)
		{
			//如果temp小于arr[end],说明待插入元素应该插入在这个位置
			//将元素后移一位
			if (temp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			//否则直接跳出循环
			else
			{
				break;
			}
		}
		//将待插入元素插入到正确位置
		arr[end + 1] = temp;
	}
}

时间复杂度： 最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序 最好情况下为O(N)，此时待排序列为升序，或者说接近升序。 元素集合越接近有序，直接插入排序算法的时间效率越高 空间复杂度：O(1)，它是一种稳定的排序算法