原创《论排序算法效率》：关于免费算法效率论文范文在这里免费下载与阅读,为您的算法效率相关论文写作提供资料。
[摘 要] 排序算法是计算机设计中常用的解决问题的方法,常见的有冒泡法、选择法、插入法、归并法和快速法等.对于这些排序算法,各自有何种优势和缺陷?又分别适用于什么情况?搞懂这些问题对于我们进行程序设计和优化都具有十分重要的意义.本文主要通过对上述五种排序算法的剖析,分别对其效率进行研究和讨论.
[关键词] 排序算法；程序设计；冒泡法；插入法；快速法
doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2018. 05. 067
[中图分类号] TP301.6 [文献标识码] A [文章编号] 1673 - 0194（2018）05- 0162- 03
0 引 言
在计算机程序设计中,排序算法是一种被广泛用于解决实际问题的重要方法.排序的目的在于帮助程序设计者提高查找、插入和删除的效率,使编程过程变得相对简单化和便捷化.随着当前计算机及网络技术的高度发展,以及计算机程序在各个应用领域的大力推广,基于计算机硬件存储空间和运行速度的局限性,进一步突出了提高计算机运行速度和节省存储空间的重要性,因此它也成为今后软件设计人员共同努力和追求的方向.如何解决上述问题,其视角和思路并不唯一,但目前程序设计人员已将排序算法视为一个重要的因素,因为我们所选择的排序算法将直接影响程序的执行效率和它对计算机硬件存储空间的占用额,不仅决定了整个软件的综合性能,还会影响整个计算机系统的运行效率.
所谓排序算法,即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序,这种新序列遵循着一定的规则,体现出一定的规律,因此,经处理后的数据便于筛选和计算,大大提高了计算效率.对于排序,我们首先要求其具有一定的稳定性,即当两个相同的元素同时出现在某个序列之中,则经过一定的排序算法之后,两者在排序前后的相对位置不发生变化.换言之,即便是两个完全相同的元素,它们在排序过程中也是各有区别的,不允许混淆不清.
1 计算机程序设计中常见的排序算法
目前计算机程序设计中出现的排序算法已不单一,而是呈现出多样化的前景,比如有冒泡排序法、选择排序法、插入排序法、归并排序法和快速排序法等多种形式.
1.1 计算机程序设计中的冒泡排序算法
冒泡排序算法是把较小的元素往前调或者把较大的元素往后调.这种方法主要是通过对相邻两个元素进行大小的比较,根据比较结果和算法规则对该二元素的位置进行交换,这样逐个依次进行比较和交换,就能达到排序目的.冒泡排序的基本思想是,首先将第1个和第2个记录的关键字比较大小,如果是逆序的,就将这两个记录进行交换,再对第2个和第3个记录的关键字进行比较,依次类推,重复进行上述计算,直至完成第（n-1）个和第n个记录的关键字之间的比较；此后,再按照上述过程进行第2次、第3次排序,直至整个序列有序为止.排序过程中要特别注意的是,当相邻两个元素大小一致时,这一步操作就不需要交换位置,因此也说明冒泡排序是一种严格的稳定排序算法,它不改变序列中相同元素之间的相对位置关系.
1.2 计算机程序设计中的选择排序算法
选择排序算法的基本思路是为每一个位置选择当前最小的元素.选择排序的基本思想是,基于直接选择排序和堆排序这两种基本的简单排序方法,首先从第1个位置开始对全部元素进行选择,选出全部元素中最小的给该位置；再对第2个位置进行选择,在剩余元素中选择最小的给该位置即可；以此类推,重复进行“最小元素”的选择,直至完成第（n-1）个位置的元素选择,则第n个位置就只剩唯一的最大元素,此时不需再进行选择.使用这种排序时,要注意其中一个不同于冒泡法的细节,举例说明：序列5 8 5 3 9,我们知道第一遍选择第1个元素“5”会和元素“3”交换,那么原序列中的两个相同元素“5”之间的前后相对顺序就发生了改变.因此,我们说选择排序不是稳定的排序算法,它在计算过程中会破坏稳定性.
1.3 计算机程序设计中的插入排序算法
插入排序算法是基于某序列已经有序排列的情况下,通过一次插入一个元素的方式按照原有排序方式增加元素.这种比较是从该有序序列的最末端開始执行,即要插入序列中的元素最先和有序序列中最大的元素比较,若其大于该最大元素,则可直接插入最大元素的后面即可,否则再向前一位比较查找直至找到应该插入的位置为止.插入排序的基本思想是,每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中,寻找最适当的位置,直至全部记录插入完毕.执行过程中,若遇到和插入元素相等的位置,则将要插入的元素放在该相等元素的后面,因此插入该元素后并未改变原序列的前后顺序,我们认为插入排序也是一种稳定的排序方法.插入排序分直接插入排序、折半插入排序和希尔排序3类.
1.4 计算机程序设计中的归并排序算法
归并排序算法就是把序列递归划分成为一个个短序列,以其中只有1个元素的直接序列或者只有2个元素的序列作为短序列的递归出口,再将全部有序的短序列按照一定的规则进行排序为长序列.归并排序融合了分治策略,即将含有n个记录的初始序列中的每个记录均视为长度为1的子序列,再将这n个子序列两两合并得到n/2 个长度为2（当n为奇数时会出现长度为1的情况）的有序子序列；将上述步骤重复操作,直至得到1个长度为n的有序长序列.需要注意的是,在进行元素比较和交换时,若两个元素大小相等则不必刻意交换位置,因此该算法不会破坏序列的稳定性,即归并排序也是稳定的排序算法.
1.5 计算机程序设计中的快速排序算法
快速排序算法的基本思想是通过分解、求解和合并这3个主要步骤来计算和排序.具体而言,当我们要对一个序列R进行排序时：第一步要先分解,即在R中任选一个记录作为基准,以此基准为界将R一分为二,即左、右两个子区间,前者中的记录均小于基准,后者中的记录均大于基准；第二步要求解,即对这两个区间快速排序；第三步就是合并,对上述两个分别完成排序的子区间进行合并,即完成整体的排序.快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和右侧子区间元素交换的时刻.
算法效率论文参考资料：
结论：论排序算法效率为关于对写作算法效率论文范文与课题研究的大学硕士、相关本科毕业论文算法效率函数图像论文开题报告范文和相关文献综述及职称论文参考文献资料下载有帮助。
