java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述__49_97_38_13_65_

当前位置: 编程技术>java/j2ee

java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

来源: 互联网发布时间：2014-10-21

本文导语: 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法...

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。
一个算法应该具有以下五个重要的特征：
1.有穷性：一个算法必须保证执行有限步之后结束；
2.确切性：算法的每一步骤必须有确切的定义；
3.输入：一个算法有0个或多个输入，以刻画运算对象的初始情况；
4.输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
5.可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
合并排序（MERGE SORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。
例如数组A有7个数据，分别是： 49 38 65 97 76 13 27，那么采用归并排序算法的操作过程如图7所示：
初始值 [49] [38] [65] [97] [76] [13] [27]
看成由长度为1的7个子序列组成
第一次合并之后 [38 49] [65 97] [13 76] [27]
看成由长度为1或2的4个子序列组成
第二次合并之后 [38 49 65 97] [13 27 76]
看成由长度为4或3的2个子序列组成
第三次合并之后 [13 27 38 49 65 76 97]
图6 归并排序算法过程图
合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现，形式上较为简单,但实用性很差。
合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数
是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次，按照这一规律，当有N个子序列时可以推断出合并的次数是
X（2>=N,符合次条件的最小那个X）。
冒泡算法描述：
在解释冒泡排序算法之前，先来介绍把10个数（放在数组A中）中最大的那个数放在最后位置上的一种算法。算法描述如下：
（1）从数组A[1]到A[10]，把相临的两个数两两进行比较。即A[1]和A[2]比较，比较完后A[2]再与A[3]比较，……最后是A[9]和A[10]比较。
(2)在每次进行比较的过程中，如果前一个数比后一个数大，则对调两个数，也就是说把较大的数调到后面，较小的调到前面。比如在第一次的比较中，如果A[1]比A[2]大则A[1]和A[2]的值就互换。下图用6个数据来说明以上的算法。
假设6个数据是：A[]=5 7 4 3 8 6
A[1] A[2] A[3] A[4] A[5] A[6]
5 7 4 3 8 6 第一次，A[1]=5和A[2]=7比较，7>5，不进行对调。
5 7 4 3 8 6 第二次，A[2]=7和A[3]=4比较，449,两者交换，此时I：=3 )
进行第三次交换后： 27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找
进行第四次交换后： 27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )
此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：
初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序 {13} 27 {38}
结束结束 {49 65} 76 {97} 49 {65} 结束
结束
*************************************************************************
图6 快速排序全过程
快速排序的算法描述
1）、设有N（假设N=10）个数，存放在S数组中；
2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]