【排序算法（一）】——插入排序，选择排序 —＞深层解析

星辰与你

发布于 2024-10-17 19:38:31

1110

发布于 2024-10-17 19:38:31

文章被收录于专栏：学习

前言

排序，就是使用一串记录，按照其中的某个或某些关键字的大小，递增或者递减的排序起来的一系列操作。 排序算法有着广泛的应用，因为有序的数据通常能够更高效地查找、分析和处理。

排序算法大致可以分为以下几种：

一、排序算法评价维度

运行效率：我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（时间复杂度中的常数项变小）。对于较大的数据量的情况，运行效率显得尤为重要。 就地性：顾明思义，原地排序通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从节省内存。通过情况，原地排序的数据搬运操作较少时，运行速度也更快。 稳定性：稳定排序在完成排序后，相等的元素在数组中的相对顺序不发生变化。 自适应性：自适应排序的时间复杂度会受输入数据的影响，即最佳时间复杂度、最差时间复杂度、平均时间复杂度并不完全相同。 是否基于比较：基于比较的排序依赖比较运算符（< 、= 、>）来判断元素的相对顺序，从而排序整个数组，理论最优时间复杂度为O(n * log n)。而非比较不使用比较运算符，时间复杂度可以达到O(n)，但其通用性相对较差。

现在来学习各种排序算法，并基于上述各种评价维度对各个算法的优缺点进行分析。

二、插入排序

2.1、直接插入排序

2.1.1、插入排序分析及代码实现

直接插入排序，当插入第i(i>=1)个元素，前面的数据已经有序，此时用arr[ i ]的数据与arr[ i - 1 ]，arr[ i - 2 ]，arr[ i - 3 ]，直到第一个数据，找到插入位置就将arr[ i ] 插入，原来位置上的元素顺序后移。

如上图所示，插入排序的过程，现在就来使用代码实现一下。

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		while (end >= 0)
		{
			if (arr[end] > arr[end + 1])
			{
				Swap(&arr[end], &arr[end + 1]);
				end--;
			}
			else
			{
				break;
			}
		}
	}
}

这里也可以不使用交换函数，将arr[end+1]的值存起来，直接将end位置的值赋给end+1。

代码如下：

void InsertSort1(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end+1] = tmp;
	}
}

2.1.2、插入排序时间复杂度分析

最优情况： 数组已经有序为升序（这里排序为升序），此时只需要进行n次循环比较，时间复杂度为O(n)。 平均情况： 平均情况下，时间复杂度为O(n^2)，这里数组的每一个数据都需要与排序好的数据进行多次比较，平均下来一个数据比较n/2次，需要循环n次，时间复杂度就为O(n^2)。 最差情况： 最差情况就是数据有序为降序（我们要排序为升序），此时每一个数据都需要与已经排序完的数据一一进行比较并交换，时间复杂度为O(n^2)。

2.1.3、直接插入排序的优化

直接插入排序算法复杂度为O(n^2)，效率并不高，这里对其进行优化。

直接插入排序优化，可以将数组数据进行分组，先让部分数据有序，再逐渐减少每一组数据的个数，直到为1。

2.2、希尔排序

希尔排序，就是对直接插入排序的优化；

希尔排序又称缩小增量法。希尔排序的基本思想：

选定一个整数（通常情况下gap = n / 3 +1），把待排序数据分成各组，所以的距离相等的记录分别在同一组内，对每一组数据进行排序，然后gap = gap / 3 +1得到下一个整数，继续将数组分成各组，进行插入排序，当gap = 1 时，就相当于直接插入排序（但是此时，数组已经基本有序）。

代码实现：

//希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n -gap; i++)
		{
			int end = i;
			while (end >= 0)
			{
				if (arr[end] > arr[end + gap])
				{
					Swap(&arr[end], &arr[end + gap]);
					end = end - gap;
				}
				else
				{
					break;
				}
			}
		}
	}
}

希尔排序时间复杂度：

内层循环

这里因为gap的取值不一样，（可以取2、3.......），希尔排序的算法复杂度就很难计算。

外层循环

这里外层循环复杂度取决于gap的取值，时间复杂度O(log2 n)或者(log3 n）时间复杂度可以表示为O(log n)。

对于希尔排序算法的时间复杂度，计算十分复杂

三、选择排序

选择排序的基本思想：

每一次从待排序的数据元素中选出最大（或者最小）的一个元素，存放在序列的其实位置，直到数组所有元素排序完。

3.1、直接选择排序

这里可以选最大的数据，放到数组末尾；也可以选最小的，放到数组开头。如下图所示：

这里只找最大或者最小的效率有点低，我们两个一起找。

这里两个一起找，就要注意，当找到最大值的小标maxi与left（排序左区间）相等时，我就要另加判断（因为需要将left的数据与最小值mini进行交换）。

//直接选择排序
void SelectSort(int* arr, int n)
{
	int mini = 0, maxi = 0;
	int left = 0, right = n - 1;
	while (left < right)
	{
		for (int i = left; i < right; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		if (maxi == left)
		{
			maxi = mini;
		}
		Swap(&arr[mini], &arr[left]);
		Swap(&arr[maxi], &arr[right]);
		left++;
		right--;
	}
}

3.2、堆排序

在之前，数据结构堆中，提到了堆排序，这里实现堆排序就是利用堆的这种思维，这里使用堆排序前提数据是堆结构（所以这里就需要先堆数组进行建堆操作）。

在每次将堆顶数据与堆最后一个数据交换，再向下调整后，不将这个数据删除，而是留着堆的末尾；接下来接着让第一个数据与倒数第二个数据交换，再向下调整；直到调整完堆里的全部数据。

代码实现：

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向下调整算法
void AdjustDown(int* arr, int parent, int n)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child< n - 1 && arr[child]>arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else {
			break;
		}
	}
}
//堆排序
void HeapSort(int* arr, int n)
{
	//建堆
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}
	//堆排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}

堆排序的算法复杂度：O(n*log n)。