网站开发课程百度云,旅游交友的网站建设,福州设计公司排名,减肥养生网站建设引言
进入了初阶数据结构的一个新的主题——排序。所谓排序#xff0c;就是一串记录#xff0c;按照其中的某几个或某些关键字的大小#xff08;一定的规则#xff09;#xff0c;递增或递减排列起来的操作。
排序的稳定性#xff1a;在一定的规则下#xff0c;两个值…
引言
进入了初阶数据结构的一个新的主题——排序。所谓排序就是一串记录按照其中的某几个或某些关键字的大小一定的规则递增或递减排列起来的操作。
排序的稳定性在一定的规则下两个值相等的元素在排序算法处理前后的相对位置是否发生变化如果相对位置变化称这种排序算法是稳定的否则为不稳定的。这个概念并不影响你对排序的学习
排序将会是初阶数据结构的收尾模块在这个模块中将会带领大家学习七大知名的排序方式。而在本篇博客中将会介绍其中的两个排序一个是直接插入排序另一个则是希尔排序。不过在开始我们排序的讲解之前先介绍一下我们将要讲的排序算法都有哪些。 没错我们今天将要处理的就是插入排序模块。
直接插入排序
直接插入排序是一种简单的插入排序法如果想更好的理解希尔排序首先需要弄懂直接插入排序其基本思想是 把待排序的元素按其大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 很像我们打扑克时别人给你发一副乱序的牌让你自己手动排序的过程需要从左往右依次排好顺序 直接插入排序核心逻辑当你插入第 i 个元素时前面的 array[0],array[1]……array[i-1] 已经排好序此时让array[i]的数据按array[i-1]……往前的顺序依次比较找到可插入的位置插入array[i]。原来位置上的元素顺序后移。
这里博主找了一个动图供大家参考理解
实现直接插入排序
我们可以先来分析一下单趟的直接插入排序分为两种情况
1. 单趟排序单独取一趟排序分析其过程过程中end走到序列中间即插入此时tmp小于a[end] 2. [0,end] 区间中元素均小于需插入元素 a[end1] 也就是tmp时单趟排序end走到序列最前面end -1 下面是单趟的代码实现
int end 3;
int tmp a[end 1];
while (end 0) {if (tmp a[end]) {a[end 1] a[end];--end;}else break;
}
a[end 1] tmp;
当end的值从1一直排到末尾序列值n - 2时整个插入排序便完成了。
for循环遍历 end [0, n - 2] 由于长度为n的数组有效下标最大为n - 1当end为n - 1时要插入的元素tmp存的刚好就是a[end 1]也就是下标为n - 1的数同时也就是数组的最后一个值。 直接插入排序代码
// 直接插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i) {// [0,end]区间内有序end 1位置是待插入元素int end i;// tmp保存的是待插入元素的值int tmp a[end 1];while (end 0) {if (tmp a[end]) {// 后移元素操作a[end 1] a[end];--end;}else break;}//元素的插入a[end 1] tmp;}
} 直接插入排序的特性 时间复杂度O(N^2)空间复杂的O(1)元素越接近有序直接插入排序算法效率越高。稳定性稳定最好情况有序/接近有序最坏境况逆序 当一个序列接近有序时每一趟直接插入的过程都会变得简单很多即往前走上几步便能找到比tmp大的值从而跳出单趟循环在每一次循环的跳出过程中直接插入排序的时间复杂度可达 O(N)。相反当一个排序按逆序排列每一趟都需要将前面的所有元素往后移动一次插入tmp时间复杂度便成了计算一个等差数列和:
其时间复杂度显而易见——O(N^2)。
希尔排序
希尔排序也是插入排序的一种是一个名叫希尔Donald Shell的大佬思考推论得出的排序方式其底层逻辑本质上来说还是直接插入排序。希尔大佬发现了直接插入排序元素越接近有序直接插入排序算法效率越高这一特点突发奇想直接插入排序在非顺序的元素序列中如果插入元素的值较小需要从插入尾部一步步移到头部这个过程中的消耗无疑是巨大的。如果能有一种方式能将乱序元素序列通过允许远距离的交换元素进行预排列快速生成一个接近有序的序列这时候在调用直接插入排序排序的速率是否会大大提升。
在希尔排序正真被众人所接受之前这个排序方式也备受质疑但时间总会给出答案希尔排序在现今排序大家庭中有着举足轻重的地位。
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序序列中所有元素分成 i 个组所有距离为 i 的记录分在同一组内并对每一组内的元素进行直接插入排序。然后取 i n / 2 (n为排序序列元素个数) 重复上述分组和排序的工作。当到达 i 1 时所有记录在统一组内排好序。
总结一下其过程
预排序gap 1直接插入排序(gap 1) 实现希尔排序
我们可以首先来分析一下单趟的希尔排序。
设 gap 3 的时候
每隔3个元素取一个数最后可以分成gapgap 3组数
这时候将分好的每一组进行排序排序方式为直接插入排序。注意在排序的过程中不同的组之间的位置不会有交集元素的位置始终实在自己组内变动的。拿上面举例gap 3的第一组数只会在0369位置上排序不会将数字排到其他组的位置上。
这里我们可以复用一下之前选择排序的单趟只不过变成了gap--变成了-gap因为是按照gap分组间隔排序的不同组需要排序的元素之间间隔都为gap下面是排单组第一组4 8 3 7元素时的代码。 int gap 3;
for (int i 0; i n - gap; i gap) {int end i;int tmp a[end gap];while (end 0) {if (tmp a[end]) {a[end gap] a[end];end - gap;}else break;}a[end gap] tmp;
} 这时候想要排分好的多组元素就会容易非常多了我们再套一层循环就可以达到排序不同组的效果。 gap 3;
for (int rem 0; rem gap; rem) {for (int i 0; i n - gap; i gap) {int end i;int tmp a[end gap];while (end 0) {if (tmp a[end]) {a[end gap] a[end];end - gap;}else break;}a[end gap] tmp;}
} 这里的代码就成功的达到帮gap的所有组排序的效果了。现在实现希尔排序就只差最后一步就是改变gap的值让其从n / 2一直除2直到除到1为止每得到一次gap都进行一次上面的分组排序运算下面就是完整的希尔排序代码。 void ShellSort(int* a, int n)
{int gap n;while (gap 1) {gap gap / 2;for (int rem 0; rem gap; rem) {for (int i 0; i n - gap; i gap) {int end i;int tmp a[end gap];while (end 0) {if (tmp a[end]) {a[end gap] a[end];end - gap;}else break;}a[end gap] tmp;}}}
} 希尔排序代码
不过你难道以为希尔排序到这里就结束了其实这份代码还有优化的空间。比如说其实你可以省去遍历不同组的for循环像下面这样。其实本质没什么变化就是把一组一组拿出来排序的方式改成按顺序在不同组之间换着排。
void ShellSort(int* a, int n)
{int gap n;while (gap 1) {gap gap / 2;//去掉遍历不同组的for循环下面遍历的igap改为ifor (int i 0; i n - gap; i) { int end i;int tmp a[end gap];while (end 0) {if (tmp a[end]) {a[end gap] a[end];end - gap;}else break;}a[end gap] tmp;}}
}
你还可以将gap gap / 2 改成gap gap / 3 1。
void ShellSort(int* a, int n)
{int gap n;while (gap 1) {gap gap / 3 1;for (int i 0; i n - gap; i) {int end i;int tmp a[end gap];while (end 0) {if (tmp a[end]) {a[end gap] a[end];end - gap;}else break;}a[end gap] tmp;}}
}
关于希尔排序的一些特性和问题
不过对于gap的取法其实很多最初Shell提出gap gap / 2后来Knuth提出取 gap (gap / 3) 1还有人提出取奇数或者是互质更好。但无论哪一种主张都没有得到证明。
《数据结构-用面相对象方法与C描述》--- 殷人昆 希尔排序的特性 时间复杂度希尔排序的时间复杂度不好计算gap的取值方法很多导致很难去计算在好些书中给出的希尔排序的时间复杂度都不固定。Knuth经过大量的实验统计复杂度大概在O(n^1.25)~O(1.6*n^1.25)之间。现代更高效的增量序列可以使希尔排序达到O(N*logN)的复杂度。希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。整体而言可以达到优化的效果。稳定性不稳定 《数据结构(C语言版)》--- 严蔚敏 测试计算效果
clock()函数是time.h头文件中的一个函数用来返回程序启动到函数调用之间的CPU时钟周期数。这个主可以用来帮助我们衡量程序或程序某个部分的性能。
我们可以计算对比一下本篇博客两个排序方式占用的CPU时间
void TestOP()
{srand(time(0));const int N 100000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];}int begin1 clock();InsertSort(a1, N);int end1 clock();int begin2 clock();ShellSort(a2, N);int end2 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);}
上面这段代码的功能是生成十万个随机数分别用希尔排序和直接插入排序去排列同时用clock记录所消耗的时间打印结果。 我们可以发现希尔排序相比于直接插入排序的性能提升了很多。
结语
本篇博客的内容到这里就结束了插入排序的序列元素越接近有序直接插入排序算法效率越高。希尔正是发现了其特点引入“增量”的概念允许排序中远距离的交换元素快速达到预排序效果大幅度提高了对大规模数据集的排序效率。直接插入排序和希尔排序在计算机科学的排序算法领域中占有重要地位。在掌握其中规律之后相信你对排序一定有了更加深入的理解。
