[排序算法分析与实现] 十大排序算法

时间：2019-01-29 03:26:42　来源：雅意学习网本文已影响人

　　关键词：排序算法比较C程序　　摘要：针对排序问题采用四种方法：冒泡法、选择法、快速法和插入法进行算法分析，并分别通过C语言实现。　　　　排序是计算机程序设计中最重要的研究问题之一，是数据处理领域经常使用的一种运算。对于搜索大型数据库来说，对信息进行排序的算法至关重要［1］。例如新生入学都会有相应的学号，以便于今后的管理；用字典或电话号码本查找信息比较容易和方便，是因为其中的信息都按字母表的顺序排了序。排序是一种非常有用的技术，由于它在理论上的重要性，2000年被列为对科学和工程计算的研究与实践影响最大的十大问题之一［2］。
　　一、排序的基本概念
　　1.排序的定义
　　所谓排序，就是整理文件中的记录，使之按关键字递增（或递减）次序排列起来。其确切的定义如下：
　　输入：n个记录R1，R2，…，Rn，其相应的关键字为K1，K2，…，Kn。
　　输出：Ri1，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin（或Ki1≥Ki2≥…≥Kin）。
　　当待排序记录的关键字均不相同时，排序的结果是唯一的，否则排序结果不唯一［3］。
　　2.排序的类型
　　按是否涉及数据的内、外存交换进行划分，可分为内部排序和外部排序两种：在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，称之为内部排序（简称内排序）；反之，称为外部排序［3］。对于内部排序，按算法的不同又可分为：插入排序、选择排序、交换排序、归并排序和分配排序五类。
　　下面就几种常用的排序算法――冒泡法、选择法、快速法和插入法展开讨论。
　　二、算法分析
　　1.冒泡法
　　（1）基本思想
　　依次比较相邻的两个数，将小数放在前面，大数放在后面。好比是气泡，轻的往上升，重的往下沉，故称作冒泡排序。
　　（2）实现步骤
　　假设N个数要从小到大排序：
　　（1）对N个数进行第一遍扫描，将相邻的两个数进行比较，比较N-1次后，最大的数到了最后；（2）将剩余N-1个数进行第二遍扫描，比较N-2次，“次大”的数将到倒数第二的位置；（3）同理N-2个数进行第三遍扫描，比较N-3次。
　　由此得出N个数将需要扫描N-1遍，每遍扫描需要经过N-i（i=1，2，3，…）次比较。过程示例见图1。
　　2.选择法
　　（1）基本思想
　　每一趟从待排序的数组元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
　　（2）实现步骤
　　假设初始状态：无序区为R［1..n］（N个数），有序区为空
　　（1）第一遍扫描，将相邻的两个数进行比较，选择最小值与第1个数交换，这样有序区记录个数增1，无序区记录个数减1。（2）第i遍扫描：若当前有序区和无序区分别为R［1..i-1］和R（1≤i≤n-1），从当前无序区中选出最小值与无序区的第1个记录交换。
　　由此得出，N个数选择排序需经过N-1遍扫描，每遍扫描需要经过N-i（i=1，2，3，…）次比较；每遍扫描选择其中最小的与无序区的第一个记录交换。过程示例见图2。
　　3.快速法
　　（1）基本思想
　　采用分治法的思想，即将原问题划分为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
　　（2）实现步骤
　　①分解：在R中任选一个记录作为基准（Pivot），以此基准将当前无序区划分为左、右两个较小的子区间R［low..pivotpos-1］和R［pivotpos+1..high］，并使左边子区间中所有记录值小于等于基准记录，右边的子区间中所有记录值均大于等于，而基准记录则位于正确的位置上，无需参加后续的排序。
　　过程示例见图3：图（a）、（b）表示归并过程，即小于基准值的数靠左，大于基准值的数靠右；当左右执行标号合并到一个位置时，即为基准值的位置，如图（c）所示，并将无序区分为左右两个。
　　②通过递归调用快速排序，也就是继续采用步骤①的方法对左右子区间快速排序。
　　把以上排序结果组合起来就得到全部元素的排序结果。
　　4.插入法
　　（1）基本思想
　　假定待排序的记录存放在数组R［1..n］中，初始时，R［1］自成1个有序区，无序区为R［2..n］。从i=2起直至i=n，依此将R［i］插入到当前的有序区R［1..i-1］中，生成含n个记录的有序区。
　　（2）实现步骤
　　将待插入值R［i］从右向左依此与有序区中的值R［j］（j=i-1,i-2，…,1）进行比较：①若R［j］大于R［i］，则将R［j］后移一个位置；②若R［j］小于或等于R［i］，则查找过程结束。比R［i］大的值均已后移，所以j+1的位置已经腾空，j+1即为R［i］的插入位置。
　　过程示例见图4。
　　三、程序实现
　　1.冒泡排序（Bubble Sort）
　　void Bubble Sort（int a［］,int n）
　　{ int i,j,t；
　　 for（j=1；ja［i+1］）{t=a［i］；a［i］=a［i+1］；a［i+1］=t；}
　　}
　　2.选择排序（Selection Sort）
　　voidSelectSort（int a［］,int n）
　　{ inti,j,min,t；
　　 for（j=1；ja［i］）min=i；
　　 t=a［j-1］；a［j-1］=a［min］；a［min］=t； }
　　}
　　3.快速排序（QuickSort）
　　void QuickSort（int a［］,int low,int high）
　　{ intmiddle；
　　 if（low>high） return；
　　 middle=split（a,low,high）；
　　 QuickSort（a,low,middle-1）；
　　 QuickSort（a,middle+1,high）；
　　}
　　int split（int a［］,int low,int high）
　　{ int part_element=a［low］；
　　 for（；；）
　　 { while（low=high）break；
　　 a［low++］=a［high］；
　　 while（low=high）break；
　　 a［high--］=a［low］；
　　 }
　　 a［high］=part_element；
　　 return high；
　　} ［4］
　　4.插入排序（Insertion Sort）
　　void InsertSort（int a［］,int n）
　　{ int i,j,k,t；
　　 for（j=1；j 本文为全文原貌未安装PDF浏览器用户请先下载安装原版全文

推荐访问:算法排序分析

[排序算法分析与实现] 十大排序算法

最新文章

热门文章