手撕排序算法之插入排序

前言

排序算法是一种算法思想，插入排序有两种，直接插入排序和希尔排序，后者可以看作是前者的优化，因为它完完全全采用的是插入排序算法

一、直接插入排序

分两种情况，

1.1简单插入排序

在一个已经有序的数组里插入一个数据，使其依旧有序，只需要对一个元素进行插入排序，进行一次插入排序

假如数组有n+1个元素，前n个元素按升序排序，第n+1个元素是待插入元素，那我们如何将待插入元素插入有序数组，并且使其依旧有序呢？

答案是要拿被插入的元素依次和数组的元素对比，如果插入元素小于数组元素，那么该数据元素向后移动一个位置，插入元素继续和下一个数组元素对比，直到大于等于某个位置的数组元素时，在该位置的数组元素后插入被插入的元素，如下图，我们选择从后向前对比

代码如下，请君自取：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void SimpleInsertionSort(int* arr, int n)//带插入的数组和元素
{
	int end;  
	end = n-2;//有序数组最后一个元素的下标
	int tem = arr[end+1];//有序数组后的元素，待插入排序
	while (end >= 0)//待插入元素从后向前依次与有序数组元素比较
	{
  if (arr[end] > tem)//插入元素小则与下一有序数组元素比较
  {
  	arr[end + 1] = arr[end];
  	end--;
  }
  else
  {
  	break;
  }   
	}
	//出来时有两种情况，但无论哪种情况，都要插入元素
	//1.待插入元素小于所有有序数组元素，全部比较完后
	//2.待插入元素小于有序数组中间的某一元素
	arr[end + 1]=tem;  
}
int main()
{
	int arr[10] = { 0,1,3,4,5,6,7,8,9,2 };
	int n = sizeof(arr) / sizeof(arr[0]);
	SimpleInsertionSort(arr,n);
	for (int i = 0; i < 10; i++)
	{
  printf("%d ", arr[i]);
	}
}

执行结果：

1.2复杂插入排序（也就是真正的直接插入排序）

为什么要说是复杂插入排序呢？因为我们要在有n个元素的无序数组里，利用简单插入排序的思想，找到有序数组，进行多次简单插入排序，使得数组有序

那么简单插入排序的思想是什么呢？

使得插入元素前的n个元素保持有序，从后向前，插入元素依次与有序元素比较，直到找到一个合适的位置插入其中（在这个过程中我们需要保存待插入元素的值）

到这里，我们是否可以明白，直接插入排序其实就是多个简单插入排序的结合

对于复杂插入排序，我们如何找到一个有序的数组呢？

只有一个元素，那么一定有序

因此，我们将第一个元素作为有序数组，根据简单插入排序

将第二个元素当作插入元素，与有序数组对比，进行简单插入排序，第一次简单插入排序完成后，

有序数组的个数变为2，我们将第三个元素当作插入元素，同前面的有序数组对比，进行简单插入排序，直到最后一次的插入排序，那么最后一次插入排序在什么时候呢

假设有n个元素，要执行多少次简单插入排序呢？插入排序什么时候应该停止呢

答案是n-1次，当第n个元素为待插入元素时，这一次的简单插入排序完成之后，插入排序也就随之结束，而第一次待插入的元素是第二个，2到n，n-1次

其实，对于n个元素的数组，最后一次插入排序时，有序数组最后一个元素的下标一定是n-1-1,即n-2,也就是有序数组的最大下标为n-2，我们用i来表示数组元素下标，只需让i<n-1，就可以控制排序是否需要进行

那么，到这里，我们是否明白了只要对上述的简单插入排序进行次数的控制（也就是控制插入排序是否需要进行），就可以对一个完全乱序的数组进行插入排序

代码如下，请君自取

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void StraightInsertionSort(int* arr, int n)
{
	int end;//有序数组最后一个元素的下标
	int tem;//待插入元素的值
	for (int i = 0; i < n - 1; i++)//i为有序数组------
  //--最后一个元素的下标，最后一次插入时，有序数组最后一个元素的下标为n-2
	{
  end = i;
  tem = arr[end + 1];
  while (end >= 0)//待插入元素从后向前依次与有序数组元素比较
  {
  	if (arr[end] > tem)//插入元素小则与下一有序数组元素比较
  	{
    arr[end + 1] = arr[end];
    end--;
  	}
  	else
  	{
    break;
  	}
  }
	//出来时有两种情况，但无论哪种情况，都要插入元素
	//1.待插入元素小于所有有序数组元素，全部比较完后
	//2.待插入元素小于有序数组中间的某一元素
  arr[end + 1] = tem;
	}
}
int main()
{
	int arr[10] = { 7,6,8,4,5,3,1,0,2,9 };
	int n = sizeof(arr) / sizeof(arr[0]);
	StraightInsertionSort(arr,n);
	for (int i = 0; i < 10; i++)
	{
  printf("%d ", arr[i]);
	}
}

执行结果：

1.3时间复杂度分析

我们都知道，时间复杂度是算法在最坏的情况得到的结果，那什么时候结果是最坏的呢？

答案是逆序，有n个元素的数组逆序，我们想要插入一个元素保持有序，所需要移动的次数为1+2+...+n-1

因此直接插入排序算法的时间复杂度为O（n^2)

二、希尔排序

2.1简单解释

在前言里，我们说，希尔排序是直接插入排序的优化，为什么这样说呢？它又是如何对直接插入排序进行优化的

对于直接插入排序而言，就是通过一次次的简单插入排序，将较大的数移动到后边的位置，将较小数放到前面的位置，使得数组逐渐有序，但这种移动效率太低，因为每一次简单排序，一个元素最多能向后移动一次

因此希尔排序是这样做的，先将无序数组进行预排序，使得较大的数更快到达后边，较小数更快到达前边，通过简单的处理，使得原本无序的数组接近有序，再对数组进行直接插入排序

那么预排序是怎么做到这一点的呢？

将数组进行分组，间隔为gap的元素为一组，对同一组的元素进行直接排序，gap的值越大，元素移动的就越快，但也有缺点，那就是越不接近有序

这里给的是有序数组，可我们要明白，当gap足够大时，当预排序分组后，再对每一组进行直接插入排序后，确实满足了大数快速向后，小数快速向前这一点

此时，我们再对整个数组进行直接插入排序，因为经过预排序的处理，原本无序的数组已经接近有序，此时再进行直接插入排序，效率会高很多

2.2希尔排序代码

代码如下，请君自取

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void ShellSort(int* arr, int n)
{
	int gap=n;
	while (gap > 1)
	{
  gap =gap/2;
  //gap=gap/3+1;
  int end;
  int tem;
  for (int i = 0; i < n - gap; i++)
  {
  	end = i;
  	tem = arr[end + gap];
  	while (end >= 0)
  	{
    if (arr[end] > tem)//插入元素小则与下一有序数组元素比较
    {
    	arr[end + gap] = arr[end];
    	end -= gap;
    }
    else
    {
    	break;
    }
  	}
  	arr[end + gap] = tem;
  }
	}
}
int main()
{
	int arr[10] = { 7,6,8,4,5,3,1,0,2,9 };
	int n = sizeof(arr) / sizeof(arr[0]);
	ShellSort(arr, n);
	for (int i = 0; i < 10; i++)
	{
  printf("%d ", arr[i]);
	}
}

执行结果：

2.3没看懂代码，请继续看这里

当你看过希尔排序的代码后，有没有一种很眼熟的感觉，是不是感觉云里雾里？别着急

让我们再来回顾一下希尔排序的做法

1.预排序，将间隔为gap的元素划分为一组，对每组进行直接插入排序

那么相比直接插入排序，希尔排序的插入排序应当在什么时候停止呢？

n个元素的数组，对于每次插入排序而言，有序数组的最后一个元素的下标最大是n-1-gap，我们用i表示数组元素下标，只需i<n-gap就可以控制插入排序是否进行

2.直接插入排序

当gap=1时，其实就是直接插入排序，其代码也和直接插入排序的代码相同

关于gap

我们需要了解到，gap越大，较大的数更快到达后边，较小数更快到达前边，但是也会使得数组越不接近有序，

而gap越小，虽然元素的移动会越慢，但会使得数组越接近有序，而当gap=1的时候，就是直接插入排序

因此，gap的值应该是不断变化的，我们只要保证它最后的值为1，进行直接插入排序就行，其前面的所有过程，都是在进行预排序

三、两种算法的性能比较

我们动态申请10000个数据个数组，并随机生成数据放入其中，用clock函数的差值得到两种算法排序10000个元素的运行时间

代码如下，请君自取

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
void ShellSort(int* arr, int n)//希尔排序
{
	int gap=n;
	while (gap > 1)
	{
  gap /= 2;
  int end;
  int tem;
  for (int i = 0; i < n - gap; i++)
  {
  	end = i;
  	tem = arr[end + gap];
  	while (end >= 0)
  	{
    if (arr[end] > tem)//插入元素小则与下一有序数组元素比较
    {
    	arr[end + gap] = arr[end];
    	end -= gap;
    }
    els
    {
    	break;
    }
  	}
  	arr[end + gap] = tem;
  }
	}  
}
void StraightInsertionSort(int* arr, int n)
//直接插入排序
{
	int end;//有序数组最后一个元素的下标
	int tem;//待插入元素的值
	for (int i = 0; i < n - 1; i++)//i为有序数组最后
  //一个元素的下标，最后一次插入时，有序数组最后一个元素的下标为n-2
	{
  end = i;
  tem = arr[end + 1];
  while (end >= 0)//待插入元素从后向前依次与有序数组元素比较
  {
  	if (arr[end] > tem)//插入元素小则与下一有序数组元素比较
  	{
    arr[end + 1] = arr[end];
    end--;
  	}
  	else
  	{
    break;
  	}
  }
  arr[end + 1] = tem;
	//出来时有两种情况，但无论哪种情况，都要插入元素
	//1.待插入元素小于所有有序数组元素，全部比较完后
	//2.待插入元素小于有序数组中间的某一元素
  arr[end + 1] = tem;
	}
}
int main()
{
	srand((unsigned int)time(0));//设置时间戳
	int* a1 = (int*)malloc(sizeof(int) * 10000);//动态开辟空间
	int* a2 = (int*)malloc(sizeof(int) * 10000);
	int* a3 = (int*)malloc(sizeof(int) * 10000);
	for (int i = 0; i < 10000; i++)
	{
  a1[i] = rand();//产生随机值
  a2[i] = a1[i];//a2,a3的内容是相同的
  a3[i] = a1[i];
	}
	int start1 = clock();//clock函数功能，返回系统运行到该语句处的毫秒数，
	ShellSort(a2, 10000);
	int end1 = clock();//clock函数功能，返回系统运行到该语句处的毫秒数，
	int start2 = clock();
	StraightInsertionSort(a3, 10000);
	int end2 = clock();
	printf("%d\n", end1 - start1);//两者做差，可得算法的执行时间
	printf("%d\n", end2 - start2);
	free(a1);
	a1 = NULL;
	free(a2);
	a2 = NULL;
	free(a3);
	a3 = NULL;
}

执行结果：

很明显，希尔排序的性能远远高于直接插入排序，数组越大，差距越明显