数据结构——排序（插入排序）

目录

一、插入排序

二、直接插入排序

基本概念：

工作原理：

示例：

    代码实现

三、希尔排序

（一）基本概念

（二）工作原理

（三）示例

（四）代码实现

一、插入排序

插入排序是一种简单且直观的排序算法，在实际应用和算法学习中都具有重要地位。它主要分为直接插入排序和希尔排序两种形式，每种都有其独特的特点和应用场景。

二、直接插入排序

1. 基本概念：

   • 直接插入排序是一种简单的排序算法，它的基本思想是将一个未排序的数据元素逐个插入到已排好序的部分序列中，直到整个序列都变为有序。
   • 就像整理手中的扑克牌一样，每次拿到一张新牌，将其插入到已整理好的牌堆中的合适位置，使得牌堆始终保持有序。

2. 工作原理：

   • 从数组的第二个元素开始，将其视为待插入的元素。
   • 与已排好序的部分序列（通常是数组的前一个或前几个元素）进行比较，找到合适的位置插入该元素。
   • 重复这个过程，直到所有元素都被插入到正确的位置，此时数组就变为有序的了。

3. 示例：

   • 例如有数组 [5, 3, 8, 4, 2]。
   • 首先，认为第一个元素 5 是已排好序的部分序列。
   • 然后处理第二个元素 3，将 3 与 5 比较，发现 3 小于 5，将 3 插入到 5 的前面，此时数组变为 [3, 5, 8, 4, 2]。
   • 接着处理第三个元素 8，由于 8 大于已排好序部分序列的最后一个元素 5，所以直接将 8 放在合适位置，数组仍为 [3, 5, 8, 4, 2]。
   • 再处理第四个元素 4，将 4 与 8、5 依次比较，插入到 5 的后面，数组变为 [3, 4, 5, 8, 2]。
   • 最后处理第五个元素 2，经过比较插入到最前面，数组变为 [2, 3, 4, 5, 8]，排序完成。

    代码实现

InsertSort函数详解

1. 外层循环：

   • for (int i = 0; i < n - 1; ++i)循环遍历数组中除最后一个元素之外的所有元素。这个循环的作用是逐步扩大已排好序的部分序列。
   • 每次循环中，变量end被初始化为i，表示当前已排好序部分序列的最后一个位置。

2. 内层循环与插入操作：

   • int tmp = a[end + 1];将待插入的元素（即当前未排序部分的第一个元素）存储在tmp中。
   • while (end >= 0)开始一个内层循环，只要end不小于 0，就继续循环。这个循环的目的是在已排好序的部分序列中找到待插入元素的正确位置。
   • if (a[end] > tmp)如果当前已排好序部分的元素大于待插入元素，就将该元素向后移动一位，即a[end + 1] = a[end];，然后递减end继续比较前一个元素。
   • else当找到一个不大于tmp的位置或者遍历到数组的开头时，跳出循环。
   • a[end + 1] = tmp;将待插入元素插入到正确的位置。

void InsertSort(int* a, int n)
{
	// [0, end]有序  end+1位置的值插入[0, end]，让[0, end+1]有序
	//这个循环遍历数组中除最后一个元素之外的所有元素。
	for (int i = 0; i < n - 1; ++i)
	{
		int end = i ;
		int tmp = a[end + 1];
		while (end >=0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			//当找到一个不大于tmp的位置或者遍历到数组的开头时，跳出循环
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

三、希尔排序

（一）基本概念

希尔排序是对直接插入排序的改进，也称为缩小增量排序。它通过将数据分成若干个较小的子序列，对每个子序列进行插入排序，然后逐步减少子序列的数量和间隔，最终对整个序列进行一次直接插入排序，使得整个序列基本有序，从而提高排序效率。

（二）工作原理

1. 首先确定一个初始的间隔（增量），一般初始间隔可以取数组长度的一半。
2. 将数组按照间隔分成若干个子序列。例如，间隔为 3 时，对于数组 [1, 2, 3, 4, 5, 6, 7, 8, 9]，会分成 [1, 4, 7]、[2, 5, 8]、[3, 6, 9] 等子序列。
3. 对每个子序列分别进行直接插入排序。
4. 然后逐渐减小间隔，重复步骤 2 和 3，直到间隔减小到 1。此时，整个数组基本有序，再进行一次直接插入排序就可以得到完全有序的序列。

（三）示例

以数组 [9, 8, 7, 6, 5, 4, 3, 2, 1] 为例，初始间隔为 4：

• 第一轮，间隔为 4：
  • 子序列 [9, 5, 1]，进行插入排序后变为 [1, 5, 9]。
  • 子序列 [8, 4, 2]，排序后变为 [2, 4, 8]。
  • 子序列 [7, 3]，排序后变为 [3, 7]。
  • 子序列 [6] 不变。
  • 此时数组变为 [1, 2, 3, 6, 5, 4, 7, 8, 9]。
• 第二轮，间隔为 2：
  • 子序列 [1, 3, 5, 7, 9]，排序后变为 [1, 3, 5, 7, 9]。
  • 子序列 [2, 4, 6, 8]，排序后变为 [2, 4, 6, 8]。
  • 数组变为 [1, 2, 3, 4, 5, 6, 7, 8, 9]。
• 第三轮，间隔为 1，进行直接插入排序，此时数组已经基本有序，排序后仍为 [1, 2, 3, 4, 5, 6, 7, 8, 9]，排序完成。

（四）代码实现

主要步骤解释

1. 确定初始间隔并循环：

   • int gap = n;初始化间隔为数组的长度n。
   • while (gap > 1)循环条件确保在间隔大于 1 时进行预排序操作。每次循环都会将间隔逐渐缩小，直到间隔变为 1，此时进行直接插入排序以确保数组完全有序。

2. 设置间隔策略：

   • gap /= 2;这里采用了简单的间隔减半策略。也可以使用其他策略，如gap = gap / 3 + 1;以不同的方式调整间隔，不同的策略可能会影响算法的性能。

3. 多组数据同时预排序：

   • for (int i = 0; i < n - gap; ++i)外层循环遍历数组，从第一个元素开始，每次处理一组间隔为gap的数据。
   • int end = i;和int tmp = a[end + gap];与直接插入排序类似，保存当前待插入元素和其对应的索引。
   • while (end >= 0)内层循环在已处理的部分中找到待插入元素的正确位置。如果当前元素大于待插入元素，就将当前元素向后移动gap位，然后继续向前比较。当找到合适位置或遍历到数组开头时，跳出循环。
   • a[end + gap] = tmp;将待插入元素插入到正确的位置。

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap>1)//gap > 1时都是预排序,接近有序;gap == 1时就是直接插入排序 有序
	{
		gap /= 2; // logN,gap/2一定会最后除成1
		//gap = gap / 3 + 1;而gap/3不会，所以最后加个1；log3N 以3为底数的对数
		// gap很大时，下面预排序时间复杂度O(N)
		// gap很小时，数组已经很接近有序了，这时差不多也是(N)

		// 把间隔为gap的多组数据同时排，gap由大变小，
		//gap越大，大的数可以更快的排在后面，小的数可以更快的排在前面，gap越大，预排完越不接近有序
		//gap越小，越接近有序
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)//数组下标从0开始
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

四、两者比较

1. 排序思想有共通点：

   • 两者都是基于插入的思想进行排序。直接插入排序是将未排序的元素逐个插入到已排好序的部分中，而希尔排序也是通过不断地将元素插入到相对有序的子序列中，逐步使整个数组有序。
   • 在实现过程中，都有一个类似的内层循环用于寻找待插入元素的正确位置。在这个循环中，都是通过比较当前元素与待插入元素的大小，决定是否进行元素的移动。

2. 时间复杂度不同：

   • 直接插入排序在最坏情况下的时间复杂度为 ，对于小规模数据或基本有序的数据排序效率较高，但对于大规模无序数据，性能可能较差。
   • 希尔排序的时间复杂度取决于间隔序列的选择，一般在一些情况下可以达到  左右，虽然最坏情况下时间复杂度仍然为 ，但平均性能比直接插入排序更好，尤其对于大规模数据。

3. 初始状态和循环条件不同：

   • 在直接插入排序函数中，外层循环从数组的第一个元素开始，逐步处理到倒数第二个元素，因为最后一个元素不需要进行插入操作。内层循环的条件是已排好序部分的索引end大于等于 0，只要还没有遍历到数组的开头，就继续比较和移动元素。
   • 希尔排序函数中，外层循环的条件是间隔gap大于 1，通过不断减小gap来逐步进行预排序。在每次外层循环中，都会对间隔为gap的子序列进行处理。内层循环的条件和直接插入排序类似，但处理的是间隔为gap的元素。

总体而言，希尔排序是对直接插入排序的改进，通过更复杂的排序策略，在处理大规模数据时具有更好的性能。而直接插入排序则更加简单直观，适用于小规模或基本有序的数据。