手撕排序算法之插入排序
标签： 手撕排序算法之插入排序 博客 51CTO博客
2023-04-11 18:24:02 117浏览
前言
排序算法是一种算法思想，插入排序有两种，直接插入排序和希尔排序，后者可以看作是前者的优化，因为它完完全全采用的是插入排序算法
一、直接插入排序
分两种情况，
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;
}执行结果：
很明显，希尔排序的性能远远高于直接插入排序，数组越大，差距越明显
好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
展开评论
