排序算法简介(软考)

《排序算法简介(软考)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构和算法选择排序选择排序分为简单选择排序，堆排序简单选择排序：从元素中寻找最小的元素，将它和第一位替换，依次类推堆排序首先知道什么是堆，堆是一颗二叉树，是满足什么条件的二叉树呢？但Ki<=K2i，Ki<=K2i+1或者Ki=>K2i，Ki=>K2i+1Eg:对46,79,56,38,40,84建立一个大顶堆，求初始堆首先建立完全二叉树，插入规则是按层次遍历插入调整二叉树，使其符合堆的规则，一半从n/2的元素开始交换排序交换排序分为冒泡排序，快速排序57685952从小到大排序冒泡排序快速排序快速排序（Quicksort

2、）是对冒泡排序的一种改进。由C.A.R.Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。　　初始状态{49386597761327}　　进行一次快速排序之后划分为{273813}49{769765}分别对前后两部分进行快速排序{273813}经第三步和第四步交换后变成{132738}完成排序。{769765}经第三步和第四步交换后变

3、成{657697}完成排序。//参照《数据结构》（C语言版）　　//调用：quicksort-->qsort-->partitions　　intpartitions(inta[],intlow,inthigh)　　{　　intpivotkey=a[low];　　//a[0]=a[low];　　while(low=pivotkey)　　--high;　　a[low]=a[high];　　while(low

4、+low;　　a[high]=a[low];　　}　　//a[low]=a[0];　　a[low]=pivotkey;　　returnlow;　　}　　voidqsort(inta[],intlow,inthigh)　　{　　intpivottag;　　if(low

5、ntn)　　{　　qsort(a,0,n);　　}　　//简单示例　　#include　　//#include　　#include"myfunc.h"//存放于个人函数库中　　main()　　{　　inti,a[11]={0,11,12,5,6,13,8,9,14,7,10};　　for(i=0;i<11;printf("%3d",a[i]),++i);　　printf("");　　quicksort(a,10);　　for(i=0;i<11;printf("%3d",a[i]),++i

6、);　　printf("");　　}归并排序归并排序故名思意就是合并起来在进行排序。他的基本思路是这样的；首先：先将所有的元素都看成有序序列，将这些序列两两合并生成一个长度为2/n的新有序序列，随后再进行归并，再排序。Eg：5768595272289633[5768][5952][7228][9633]比较得到[5768][5259][2872][3396]合并得到[57685259][28723396]比较得到[52575968][28337296]依次类推……基数排序设待排序文件各记录的关键字为288，371，260

7、，531，287，235，56，299，18，23。这时r=10,d=3。进行3趟分配和3趟收集。排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。不明白参考下面的具体实例：“基数排序法”（radixsort）则是属于“分配式排序”（distributionsort），基数排序法又称“桶子法”（bucketsort）或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m)，其中r为所采取的基数，而m

8、为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。解法基数排序的方式可以采用LSD（Leastsgnificantdigital）或MSD（Mostsgnificantdigital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。LSD的基数排序适用于