前言
排序算法是一种算法思想,插入排序有两种,直接插入排序和希尔排序,后者可以看作是前者的优化,因为它完完全全采用的是插入排序算法
一、直接插入排序
分两种情况,
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;
}
执行结果:
很明显,希尔排序的性能远远高于直接插入排序,数组越大,差距越明显