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

前言

本文介绍几种排序算法，我把他们分成两组，每一组的两种算法都有一种简单算法和进阶优化的联系。而这种优化在算法的效率等方面相差是非常大的。

一、插入排序与希尔排序

插入排序是一种比较简单的排序算法，这种算法的效率其实不是那么高，所以就有了希尔排序作为它的“升华算法”，希尔排序那就非常的强大了。

直接插入排序

直接插入排序的定义是这样的：把待排序的记录按照其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
这是一直比较官方的语言的描述，简单的说就是从待排序的序列中的第一个值开始，将其视为一个有序序列（单值序列），然后逐步把序列中的其他值一一插入到这个有序序列里并使其始终有序，最后就可以得到一个有序的序列。

• 这里我们直接来实现一下插入排序

  void InsertSort(int* arr,int n)//排序算法传参基本都是传数组和数组大小
  {
  	for(int i = 0;i<n-1;i++)
  	{
  		int end = i;
  		int tem = arr[end+1];//记录要插入的数据
  		while(end >= 0)
  		{
  			if(arr[end] > tem)//假设要排升序
  			{
  				arr[end + 1] = arr[end];//将大的数据往后移动空出位置
  				end--;//往后继续找合适的位置
  			}
  			else
  			{
  				break;//找到了合适位置跳出循环
  			}
  		}
  		arr[end + 1] = tem;//当前比较值的前一个位置是空着的，要给到那个位置
  	}
  }
  

• 时间复杂度分析
  对于这个排序算法，虽然有两个循环，但时间复杂的并不是严格的O(N^2)，这是因为内部的while循环并不是和外部的for循环一样要循环n次，相应的会少一些，因为我们遍历那个已经有序的序列时，最多也不会一开始就遍历n次，而最好的情况就是本身相当有序，数据分布基本有序，这时候就是接近于O(N)了，这是最好的情况。最坏的情况就是，比如升序时，大的数据全在前，小的数据全在后，这时候时间复杂度是O(N^2)。当然，大多数情况下，都是接近于O(N^2)的。所以说效率不是那么高。

希尔排序

希尔排序又称缩小增量法。上文我们分析了插入排序和插入排序的时间复杂度，在实际情况下，效率相对还是很低，我们也分析了，如果是升序，那么对于小数据在前大数据在后的时候，时间复杂度接近O(N)，所以我们怎么把数据处理成这样让插入排序变得高效呢？于是希尔排序就来了。

• 希尔排序的思想：选定一个gap值，把代排序的文件分成各组，间隔相等（为gap值）的数据视为一组，对每一组内的数据进行排序，排序完成后我们进行一次迭代，更新一下gap值，再次分组排序，直到最后我们就直接对整个数据集合进行直接插入排序。这个时候的数据就基本符合直接插入排序效率较高的那种情况了（就比如上文所说，大的在前小的在后）。
• 希尔排序的具体操作：根据我们的思想，取一个gap值，从第一个数据开始，取间隔为gap的数据作为一组，以此类推分出来了许多组，对每一组进行直接插入排序（降低了数据量，提高效率）。这是一个内层循环。然后我们对于gap值需要做处理，gap是可以取任意值然后以一定的规律变小的，不同的gap有不同的时间复杂度也就是效率。一般来说取 “gap = n / 3 +1” 然后以 “gap = gap / 3 + 1” 作为循环条件直至gap = 1，也就是最后的一次插入排序。这就组成了外层循环。本文将要实现的代码也是这样的gap取值，这是相对常见一些的取值。
• 我们每一次都优化了数据的结构（分布情况），有利于进行高效的插入排序，在一次次的分组之中，完成了整体的效率提高，这就是希尔排序的精妙之处。这里有一张图也可以帮助大家理解
  

讲述完了希尔排序的主要原理，下面就直接来实现一下代码：

void Shellsort(int* arr,int n)//这里还是排升序
{
	int gap = n;
	while(gap > 1)//外层循环，gap迭代
	{
		gap = gap / 3 + 1;
		for(int i = 0;i<n - gap;i++)//开始对每一组进行插入排序，每一次的循环都是一个组内元素的插入排序，直到所有组都排序完毕
		{
			int end = i;
			int tem = arr[end + gap];//直接用间距gap找到同组的元素
			while(end >= 0)//同组内的元素插入排序
			{
				if(arr[end]>tem)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tem;
		}
	}
}

• 时间复杂度分析
  希尔排序的代码模拟如上，看似代码量不大，甚至比插入排序多了一个循环，有三个循环，但是，希尔排序的效率却比直接插入排序高了不止一个档次。但希尔排序的时间复杂度本身也是个复杂的问题，由于待排序的数据量n，希尔排序中gap的选值和迭代方式选取都有不同，其时间复杂度都是不同的，所以对于希尔排序的时间复杂度，学术界目前也没有一个定论，比如有一本书（《数据结构（C语言版）》–严蔚敏）中写道：
  
  所以希尔排序的时间复杂度可以很高，这取决于gap的取值等条件，但希尔排序大致是能达到O(N^1.3)左右的，我们可以记这个数字，这也是相当高的效率了。

二、选择排序与堆排序

上文介绍了两种插入式的排序，接下来是选择式的排序：从一个数据集合里选出最值数据放到合适的位置完成排序。本文介绍两种最经典的排序：直接选择排序和堆排序。

直接选择排序

直接选择排序非常简单粗暴，就是在数组里找到最值的数据放到两头，然后再找剩下的……直到遍历完数据，也就排序完毕了。为了方便一些，我们可以一次找最大值和最小值。
这种排序非常好理解，这里我也就不过多赘述了，直接实现代码吧：

void Selectsort(int* arr,int n)//还是排升序
{
	int begin = 0, end = n - 1;
	while(begin < end)//外层循环，控制查找数据范围
	{
		int min = begin;//设置一个比较的对象
		int max = begin;
		for(int i = begin + 1; i <= end; i++)
		{
			if(arr[i]>arr[max])//更新最大最小值的下标
			{
				max = i;
			}
			if(arr[i]<arr[min])
			{
				min = i;
			}
		}
		if(max == begin)//如果最大值刚好就在开始位置，那么会交换两次出现错误，要额外设置一下
		{
			max = min;		
		}
		swap(&arr[begin],&arr[min]);//一个交换的函数，比较的简单我就不写了
		swap(&arr[end],&arr[max]);
		begin++;
		end--;
	}
}

直接的选择排序毫无疑问时间复杂度为O(N^2)，思想非常简单，但是效率肯定是低下的。

堆排序

之前，我有过专门讲解树这种数据结构的文章，而堆是一种完全二叉树，它是一种非常高效的结构，很经典的应用就是堆排序。所谓堆排序，并不是说就是利用堆这种数据结构来实现，虽然也可以做到，但前提是你需要一个堆，这就使得操作变得更麻烦了。真正的堆排序其实是利用了堆的思想来实现的排序算法。

• 堆排序的算法思路：堆对于数据的处理是高效的，而堆分为大堆和小堆，也就是说堆顶的数据总是堆整体的最值，这就是我们排序的一个最根本的东西。所以在对大量数据进行排序的时候，我们可以用这些数据建立出一个堆结构，对这个堆结构，如果排升序就建大堆，排降序就建小堆，每一次将堆顶数据与堆末尾数据交换，并放在数组的末尾，再对剩下的数据调整为正确的堆结构，然后一次次的调整堆，取出最值，最终就能得到一个排序好的数据集合。
• 堆的排序不仅是用到了思想，也用到了堆结构里的一些操作，比如向下调整建堆算法，帮助我们整理数据为堆并调整，而且其时间复杂度仅为O(logN)（向上调整建堆是O(N)），效率非常高。使得堆排序整体的效率也非常高。

接下来，我们直接来实现这个堆排序的模拟代码：

先把向下调整建堆算法拿过来                     //调整的数据个数（范围）
void Adjustdown(HPdatatype* arr, int parent, int n) //目前是调整为大堆(大堆并不有序！！)
{                               //父结点位置
	int child = parent * 2 + 1;
	while (child < n)
	{
		                        //大堆：<
		                        //小堆：>
		if (child + 1 < n && 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--)//n-1是找到最后一个结点，再-1然后2是在找父结点，然后循环找到所有父结点
	{
		Adjustdown(arr,i,n);//从最后一颗子树开始，把每一棵子树都向下调整一遍，将杂乱的数据整理成堆结构
	}
	int end = n-1;
	while(end>=0)
	{
		swap(&arr[0],&arr[end]);//首尾数据交换拿到最值放在数组末尾
		Adjustdown(arr,0,end)//end本身就是n-1，已经减少了调整算法操作的范围
		end--;               //只需要不断的取最值，减少操作范围，不断循环，最后就是一个有序的数组了
	}
}

• 时间复杂度分析
  对于堆的主排序算法，有两个独立的循环，第一个循环是整体的建堆过程，内外部的循环加在一起其实是O(N)，因为循环的总次数都不是N次，放在一起总体的时间复杂度推导出来就是O(N)，而第二个循环的时间复杂度就是外层的N次和内层的logN次，整体的复杂度是O(N*logN)，而且堆排序几乎能适用绝大部分场景，而且效率基本没有波动，是一个集高效强大于一身的排序算法，而且被C++的标准库给采用，当C++库的排序算法的底层快速排序不适用时，就会转向堆排序来处理，可见堆排序的强大。

总结

本文介绍了四种经典的排序算法，希望大家可以堆排序算法有一个更深的认知。