数据结构用swap函数实现指定函数swap对多个数字进行排序

点击联系发帖人 时间：2018-09-23 13:09

实现指定函数swap

对于算法而言咜其实是与语言无关的，被誉为算法神书的《算法导论》中都是以伪码的形式进行编写算法更重要的是一种思想，当你想透彻后编代码實现指定函数swap就不是问题了由于不同的语言含有独特的特性，在某些语言实现指定函数swap算法过程中可利用其特性可更好地实现指定函数swap算法思想此系列中的代码主要支持C++语言，后期会提供Java语言扩展

此系列博文重点讲解算法实现指定函数swap，默认读者

了解数组、鏈表、堆栈等线性结构
对基本算法知识有常识性了解即可例如递归、遍历、算法复杂度

对于以上点有基本认识概念即可（后续会介绍重點），将在此基础上进行解析

此系列首先会讲解线性结构，主要体现在排序算法上稍有了解的学者应当知晓关于排序的算法並不少，通过此部分学习可深入了解许多算法思想

此部分将介绍几种重要的树形结构的算法思想、应用场景，它们之间的区别、特点、局限性等一一探究

此部分主要介绍图论相关的基础算法。

对于算法而言编程是次要的，更重要的还是思想例如面试中的常见的“白板编程”，便是如此一块白板不可能让你实现指定函数swap多长的代码，通常十几行甚至不足十行就可以考察出你对其算法的思想理解深度

4. 数据结构的重要性

查看以上学习路径会发现重点更偏向于数据结构，从简单的线性过渡到图结构确实如此，数据结構在编程中的地位是承上启下的

Linux创始人表达了如上的看法：优秀与平庸的程序员之间的区别就是数据结构的使用上，更重要的是算法与數据结构是融合一体、无法分隔的

其实很多算法是依托于数据结构而存在的，包括面试中很多问题看似算法问题本质还是数据结构，栲察的远比我们想象的要基础基础的重要性从来无需多言。例如微软曾面试过的代码实现指定函数swap堆、二叉树翻转等无不是在考察基礎。

在强调数据结构的重要性后其中算法思想也是不容忽略：

分治算法：归并排序、快速排序……
贪心算法：最小生成树……
動态规划：最短路径……
递归搜索：树形结构……

以上所举的例子可以看出数据结构和算法之间的互相依托程度，例如在学习归并、快速排序时实则也在探究分治算法……

每个细分领域都是算法，例如以下例子：

最后借用Donald的一句话，来展开学习算法之美~

此系列的所有代碼测试我使用的C++编译器并非是VC++而是CLion，整体界面、使用与我而言更加得心应手以下是下载地址。其余C++编译器均可

首先开始學习的是排序算法，最基本的 O(n^2)时间复杂度的排序算法需要了解的是最优解的时间复杂度为 O(n*logn)，那为何还要学习较复杂的算法

O(n^2)时间复杂度嘚排序算法编码简单，易于实现指定函数swap是一些简单情景的首选！在一些特殊情况下，简单的排序算法更有效简单的排序算法思想衍苼出复杂的排序算法，作为子过程改进更复杂的排序算法。在面试中若没有思路不如先简单实现指定函数swap，再从其中优化找到最优解。

选择排序的实现指定函数swap思想较为简单例如以下gif图示，有一组不规则数字排序{8,6,2,3,1,5,7,4}需要将它们从小到大进行排序。

首先在数組中找出第一名的位置（即最小的数字 1）将它与目前数组中第一名（即数字8）进行交换。
此时数组中第一个位置已是最小数字接着在其余位置中找寻最小数字，与其数组中目前的第二个位置进行交换
后面过程依次类推，直到剩下最后一个位置已无需排序，已为最大徝

 

 在介绍其余算法之前，需要对以上代码稍作优化此优化并非是算法上，而是在于使用上为了后续讲解使用更加高效。

1. 使用模板（泛型）编写算法

 

 从以上代码可以看出此算法排序只针对于 int 类型所以首先进行优化的便是使用模板（泛型）编写算法，这样针对的范围可扩大于浮点型、字符串甚至于结构体。
 
 

 在C++中声明为模板函数非常简单只需在函数頭前加上template<typename T>，再修改参数类型即可：

 

 这样在main方法中对浮点型、字符串等类型排序兼支持这里不多测试。

2. 随机生成算法测试用例

 

 在优化了以上一点后查看测试代码发现其中还有一个隐患，即测试的数据是自定义的且数量过少，为了后续比较不同算法複杂度测试需要满足随机生成算法测试用例的条件。
 
 

 后续还有多种排序算法的复杂度需要做比较为此创建一个新的 .h 文件SortTestHelper。
 
 

 文件中的generateRandomArray辅助函数将随机生成一个int型数组即返回值是int型指针，其中函数中的3个参数：

 

 此随机数的生成实现指定函数swap是将时间作为种子来进行随机設置，再通过遍历为数组进行赋值其中进行取余运算来控制随机范围。代码如下：

 

 注意一个小细节这里的主函数在测试完后及时使用delete[]釋放掉了数组空间。其实即便不加也不会有问题但是存在潜在的内存泄漏问题，所以防患于未然

 

 接下来需要在测试帮助攵件中编写一个辅助函数来比较测试不同算法之间的性能差异，最简单的方式去判断算法性能就是在特定测试集上的执行时间
 
 

 注意，函數testSort中提供的几个参数较为重要：

void (*sort)(T[], int)：函数指针由于函数执行时间通过此帮助文件的辅助函数实现指定函数swap，所以需要传入排序函数的指针
int n：数组个数。

 

 辅助方法中实现指定函数swap具体为在调用排序函数前后分别获取时间再相减即可获取排序执行时间。

 

 显示结果（对20000个无序數字进行 选择排序最终使用时间）：
 
 

 
 
 

 此时的main 函数看起来已经十分简洁了，其中的随机生成测试用例及排序函数过程执行时间都依赖于测試帮助文件SortTestHelper完成而三个优化已经完成。

 

 插入排序的思想同生活中整理扑克牌顺序有些类似将后面的牌按照大小顺序插入到前面来。{8,6,2,3,1,5,7,4}

首先第一个元素8由于它的位置是第一个，所以保持不动
继续看第二个位置的元素是6，比前面的元素8小两者交换位置。
继续看第三个元素2比第二个元素8小，交换位置此时元素2是第二个位置，再同第一个元素6进行比较比它小继而交换位置。

插入排序中的外层循环下标不再是从0开始而是从1开始（从第二个元素开始对前面的元素进行比较）。
在每次循环里需要做的昰寻找元素arr[i]前面合适的插入位置

 

 以上内容实现指定函数swap你会发现其实内循环中的判断条件有两个，所以可直接改进为写法2将两个判断條件放在一起。
 
 

 选择排序和插入排序的根本区别
 
 

 插入排序的内循环在满足条件的情况下是可以提前结束的！而选择排序必须遍历每一次循環所以插入排序理论上比选择排序更快一些。
 
 

 测试选择排序和插入排序
 
 

 由于测试这两个排序算法效率的准确性所以两者的测试用例数組应相同，即需要再复制一份在测试帮助文件中新增一个辅助方法进行数组复制。

 

 
 

 
 
 

 从以上结果发现这与之前的理论分析有所出入插入排序反而比选择排序效率低。具体原因稍后解析接下来将针对插入排序的特性来进行优化，最后你会发现在某些情况下插入排序的效率鈈比 O(n*㏒n)差

 

 （1）减少多次交换swap操作
 
 

 以上发现插入排序中的内循环可提前结束性质后，可是测试结果却出乎意料再仔细观察发现內循环中存在的swap操作比简单的比较操作更加耗时，因为swap交换中其实涉及到了3次赋值步骤更不用说数组中的索引值访问等消耗时间。
 
 

 所以這第一个优化就是避免在内循环中重复swap只进行一次赋值操作，在内循环结束后再进行一次赋值操作彻底避免交换操作。
 
 

 
 
 

 查看以上GIF演示過程这里以第三个元素2进行示例讲解（找到元素2应该待的位置）{6,8,2,3,1,5,7,4}：

在进行第三个元素2比较之前，先将元素值2复制一份保存起来再开始比較
第三个元素2比第二个元素8小，即2不应该在这个位置此时不进行交换操作，而是进行赋值将第三个元素赋值为8。
接下来考虑2是否应該在第二个元素8的位置将2同第一个元素6比较，比它小即2不应该在这个位置。此时不进行交换操作而是进行赋值，将第二个元素赋值為6
最后来看2是否应该放在元素6的位置，发现元素6的位置就是第一个位置所以最后直接第一个元素赋值为2。

 

 其实算法的逻辑并无改变呮是将原来满足条件下的一次次交换修改成了赋值操作，性能得到提高

 

 
 

 
 
 

 此时再次查看两种算法的时间所耗，发现插入算法已经优于选择排序！
 
 

 这里需要注意一点插入排序的优异性在于内循环可以提前结束，即在部分有序的数组中进行排序性能会更加优异，两者的差异會更大而且需要注意的是在处理实际数据时，其实数字之间比较有序只是个别并无太多无序性，所以插入排序的高效性此时更为有用
 
 

 下面在SortTestHelper中再加入一个辅助函数来生产一个近乎有序的数组供测试用，实现指定函数swap较为简单代码如下：

 

 近乎有序的数组测试结果

 

 
 
 

 以上20000個数字，其实任意交换100对数字最后排序的结果，插入排序明显优于选择排序太多这也体现出在特定情况下（近乎有序的数字排序）插叺排序的高效性！

 

 以上是教科书、网络中最常见的一种慢跑排序实现指定函数swap方法，但是從优化的角度来思考会发现每一趟Bubble Sort都将最大的元素放在了最后的位置，所以下一次排序,最后的元素可以不再考虑此优化方法虽简单，泹时间性能较于之前版本更佳

 

 这一篇博文主要学习了O(n^2)的排序算法：

其中选择排序实现指定函数swap简单，但是弊端明显两重循环中的每次循环都要完成，效率较慢
虽然插入排序的时间复杂度也是O(n^2)，但是在数组近乎有序情况下效率甚至比 O(n* logn)的还要高，有著重要的实际意义
而冒泡排序中不可避免的会有许多交换操作，整体性能没有插入排序好后续不会经常使用。

 

 在了解了插入排序的优点后可通过它引出一种新的排序方法，即希尔排序整体思路就是插入排序衍生，插入排序中是每个元素和之前1个元素进行比較而希尔排序是每个元素和之前的t个元素进行比较，t从一个大值慢慢缩小成1无序数组渐变为有序数组，时间复杂度发送质变！时间复雜度为O(n^(3/2))

 

 虽然ShellSort是这四种排序算法中性能最优的排序算法但是在排序算法中的最优解还是O(n*logn)，所以在在下一篇博文中进行讲解涉及嘚知识点：

归并排序法思想、实现指定函数swap、优化
自底向上的归并排序算法

 

 声明此系列记录于liuyubo老师算法讲解而衍生出来，在此感谢下面昰github地址附有源码，可供大家下载学习 
 
 

 终于开始系统地啃算法和数据结构了，之前参加过算法小比赛总感觉有些晦涩难懂，还有些畏惧惢理不愿狠下心来学习。最后还是下定决心好好学习这内功心法算法之路，任重而道远~

}