数据结构的排序算法

2、cclassDirectInsertSort:IAction5.6.{7・8・4regionIAction成员9・publicvoidAction()10.{11・int[]array=Program・RanaomArray();12・for(inti=l;Karray・Length;i+十)13・{14.if(array[i]=0&&tem

3、22・array[j+l]=tem;23・}24・}25.}26・tendregion27.}直接选择排序(StraightSelectionSort)(一)直接选择排序算法的思想:n个记录的文件的直接选择排序可以通过n-1次直接选择排序完成排序。1、初始状态：有序区为空，S[1...n]为无序区。2.第一趟选择排序：从S[1...n]无序区中选择最小的关键字S[k],与S[1]进行交换，完成第一趟排序，然后将S[1]作为新的有序区，S[2..n]作为新的无序区.3.第i趟排序，当前有序区和无序区分别为:S[1...i-1]sS[i...n]o该

4、趟排序从当前无序区中选出关键字最小的记录S[m],将它与无序区中的第一个元素进行交换，使S[1...・i]和S[i+1...n]为新的有序区和无序区。4、重复上述步骤，直到文件中所有的记录排序完成。1privateintQSelectSort(intDlist)2{3intij,k;4for(i=1;i

5、最小关键字的位置。12}13if(k!=i)//当前位置不同则交行14{15inttemp=list[i];16list[i]=list[k];17list[k]=temp;18}19}20}21returnlist;(三)算法分析：1、关键字比较分析：无论关键字的顺序如何，在第i趟排序中选出最小关键字，需做n-i次比较，比较S[i]与S[i+1...n]中的元素每个都要进行比较。所以直接选择排序的时间复杂度为0(n平方)。2、记录的移动次数：当该文件中的记录为正序排列时，记录移动的次数为0,当该文件中的记录为反序时，记录移动的次数为3(n-1)

6、;3、直接选择排序：他是一个就地排序。4、直接选择排序的稳定性：该排序是不稳定的。例如【5.5.4】排序的过程中第一个5与4进行交换，这样就打乱了排序的稳定性。堆排序(HeapSort)(-)堆排序的思想：堆排序的定义如下：n个关键字的a1za2,a3，.…an称为堆，当且仅当满足如下条件的序列称为堆。条件为：a(i)==a(2i)并且a(i)>=a(2i+1);如果把此序列的向量a[1....n]看做一个完全二叉树的存储结构，那么堆的实质就是满足如下条件的完全二叉树：树中的任何一个非叶子节

7、点，该节点的关键字的值要不大于(或不小于)该节点的左、又子节点的关键字的值。(-)堆排序的相关概念:1、大根堆和小根堆：顾名思义，大根堆就是根式堆中关键字最大的那个元素，小根堆，就是关键字中最小的元素作为根构成的堆就是小根堆。注意：堆中的任意一个子树都是堆。思考？那么单个叶子节点算是堆么?上面我们所说的堆实际上都是二叉堆，类似的可以定义N叉堆。（三）堆排序的特点：堆排序（heapsort）是一种树形选择排序。堆排序的特点是：在排序的过程中将a[1...n]看做一个完全二叉树，利用完全二叉树的双亲节点与子节点之间的内在关系,在当前无序区中选择关键字

8、最大或者最小的记录。（四）堆排序和直接选择排序的区别：直接选择排序中,为了从a[1...n]中选出关键字最小的记录，需要进行n-1次比较