【数据结构】排序（1）插入排序、选择排序

void InsertSort(int array[], int size)
{
	for (int i = 1; i < size; ++i) // 依次获取到array数组中的每个元素进行插入
	{
		// 单个元素的插入过程
		int key = array[i];
		int end = i - 1;
 
		// 找待插入元素在array中的位置
		while (end >= 0 && key < array[end])
		{
			array[end + 1] = array[end];
			end--;
		}
 
		// 插入key
		array[end + 1] = key;
	}
}

2.希尔排序( 缩小增量排序 )

       面试中遇到的数据集合：数据都比较杂乱，或者数据量都比较大；面试官说在该场景下仍需要你使用插入排序的思想

1.直接选择排序

void SelectSort(int array[], int size)
{
	for (int i = 0; i < size - 1; ++i) // 控制循环的趟数
	{
		// 单趟选择的过程
		// 只需将区间中的元素遍历一遍，找到最大元素所在的位置
		int maxPos = 0;
		for (int j = 1; j < size - i; ++j)
		{
			if (array[j] > array[maxPos])
			{
				maxPos = j;
			}
		}
 
		// 因为排升序：最大元素应该将去放到区间的最后一个位置
		// 但是最后一个位置也是有数据的，此处只能将maxPos位置的最大数据和区间最后一个位置的数据进行交换
		if (maxPos != size - i - 1)
		{
			Swap(&array[maxPos], &array[size - 1 - i]);
		}
	}
}

选择排序缺陷：1.进行了一些重复性的比较

2.每次遍历只排一个

2.选择排序优化

直接选择排序中：单趟找到最大元素位置，然后将最大元素放到区间末尾，一趟只能排好一次元素

优化：一次遍历将最大元素往区间末尾放，最小元素放在起始位置，一次排好两个元素

// 选择的趟数减少了一半，但是元素的比较次数实际并没有减少

// 时间复杂度：O(N^2)

// 空间复杂度：O(1)

// 稳定性：不稳定

void SelectSortOP(int array[], int size)
{
	int begin = 0;
	int end = size - 1;
 
	while (begin < end)
	{
		int maxPos = begin;
		int minPos = begin;
		int index = begin + 1;
 
		// 在[begin, end]前中找到最大最小元素的位置
		while (index <= end)
		{
			if (array[index] > array[maxPos])
				maxPos = index;
 
			if (array[index] < array[minPos])
				minPos = index;
 
			++index;
		}
 
		// 将最大的元素往区间末尾存放
		if (maxPos != end)
		{
			Swap(&array[maxPos], &array[end]);
		}
 
		// 如果最小元素如果恰巧在end位置，上面的交换结束之后
		// 最小的元素的位置就发生了改变，此时必须要及时更新minPos
		if (minPos == end)
			minPos = maxPos;
 
		// 将最小的元素往区间起始位置存放
		if (minPos != begin)
		{
			Swap(&array[minPos], &array[begin]);
		}
 
		begin++;
		end--;
	}
}

3.堆排序

这里参考往期博客【数据结构】二叉树的顺序结构实现以及堆的实现应用

时间复杂度：O（NlogN）

空间复杂度：o（1）

稳定性：不稳定

使用场景：部分排序，或者与其他排序一起使用