摘要：内部排序数据元素全部放在内存中的排序。希尔排序法的基本思想是先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。当到达时，所有记录在统一组内排好序。
本篇介绍的是排序算法，重点探讨前四种排序算法： 直接插入排序、希尔排序、直接选择排序和堆排序，关于冒泡排序、快排和归并排序我们下章再重点讨论。话不多收，我们直接开始。
排序在我们生活中随处可见，比如在我们购物的时候：
我们想看大学排名，也是要用到排序：
因为上面这8种排序算法在我们在校招中常被考到，所以我们重点讨论这8种，而对于其他的排序算法在我们校招中基本用不到，所以就不作为重点。
直接插入排序是一种简单的插入排序法，其基本思想是：
实际中我们玩扑克牌时，就用了插入排序的思想：
这张图片大家是不是很熟悉呢？这就是插入排序。
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
这个理解起来可能有点费脑：我们假设现在有一个升序数组：
int a[7] = {3, 5, 6, 7, 9 ,18}; 当我们在插入一个数据x = 2时，我们就依次从数组的最后一个数往前面比较，当找到比x小的数了，我们就停下
代码如下：
while (end >= 0){ if (a[end] > x) { a[end + 1] = a[end]; end--; } else { break; } //两个结束条件： //1.end < 0 or break; a[end + 1] = x;}这里是插入一个数据，而当数组不可能已从开始就是有序的，所以我们从依次从0开始插入。
比如现在有一个无序数组：
int a[] = {20, 0, 9, 5, 2, 7, 3, 8, 7, 3};现在用图片表示排序过程：
代码如下：
//直接插入排序//时间复杂度:最好O(N),最坏O(N^2)void InsertSort(int* a, int n){ //多趟排序 int i = 0; //将后一个数插入前面的数中,所以i的区间是[0,n-1] for(int i = 0; i < n - 1; i++) { //单趟排序：从最后一个数往前挪 int end = i; int x = a[i + 1]; while (end >= 0) { if (a[end] > x) { a[end + 1] = a[end]; end--; } else { break; } //两个结束条件： //1.end < 0 or break; a[end + 1] = x; } }}那么我们来调用下这个直接插入排序函数，看是否是正确的。
直接插入排序的特性总结：
问题？假设我们现在要排的数组是升序，而现在给我们的数组却是降序，那么越大的数就越在数组的前面，那么我们插入数据每次都要和x比，这样的话时间复杂度肯定是O(N^2),那么我们能不能将像这样的数组优化一下呢？答案是：希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
用图片表示就是：
相信大家看完这张图片也还是很懵的，我们一步一步来：
此时假设有一个数组：
int a[7] = {20, 9, 5, 2, 7, 3, 8, 7, 3}; 我们看到偏向前面的数据都比较大，而偏向后面的的数据都比较小。那么我们首先就先从gap = 4来排序：
第一步：假设现在还是先插入一个数据x
//单趟排序 while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } //两个结束条件： /*1.end < 0 or break;*/ a[end + gap] = x;此时我们插入一个数据后就是这样的图：
第二步：我们对其中的一组数据进行排序
代码如下：
for (int i = 0; i < n - gap; i += gap) { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = x; }第三步，我们进行预排序,警数组排成接近有序
代码如下：
for (int j = 0; j < gap; ++j) { for (int i = j; i < n - gap; i += gap) { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = x; } }此时我们已经将数组排成为了接近有序，而已经嵌套了3层循环。结构相对复杂，我们还有一种"一锅炖"的方法，先看代码：
//预排序：一锅炖，进行多组排序 for (int i = 0; i < n - gap; i++) { int end = i; int x = a[i + gap]; //单趟排序 while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } //两个结束条件： /*1.end < 0 or break;*/ a[end + gap] = x; }不知道大家能不能看懂，我们还是用一张图片来表示：
第四步：多次预排序，将数组排序成有序数组! !
//多次预排序(gap > 1) +直接插入 (gap == 1) while (gap > 1) { gap = gap / 2; //gap = gap / 3 + 1; //预排序：一锅炖，进行多组排序 for (int i = 0; i < n - gap; i++) { int end = i; int x = a[i + gap]; //单趟排序 while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } //两个结束条件： /*1.end < 0 or break;*/ a[end + gap] = x; } }此时我们在看最开始的那张流程图片，相信大家都能看懂了吧！
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
- 稳定性：不稳定
《数据结构(C语言版)》— 严蔚敏
《数据结构-用面相对象方法与C++描述》— 殷人昆
有很多人肯定会想，我感觉这个希尔排序也不怎么优啊！那么我们来实验一下，大家都能感受到希尔排序的优势了。
我们先测试10000个数据，排序要多久：
void Test1OP(){ srand((int)time(0)); const int N = 10000; //开辟空间 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); free(a1); free(a2);}
这里看起差距也不大。
我们不妨将数据改大一点：
此时我们看到希尔排序的优势所在了吧！
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
每次选出一个数效率太低了，我们现在优化一下这个算法，我们一次选出两个数，一个最大数和一个最小的数。
假设现在排升序，现在还是有一个数组
int a[] = {8, 9, 5, 2, 7, 3, 8, 7, 3};现在从这个数组中选出最小的数，放在开始位置，选出最大的数放在最后的位置
代码如下：
int mini = begin; int maxi = end; for (int i = begin; i <= end; i++) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } //将最小值交换到最前面，将最大值换到最后 Swap(&a[begin], &a[mini]); if (begin == maxi) { maxi = mini; } Swap(&a[end], &a[maxi]);此时我们就找一趟中找出了数组中的最小值和最大值，那么我们想要找出次小值和次大值就需要跑多躺，这必须就要控制我们的区间：
代码如下：
int begin = 0; int end = n - 1; while (begin < end) { //查找begin到end区间内的最小值和最大值的下标 int mini = begin; int maxi = end; for (int i = begin; i <= end; i++) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } //将最小值交换到最前面，将最大值换到最后 Swap(&a[begin], &a[mini]); Swap(&a[end], &a[maxi]); begin++; end--; }我们还是来检验一下结果是否正确：
结果正确。那么就这也太简单了吧！我们换一个数据试下：
int a[] = { 20, 9, 5, 2, 7, 3, 8, 7, 3 };
怎么换一组数据就不行了？我们还是画图来好检验：
通过画图我们很显然很快就发现了错误！那么我们该怎么改正呢？这里介绍一种方法：
//选择排序//时间复杂度：最好和最坏都是O(N^2)void SelectSort(int* a, int n){ assert(a); //定义两个下标begin和end控制区间 int begin = 0; int end = n - 1; while (begin < end) { //查找begin到end区间内的最小值和最大值的下标 int mini = begin; int maxi = end; for (int i = begin; i <= end; i++) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } //将最小值交换到最前面，将最大值换到最后 Swap(&a[begin], &a[mini]); if (begin == maxi) { maxi = mini; } Swap(&a[end], &a[maxi]); begin++; end--; }}那我们还是画图来看改正是否正确：
很显然画图是正确的，我们编译程序再看一下：
直接选择排序的特性总结：
这里时间复杂度为什么会是O(N^2)呢？有人会想如果是有序那不就是O(1)吗？千万不能这样想，如果你这样想的话不妨问一下如果每个排序排的都是升序，那我们还学这么多排序干嘛。这里的选择排序不管是最好的情况和最坏的情况都输 O(N^2)，因为就算排的是升序，还是要从前往后一个一个的遍历比较大小，选出最大的数和最小的数。而之前的插入排序最好的情况可能是O(N)，是因为如果排的是升序的话我们只需要和最后（下标为end）的数相比较，然后直接在最后插入，就不需要在往前面比较了。
此时我们也同样排10000个数据看一下：
void Test1OP(){ srand((int)time(0)); const int N = 10000; //开辟空间 int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; } //算出排序的时间 int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); SelectSort(a3, N); int end3 = clock(); //打印 printf
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/123918.html
摘要：本篇中主要讲的是字符串数组，复杂度要比单个字符串高一些。往往需要处理从各个地方过来的大量文本，不可避免会用到数组。用好数组，会让文本处理工作事半功倍。本篇只涉及数组的基础用法。数组定义数组可以直接赋值使用，不需要提前声明。 导读 了解完结构比较简单的字符串后，我们来看更复杂一些的数组。其实字符串在 zsh 中也可以当字符数组操作，但很少有需要把字符串当数组来处理的场景。本篇中主要讲的是...
摘要：前言由于写的文章已经是有点多了，为了自己和大家的检索方便，于是我就做了这么一个博客导航。 前言 由于写的文章已经是有点多了，为了自己和大家的检索方便，于是我就做了这么一个博客导航。 由于更新比较频繁，因此隔一段时间才会更新目录导航哦～想要获取最新原创的技术文章欢迎关注我的公众号：Java3y Java3y文章目录导航 Java基础 泛型就这么简单 注解就这么简单 Druid数据库连接池...
摘要：专题系列共计篇，主要研究日常开发中一些功能点的实现，比如防抖节流去重类型判断拷贝最值扁平柯里递归乱序排序等，特点是研究专题之函数组合专题系列第十六篇，讲解函数组合，并且使用柯里化和函数组合实现模式需求我们需要写一个函数，输入，返回。 JavaScript 专题之从零实现 jQuery 的 extend JavaScritp 专题系列第七篇，讲解如何从零实现一个 jQuery 的 ext...
摘要：标签在为一个地址附加参数时，将自动对参数值进行编码，例如，如果传递的参数值为中国，则将其转换为后再附加到地址后面，这也就是使用标签的最大好处。 什么是JSTL JSTL全称为 JSP Standard Tag Library 即JSP标准标签库。 JSTL作为最基本的标签库，提供了一系列的JSP标签，实现了基本的功能：集合的遍历、数据的输出、字符串的处理、数据的格式化等等！ 为什么要使...
摘要：原文发表于以太坊智能合约开发第五篇字符串拼接上一篇，我们实现了一个简单的智能合约。在文章最后抛出了一个问题如果我们事先在合约里定义好字符串，如何与变量进行字符串拼接在智能合约里进行字符串的拼接可不是一件简单的事情。 原文发表于：以太坊智能合约开发第五篇：字符串拼接—Solidity 上一篇，我们实现了一个简单的智能合约。用户输入什么字符串，合约就原样返回什么。在文章最后抛出了一个问题...
阅读 2050·2021-11-19 09:40
阅读 2427·2021-09-30 09:48
阅读 2462·2019-08-30 14:10
阅读 2614·2019-08-29 11:22
阅读 1731·2019-08-26 13:51
阅读 2144·2019-08-26 12:02
阅读 2228·2019-08-23 16:06
阅读 3414·2019-08-23 14:06
