常见的排序算法

《常见的排序算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、插入排序是最简单最直观的排序算法了，它的依据是：遍历到第N个元素的时候前面的N-1个元素已经是排序好的了，那么就查找前面的N-1个元素把这第N个元素放在合适的位置，如此下去直到遍历完序列的元素为止。算法的复杂度也是简单的，排序第一个需要1的复杂度，排序第二个需要2的复杂度，因此整个的复杂度就是1+2+3+……+N=O（N^2）的复杂度。//插入排序voidInsertSort(intarray[],intlength){　　　inti,j,key;　　　for(i=1;i

2、ay[i]的数据向后移动　　　　　　　for(j=i-1;j>=0&&array[j]>key;j--)　　　　　　　{　　　　　　　　　　　array[j+1]=array[j];　　　　　　　}　　　　　　　//在合适位置安放当前元素　　　　　　　array[j+1]=key;　　　}}shell排序是对插入排序的一个改装，它每次排序把序列的元素按照某个增量分成几个子序列，对这几个子序列进行插入排序，然后不断的缩小增量扩大每个子序列的元素数量，直到增量为一的时候子序列就和原先的待排列序列一样了，此时只需要做少量的比较和移动就可以完成对序列的排序了。//shell排序void

3、ShellSort(intarray[],intlength){　　　inttemp;　　　//增量从数组长度的一半开始,每次减小一倍　　　for(intincrement=length/2;increment>0;increment/=2)　　　　　　　for(inti=increment;i=increment;j-=increment)　　　　　　　　　　　{　　

4、　　　　　　　　　　　　　//把i之前大于array[i]的数据向后移动　　　　　　　　　　　　　　　if(temp

5、p;　　　　　　　}}堆的定义：n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质（简称为堆性质）：（1）ki≤K2i且ki≤K2i+1或（2）Ki≥K2i且ki≥K2i+1（1≤i≤）若将此序列所存储的向量R[1……n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。堆的这个性质使得可以迅速定位在一个序列之中的最小（大）的元素。堆排序算法的过程如下：1）得到当前序列的最小（大）的元素2）把这个元素和最后一个元素进行交换，这样当前的最小（大）的元素就放在了序列的

6、最后，而原先的最后一个元素放到了序列的最前面3）的交换可能会破坏堆序列的性质（注意此时的序列是除去已经放在最后面的元素），因此需要对序列进行调整，使之满足于上面堆的性质。重复上面的过程，直到序列调整完毕为止。//array是待调整的堆数组,i是待调整的数组元素的位置,length是数组的长度voidHeapAdjust(intarray[],inti,intnLength){　　　intnChild,nTemp;　　　for(nTemp=array[i];2*i+1

7、ild=2*i+1;　　　　　　　//得到子结点中较大的结点　　　　　　　if(nChild!=nLength-1&&array[nChild+1]>array[nChild])　　　　　　　　　　　++nChild;　　　　　　　//如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点　　　　　　　if(nTemp