三种插入排序算法

目录

1.直接插入排序

直接插入排序的步骤示例

直接插入排序的特点

适用场景

2.折半插入排序

折半插入排序的基本原理

折半插入排序的实现过程

折半插入排序的时间复杂度

折半插入排序的特点

3.希尔排序

希尔排序的基本原理

希尔排序的步骤举例

希尔排序的时间复杂度

希尔排序的空间复杂度

希尔排序的特点

希尔排序的适用场景

四、代码实现

1.直接插入排序

直接插入排序（Insertion Sort）是一种简单的排序算法，其基本原理是将数组分为两部分：已排序部分和未排序部分。每次从未排序部分选择一个元素，将它插入到已排序部分的合适位置。

具体步骤如下：

1. 初始状态：将数组的第一个元素视为已排序部分，剩余的元素视为未排序部分。

2. 从第二个元素开始处理：

   • 从未排序部分取出一个元素（通常是从左到右依次处理每个元素）。
   • 将该元素与已排序部分的元素逐个比较，从已排序部分的最后一个元素开始，找到合适的位置插入该元素。

3. 插入：

   • 如果当前元素比已排序部分的某个元素小，则将已排序部分的元素向右移动一个位置，直到找到该元素应该插入的位置。
   • 将当前元素插入到正确的位置。

4. 重复：

   • 重复步骤 2 和 3，直到所有元素都被处理完成。

直接插入排序的步骤示例

假设我们有一个待排序的数组：[5, 2, 4, 6, 1, 3]

• 第一步：假设第一个元素 5 已排序，剩余未排序的部分是 [2, 4, 6, 1, 3]。
• 第二步：处理第二个元素 2：
  • 与已排序部分 [5] 比较，发现 2 小于 5，所以将 5 向右移动一个位置，将 2 插入到第一位。
  • 结果：[2, 5, 4, 6, 1, 3]
• 第三步：处理第三个元素 4：
  • 与已排序部分 [2, 5] 比较，发现 4 小于 5，所以将 5 向右移动一个位置，将 4 插入到 2 后面。
  • 结果：[2, 4, 5, 6, 1, 3]
• 第四步：处理第四个元素 6：
  • 与已排序部分 [2, 4, 5] 比较，发现 6 比这些元素都大，因此直接将 6 插入到末尾。
  • 结果：[2, 4, 5, 6, 1, 3]
• 第五步：处理第五个元素 1：
  • 与已排序部分 [2, 4, 5, 6] 比较，发现 1 小于所有已排序的元素，于是将这些元素依次向右移动，并将 1 插入到最前面。
  • 结果：[1, 2, 4, 5, 6, 3]
• 第六步：处理第六个元素 3：
  • 与已排序部分 [1, 2, 4, 5, 6] 比较，发现 3 小于 4，所以将 4, 5, 6 向右移动，并将 3 插入到 2 后面。
  • 结果：[1, 2, 3, 4, 5, 6]

最终，数组变为已排序状态：[1, 2, 3, 4, 5, 6]。

直接插入排序的特点

• 时间复杂度：

  • 最好情况：O(n)（当数组已经是有序的时，每个元素只需要进行一次比较）
  • 最坏情况：O(n²)（当数组是逆序时，每个元素需要与所有已排序的元素进行比较）
  • 平均情况：O(n²)

• 空间复杂度：O(1)，因为直接插入排序是原地排序算法，不需要额外的内存空间。

• 稳定性：稳定。相同元素的相对顺序不变。

适用场景

直接插入排序适用于：

• 数据量小的情况，因为其实现简单且效率较高（在小数据集时往往比复杂的排序算法更快）。
• 数据本身接近有序的情况，插入排序在这种情况下的性能非常好。

2.折半插入排序

折半插入排序（Binary Insertion Sort） 是一种改进版的 插入排序，它通过使用 二分查找 来减少元素插入时的比较次数，从而提高了直接插入排序的效率。折半插入排序依然保持插入排序的基本思想：每次取一个未排序的元素，将其插入到已排序部分的合适位置。不过，区别在于查找插入位置的方式不同。

折半插入排序的基本原理

折半插入排序的基本思想与直接插入排序相似，唯一的区别在于寻找插入位置时采用了二分查找（Binary Search）方法。

基本步骤：

1. 初始状态：

   • 将第一个元素视为已排序部分，剩下的元素视为未排序部分。

2. 从第二个元素开始：

   • 每次取一个未排序的元素（假设是 arr[i]），用二分查找在已排序部分中找到合适的位置。

3. 二分查找插入位置：

   • 通过二分查找来确定当前元素应插入的位置。二分查找的过程是通过逐渐缩小搜索区间来找到插入点，降低了比较次数。

4. 插入元素：

   • 找到插入位置后，将已排序部分从插入位置开始的所有元素向后移动一位，为待插入的元素腾出空间。
   • 然后将待插入元素放入找到的合适位置。

5. 重复：

   • 重复步骤 2 到 4，直到所有元素都被处理完成。

折半插入排序的实现过程

假设我们有一个待排序的数组 [5, 2, 4, 6, 1, 3]，下面逐步展示如何使用折半插入排序来排序这个数组。

初始状态：

[5, 2, 4, 6, 1, 3]，第一个元素 5 认为是已排序的部分。

第一步：处理元素 2：

• 使用二分查找确定 2 在已排序部分 [5] 中的插入位置。
• 查找结果：2 应该插入到 5 前面（位置 0）。
• 将 5 向右移动，2 插入到位置 0。
• 结果：[2, 5, 4, 6, 1, 3]

第二步：处理元素 4：

• 使用二分查找确定 4 在已排序部分 [2, 5] 中的插入位置。
• 查找结果：4 应该插入到 5 前面（位置 1）。
• 将 5 向右移动，4 插入到位置 1。
• 结果：[2, 4, 5, 6, 1, 3]

第三步：处理元素 6：

• 使用二分查找确定 6 在已排序部分 [2, 4, 5] 中的插入位置。
• 查找结果：6 应该插入到 5 后面（位置 3）。
• 结果：[2, 4, 5, 6, 1, 3]

第四步：处理元素 1：

• 使用二分查找确定 1 在已排序部分 [2, 4, 5, 6] 中的插入位置。
• 查找结果：1 应该插入到 2 前面（位置 0）。
• 将所有元素向右移动，并将 1 插入到位置 0。
• 结果：[1, 2, 4, 5, 6, 3]

第五步：处理元素 3：

• 使用二分查找确定 3 在已排序部分 [1, 2, 4, 5, 6] 中的插入位置。
• 查找结果：3 应该插入到 2 和 4 之间（位置 2）。
• 将 4, 5, 6 向右移动，并将 3 插入到位置 2。
• 结果：[1, 2, 3, 4, 5, 6]

最终，数组变为已排序状态：[1, 2, 3, 4, 5, 6]。

折半插入排序的时间复杂度

• 二分查找的时间复杂度：O(log n)，用于确定待插入元素的插入位置。
• 元素移动的时间复杂度：每次插入元素时，最多需要将元素向后移动一次，时间复杂度为 O(n)。

因此，折半插入排序的总时间复杂度为 O(n log n)（查找插入位置部分）加 O(n)（元素移动部分）。因此，整体时间复杂度为 O(n²)，与直接插入排序相同。

折半插入排序的特点

• 时间复杂度：最坏情况下是 O(n²)，和直接插入排序相同，但减少了比较的次数。
• 空间复杂度：O(1)，因为折半插入排序是原地排序算法，不需要额外的内存空间。
• 稳定性：稳定。与直接插入排序一样，折半插入排序不会改变相等元素的相对顺序。
• 适用场景：适用于小规模数据集或者数据基本有序的情况。

3.希尔排序

希尔排序（Shell Sort） 是一种基于插入排序的排序算法，它通过引入一个新的概念——增量（步长），使得在排序过程中，元素能够更快地接近最终的有序状态，从而提高插入排序的效率。希尔排序也被称为 递减增量排序（Diminishing Increment Sort）。

希尔排序的基本原理

希尔排序的核心思想是在排序过程中不断减少步长（即增量），让元素之间的“间隔”逐渐缩小。这样，元素被分成多个子序列，通过在这些子序列中的插入排序来加速整个排序过程。随着步长逐渐减小，最终形成一个几乎有序的序列，此时使用普通的插入排序进行最终的排序。

具体来说，希尔排序通过以下几个步骤来进行排序：

1. 初始步长选择：选择一个步长序列（增量序列），初始步长通常是数组长度的一半。随着排序进行，步长逐渐减小，直到步长为 1。

2. 分组并插入排序：在每一轮排序中，根据当前步长将数组分成若干个子序列。每个子序列中的元素都是步长间隔的元素，分别对这些子序列进行插入排序。这个过程类似于插入排序，但是每次插入排序的范围更广。

3. 逐步减小步长：每一轮排序后，步长减小，通常是将步长除以 2，直到步长为 1。

4. 最终插入排序：当步长为 1 时，对整个数组进行一次插入排序，此时数组应该已经接近有序，插入排序的效率也会大大提高。

希尔排序的步骤举例

假设我们有一个待排序的数组 [5, 2, 4, 6, 1, 3]，下面逐步展示如何使用希尔排序进行排序。我们选择的步长序列是 n/2, n/4, ..., 1（也可以选择其他的增量序列）。

初始数组：

[5, 2, 4, 6, 1, 3]

第一步：选择步长为 3（n/2 = 6/2 = 3）

将数组分成步长为 3 的子序列：

• 子序列 1：[5, 6]
• 子序列 2：[2, 1]
• 子序列 3：[4, 3]

分别对每个子序列进行插入排序：

• 对子序列 [5, 6] 排序后仍然是 [5, 6]。
• 对子序列 [2, 1] 排序后是 [1, 2]。
• 对子序列 [4, 3] 排序后是 [3, 4]。

排序后数组： [5, 1, 3, 6, 2, 4]

第二步：选择步长为 1（n/4 = 6/4 = 1）

此时步长为 1，将对整个数组进行一次插入排序： [5, 1, 3, 6, 2, 4]

对整个数组进行插入排序：

• 1 插入到 5 前面，得到 [1, 5, 3, 6, 2, 4]
• 3 插入到 5 后面，得到 [1, 3, 5, 6, 2, 4]
• 6 插入到 5 后面，得到 [1, 3, 5, 6, 2, 4]
• 2 插入到 3 和 5 之间，得到 [1, 2, 3, 5, 6, 4]
• 4 插入到 5 和 6 之间，得到最终排序的数组 [1, 2, 3, 4, 5, 6]

最终，数组变为已排序状态：[1, 2, 3, 4, 5, 6]

希尔排序的时间复杂度

希尔排序的时间复杂度与选择的增量序列有关。对于最坏情况，希尔排序的时间复杂度通常为 O(n²)，这与插入排序相同。但在某些增量序列下，它的时间复杂度可以得到显著的改善，达到 O(n^(3/2)) 或更优。

• 最坏情况时间复杂度：O(n²)（当增量序列不好时）
• 平均情况时间复杂度：O(n^(3/2))（常见的增量序列，如 n/2, n/4, ..., 1）
• 最佳情况时间复杂度：O(n log n)（当增量序列较好时）

希尔排序的空间复杂度

希尔排序是 原地排序算法，它只需要常数级别的额外空间，因此它的空间复杂度是 O(1)。

希尔排序的特点

1. 时间复杂度较优：相比于普通的插入排序，希尔排序的性能更好，特别是在数据量较大时，能够有效减少插入排序的比较和交换次数。
2. 增量序列选择：希尔排序的性能很大程度上依赖于增量序列的选择。选择不同的增量序列可能导致不同的时间复杂度。最常见的增量序列是 n/2, n/4, ..., 1，但一些优化的增量序列（如 Hibbard 序列、Sedgewick 序列等）可以使算法的效率更高。
3. 不稳定：希尔排序是 不稳定的 排序算法。由于排序过程中涉及到的子序列排序并不是稳定的插入排序，因此相等元素的相对顺序可能会发生变化。
4. 适用于中等规模数据：希尔排序适用于数据量中等或较大的情况，因为它比普通的插入排序更高效。

希尔排序的适用场景

希尔排序适用于以下场景：

• 中等规模的数据集：当数据量适中且增量序列选择合理时，希尔排序比简单的插入排序更高效。
• 增量序列优化：在一些情况下，选择适当的增量序列能大幅度提高排序的效率。
• 对稳定性要求不高：因为希尔排序是不稳定排序，它适用于对元素相对顺序没有严格要求的场景。

四、代码实现

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//插入排序

typedef int ElemType;

//顺序表
typedef struct SqList {
	ElemType* data;//指针，指向一块内存的起始地址
	int length;//存储动态数组的长度
}SqList;

//顺序表初始化
void initSqList(SqList& L, int len) {
	L.length = len;
	L.data = (ElemType*)malloc(sizeof(ElemType) * L.length);//分配空间
	srand(time(NULL));//随机数生成
	for (int i = 0; i < L.length; i++)
	{
		L.data[i] = rand() % 100;//随机生成数字存入顺序表，对100取余是为了规范存入的数据是0-99
	}
}

//顺序表打印
void printSqList(SqList L) {
	for (int i = 0; i < L.length; i++)
	{
		printf("%3d", L.data[i]);
	}
	printf("\n");
}

// 插入排序顺序表中的元素
void insertSort(ElemType* arr, int length) {
	int i, j, temp;
	for (i = 1; i < length; i++) { //外层循环，控制要插入的数，从下标为1开始
		if (arr[i] < arr[i - 1]) { //小于前一个数
			temp = arr[i];        //暂存要插入的数
			//从前一个数开始比，大于要插入的数，则前一个数后移，直到找到合适位置或到表头
			for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = temp;
		}
	}
}

// 折半插入排序
void binaryInsertSort(ElemType* arr,int length) {
	int i, j, temp, low, high, mid;  // 定义6个变量，
	for (i = 1; i < length; i++) {   // 外层循环，控制要插入的数，从下标为1开始
		temp = arr[i];             // 暂存要插入的数
		low = 0, high = i - 1;     // 折半查找插入的位置
		while (low <= high) {
			mid = (low + high) / 2;
			if (arr[mid] > temp)
				high = mid - 1;
			else                   //保持稳定性，等于情况往右找
				low = mid + 1;
		}
		for (j = i - 1; j >= high + 1; j--) //从high+1到i-1都往后移一位
			arr[j + 1] = arr[j];
		arr[high + 1] = temp;               //high+1是插入位置
	}
}

// 希尔排序
void shellSort(ElemType arr[], int length) {
	int i, j, d, temp;
	for (d = length / 2; d >= 1; d = d / 2) {  //步长变化，d每次减半
		for (i = d; i < length; i++) {   //依次处理各个子表
			if (arr[i] < arr[i - d]) {   //小于子表中前一个元素
				temp = arr[i];           //暂存要插入的元素
				// 大于它的元素依次后移一个步长
				for (j = i - d; j >= 0 && arr[j] > temp; j = j - d)
					arr[j + d] = arr[j];
				arr[j + d] = temp;       //插入到子表第一个小于它的元素之后
			}
		}
	}
}

int main() {
	SqList L;//定义一个顺序表
	initSqList(L, 10);//初始化顺序表，分配10个空间
	printSqList(L);//打印顺序表中的值
	//insertSort(L.data, 10);//将顺序表进行直接插入排序
	//binaryInsertSort(L.data, 10);//将顺序表进行折半插入排序
	shellSort(L.data, 10);//将顺序表进行希尔排序
	printSqList(L);
	return 0;
}