【初阶数据结构篇】插入、希尔、选择、堆排序介绍（上篇）

插入、希尔、选择、堆排序

前言

• 本篇以排升序为例

代码位置

gitee

排序方法

常见排序算法

本篇介绍前四种，在之后博客中会讲到交换排序和归并排序以及计数排序

插入排序

直接插入排序

基本思想

直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列。

• 实际我们玩扑克牌时就用到了这一思想

动图理解：

• 当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置即将 array[i] 插⼊，原来位置上的元素顺序后移
• 以排序数组为例：

代码语言：javascript复制

int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };

• 由以上分析可以定义两个参数
• end：指向有序序列的最后一个数据，显然：
  • 初始为0
  • 末态为n-2
• tmp：有序序列后的第一个待排序数据，显然
  • 初始为1
  • 末态为n-1
• 以一次循环为例：
• 将tmp与end位置数据进行比较，
  • 若end处更大，需要将end位置数据移到end 1处，end–，继续让end-1处数据与tmp比较
  • 否则直接跳出循环，此时end 1位置为空，需要放入tmp
• 最坏的情况：当end为0处数据移到end为1处，此时end变为-1，需要跳出循环，并将tmp放到0处

结合以上分析，很容易写出代码：

代码语言：javascript复制

void InsertSort(int* arr, int n)
{
	//n-2
	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;
	}
}

---

时间复杂度分析：

• 最坏情况：数组降序排列
  • 当我们对下标为i（0<i<n）的tmp数据进行插入时，会将其与前面i个数据比较i次，总比较次数即1 2 3 ……(n-1)，为O(n2)
• 最好情况：数组升序排列
  • 当我们对下标为i（0<i<n）的tmp数据进行插入时，只会与其前面一个数据比较一次，即总共(n-1)此，为O(n)

空间复杂度：O(1)

---

希尔排序

在直接插入排序中我们发现，元素越无序，直接插入排序算法时间效率越低（因为比较次数越多）。特别是当数组为降序，我们要排升序，此时数组的相对无序程度达到了最大，时间复杂度也到了最大

所以我们有没有办法对这样一种情况进行优化呢？

答案就是希尔排序，它由D.L.Shell在1959年提出，也是第一批时间复杂度突破了O(n2)的算法之一（致敬