很多朋友是以谭浩强老师编的《c语言教程》作为学习c语言的入门教程的。书中涉及排序问题一般都以“冒泡法”和“选择法”实现。为了扩大视野,增加学习编程的兴趣,我参阅了有关书籍,整理了几种排序法,写出来同大家共勉。
让我们先定义一个整型数组a[n],下面用五种方法对其从小到大排序。
(1)“冒泡法”
冒泡法大家都较熟悉。其原理为从a[0]开始,依次将其和后面的元素比较,若a[0]>a,则交换它们,一
冒泡法原理简单,但其缺点是交换次数多,效率低。
下面介绍一种源自冒泡法但更有效率的方法“选择法”。
2)“选择法”
选择法循环过程与冒泡法一致,它还定义了记号k=i,然后依次把a[k]同后面元素比较,若a[k]>a[j],则使k=j.最后看看k=i是否还成立,不成立则交换a[k],a,这样就比冒泡法省下许多无用的交换,提高了效率。
选择法比冒泡法效率更高,但说到高效率,非“快速法”莫属,现在就让我们来了解它。
(3)“快速法”
快速法定义了三个参数,(数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素(一般为a[(i+j)/2],即中间元素)作为参照,把比它小的元素放到它的左边,比它大的放在右边。然后运用递归,在将它左,右两个子数组排序,最后完成整个数组的排序。下面分析
(4)“插入法”
插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序,再依次把后面的元素插入适当
5)“shell法”
shell法是一个叫shell 的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序,再缩
6)希尔排序
算法思想简单描述:
在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为
增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成
几种排序算法的比较和选择
1. 选取排序方法需要考虑的因素:
(1) 待排序的元素数目n;
(2) 元素本身信息量的大小;
(3) 关键字的结构及其分布情况;
(4) 语言工具的条件,辅助空间的大小等。
小结:
(1) 若n较小(n <= 50),则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多,因而当记录本身信息量较大时,用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。
(3) 若n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的n个关键字随机分布时,任何借助于"比较"的排序算法,至少需要O(nlog2n)的时间。
(5) 当记录本身信息量较大时,为避免耗费大量时间移动记录,可以用链表作为存储结构。
排序演示:
插入排序演示过程:https://www.sodocs.net/doc/b212647598.html,/course_ware/data_structure/web/flashhtml/insertsort.htm
直接选择排序演示过程::https://www.sodocs.net/doc/b212647598.html,/course_ware/data_structure/web/flashhtml/zhijiexuanze.htm
冒泡排序演示过程::https://www.sodocs.net/doc/b212647598.html,/course_ware/data_structure/web/flashhtml/maopaopaixu.htm 快速排序演示过程::https://www.sodocs.net/doc/b212647598.html,/course_ware/data_structure/web/flashhtml/kuaisupaixu.htm
堆排序演示过程::https://www.sodocs.net/doc/b212647598.html,/course_ware/data_structure/web/flashhtml/duipaixu.htm
基数排序演示过程::https://www.sodocs.net/doc/b212647598.html,/course_ware/data_structure/web/flashhtml/jishupaixu.htm
桶排序演示过程::https://www.sodocs.net/doc/b212647598.html,/course_ware/data_structure/web/flashhtml/tongpaixu.htm
归并排序演示过程::https://www.sodocs.net/doc/b212647598.html,/course_ware/data_structure/web/flashhtml/guibingpaixu.htm
C语言几种常见的排序方法 2009-04-2219:55 插入排序是这样实现的: 首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表")。 从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态。 重复2号步骤,直至原数列为空。 插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现。它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的: 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。 重复2号步骤,直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法。 选择排序 选择排序是这样实现的: 设数组内存放了n个待排数字,数组下标从1开始,到n结束。 i=1 从数组的第i个元素开始到第n个元素,寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n-1算法结束,否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始,我们要接触高效排序算法了。实践证明,快速排序是所有排序算法中最高效的一种。它采用了分治的思想:先保证列表的前半部分都小于后半部分,然后分别对前半部分和后半部分排序,这样整个列表就有序了。这是一种先进的思想,也是它高效的原因。因为在排序算法中,算法的高效与否与列表中数字间的比较次数有直接的关系,而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了,大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同,它是这样的: 首先新建一个空列表,作用与插入排序中的"有序列表"相同。 找到数列中最大的数字,将其加在"有序列表"的末尾,并将其从原数列中删除。 重复2号步骤,直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高(因为有堆这种数据结构以及它奇妙的特征,使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度,维护需要logn的时间复杂度),但是实现相对复杂(可以说是这里7种算法中比较难实现的)。
C语言9种常用排序法 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.带哨兵的直接插入排序 9.基数排序 例子:乱序输入n个数,输出从小到大排序后的结果1.冒泡排序 #include for(i=0;i int i, j, n, a[100], t, temp; while(scanf("%d",&n)!=EOF) { for(i=0;i 一、设计思想 插入排序:首先,我们定义我们需要排序的数组,得到数组的长度。如果数组只有一个数字,那么我们直接认为它已经是排好序的,就不需要再进行调整,直接就得到了我们的结果。否则,我们从数组中的第二个元素开始遍历。然后,启动主索引,我们用curr当做我们遍历的主索引,每次主索引的开始,我们都使得要插入的位置(insertIndex)等于-1,即我们认为主索引之前的元素没有比主索引指向的元素值大的元素,那么自然主索引位置的元素不需要挪动位置。然后,开始副索引,副索引遍历所有主索引之前的排好的元素,当发现主索引之前的某个元素比主索引指向的元素的值大时,我们就将要插入的位置(insertIndex)记为第一个比主索引指向元素的位置,跳出副索引;否则,等待副索引自然完成。副索引遍历结束后,我们判断当前要插入的位置(insertIndex)是否等于-1,如果等于-1,说明主索引之前元素的值没有一个比主索引指向的元素的值大,那么主索引位置的元素不要挪动位置,回到主索引,主索引向后走一位,进行下一次主索引的遍历;否则,说明主索引之前insertIndex位置元素的值比主索引指向的元素的值大,那么,我们记录当前主索引指向的元素的值,然后将主索引之前从insertIndex位置开始的所有元素依次向后挪一位,这里注意,要从后向前一位一位挪,否则,会使得数组成为一串相同的数字。最后,将记录下的当前索引指向的元素的值放在要插入的位置(insertIndex)处,进行下一次主索引的遍历。继续上面的工作,最终我们就可以得到我们的排序结果。插入排序的特点在于,我们每次遍历,主索引之前的元素都是已经排好序的,我们找到比主索引指向元素的值大的第一个元素的位置,然后将主索引指向位置的元素插入到该位置,将该位置之后一直到主索引位置的元素依次向后挪动。这样的方法,使得挪动的次数相对较多,如果对于排序数据量较大,挪动成本较高的情况时,这种排序算法显然成本较高,时间复杂度相对较差,是初等通用排序算法中的一种。 选择排序:选择排序相对插入排序,是插入排序的一个优化,优化的前提是我们认为数据是比较大的,挪动数据的代价比数据比较的代价大很多,所以我们选择排序是追求少挪动,以比较次数换取挪动次数。首先,我们定义我们需要排序的数组,得到数组的长度,定义一个结果数组,用来存放排好序的数组,定义一个最小值,定义一个最小值的位置。然后,进入我们的遍历,每次进入遍历的时候我们都使得当前的最小值为9999,即认为每次最小值都是最大的数,用来进行和其他元素比较得到最小值,每次认为最小值的位置都是0,用来重新记录最小值的位置。然后,进入第二层循环,进行数值的比较,如果数组中的某个元素的值比最小值小,那么将当前的最小值设为元素的值,然后记录下来元素的位置,这样,当跳出循环体的时候,我们会得到要排序数组中的最小值,然后将最小值位置的数值设置为9999,即我们得到了最小值之后,就让数组中的这个数成为最大值,然后将结果数组result[]第主索引值位置上的元素赋值为最小值,进行下一次外层循环重复上面的工作。最终我们就得到了排好序的结果数组result[]。选择排序的优势在于,我们挪动元素的次数很少,只是每次对要排序的数组进行整体遍历,找到其中的最小的元素,然后将改元素的值放到一个新的结果数组中去,这样大大减少了挪动的次序,即我们要排序的数组有多少元素,我们就挪动多少次,而因为每次都要对数组的所有元素进行遍历,那么比较的次数就比较多,达到了n2次,所以,我们使用选择排序的前提是,认为挪动元素要比比较元素的成本高出很多的时候。他相对与插入排序,他的比较次数大于插入排序的次数,而挪动次数就很少,元素有多少个,挪动次数就是多少个。 希尔排序:首先,我们定义一个要排序的数组,然后定义一个步长的数组,该步长数组是由一组特定的数字组成的,步长数组具体得到过程我们不去考虑,是由科学家经过很长时间计算得到的,已经根据时间复杂度的要求,得到了最适合希尔排序的一组步长值以及计算几种排序算法的分析与比较--C语言
C语言的四种排序