数据结构排序算法总结

稳定的排序算法如下表所示冒泡排序(bubble1插入排序(insertion1归并排序(mergeO(nlog桶排序(bucket基数排序(RadixO(dn)（d是常数二叉树排序(BinarytreeO(nlog不稳定的排序算法如下表所示选择排序(selection1排序(sO(nlog1堆排序O(nlog1快速排序平均是O(nlogn)，是O(log（一）的速度要求。而一般我们所谓的算法的性能主要是指算法的复杂度，一般用OO若存在一个常量Kn0n>=n0时，有f(n)<=K×g(n),f(n)=O(g(n))O(N2第二部分是高级排序算法，复杂度为O(N×Log2(N))或小于O(N2)。这里我们只介绍3种算法。另外还1R：凡扫描到本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。2（2）S排序(排序（3）O(n)的空间。(1)nn≤40)，可采用插入排序或选择排序。当记录规模较小时，插入排序较好；反之，因为选择移动的记录数少于插人，应选选择排序为宜。(2)若文件初始状态基本有序(指正序)，则应选用插人、冒泡或随机的快速排序为宜；(3)nO(N×Log2(N))速排序、堆排序或归并排序。排序的平均时间最短；快速排序不适合用于“几乎已排好序”或“几乎正好倒序”的数据。在此情况O(N2)。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的S排序的时间复杂度在数学上没有解决，大致可以认为是O(n(1￡)),其中￡是介于0和1之间的（二）O(N)；R[low..high]是当前的查找区间)：首先确定该区间的中点位置R[mid].key>K，R[mid..n].keysK，因此若表中存在关键字等于KmidR[1..mid-1]R[1..mid-R[mid].key<K，KmidR[mid+1..n]中，即新的查找区间是右R[mid+1..n]。下一次查找是针对新的查找区间进行的。R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比K结点，或者直至当前的查找区间为空(即查找失败)时为止。分块查找(BlockingSearch)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找分块查找表的结构由“分块有序”的线性表和索引表组成R[1..n]bb-1s=n/b，bs；每一块中的关ID[l..b]，即：ID[i](1≤i≤b)块的最大关键字及该块在表RR(1)nn≤40)，(2)nO(Log2(N))的二分查找方法。(3)若文件初始状态分块有序，且n一、冒泡排数放面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，二、插入排主要有直接插入排序和排序。如果该元素（已排序）3，三、归并排nn12n2435、将另一序列剩下的所有元素直接到合并序列尾四、桶排n[0，1)在桶排序算法的代码中，假设输入是个含n个元素的数组A，且每个元素满足0≤A[i]<1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶，并假设可以用某种机制来这些表。布分到N个桶中，每一个桶都用一个链表来 五、基数排C0<=Kj<=Crd-1(0<=j<=rd),可rdrd=10,C0=0,C9=9,d基数排序的基本思想是：从低位到依次对待排序的关键码进行分配和d基数排序从低位到进行，使得最后一次计数排序完成后，数组有序，最后按年排序，仅需排序三次。但是如果先排序就没这么简单了。基六、二叉树排二叉排序树（BinarySortTree）又称二叉查找树。它或者是一棵空1、首先执行查找算法，找出结点的父亲结点2、判断结点是其父亲结点的左、右儿子。将结点作为叶子结点插3z1、如果结点z没有，则修改其父结点p[z]，使NIL为其2、如果结点z只有一个，则可以通过在其子结点与父结点间建立z；3、如果结点z只有两个，先删除z的后继y(它没有左)，再yz七、选择排与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记 八、排(S)排序的基本思想是：先取一个小于n的整数d1作为d1d1d2<d1di=1，插入排序为止。该方法实质上是一种分组插入方法。d1=n/2，di+1=di/21，di九、堆排(1)ki≤K2i且或(2)Ki≥K2i且ki≥K2i+1(1≤i≤若将此序列所的向量R[1..n]看作是一棵完全二叉树的结构则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。1R[1..n]R[1..n-1]R[n]，R[1..n-3、由于交换后新的根R[1]可能堆性质，故应将当前无序区R[1..n-1]R[1..n-1]R[1]和该区间的最后一R[n-1]R[1..n-2]R[n-1..n]，且十、快速排第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2一、插入排一、插入排 排二、交换排 一、插入排1）直接插入排 算法演时间复杂度：平均情况—view情况— 辅助空间 稳定性：稳voidInsertSort(SqList&L)Lintfor(i=2;i<=L.length;if(LT(L.r[i].key,L.r[i-1].key))22）折半插入排时间复杂度：平均情况— viewL.r[i]L.r[0]= for(j=i- LT(L.r[0].key, --L.r[j+1]= L.r[j+1]= }}//voidBInsertSort(SqList&L)Lintfor(i=2;i<=L.length;++i)L.r[0]= L.r[i]low= high=i-07while(low<=high){ r[low..high]中折半查找有序08m=if(LT(L.r[0].key,L.r[m].key))high=m- elselow }for(j=i-1;j>=high+1;--j)L.r[j+1]= 移L.r[high+1] 入}}//3）排 算法演 返时间复杂度：理想情况— viewvoidSInsert(SqList&L,intdk)//对顺序表L作一趟插入排序。本算法对算法10.1作了以下修 1.dk， 2.r[0]j<=0intfor(i=dk+1;i<=L.length;if(LT(L.r[i].key,L.r[i-dk].key))L.r[i]插入有L.r[0] for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-L.r[j+dk]= L.r[j+dk]= }}//SvoidSSort(SqList&L,intdlta[],intt)//按增量序列dlta[0..t-1]对顺序表L作排序for(int二、二、交换排1）冒泡排 算法演时间复杂度：平均情况—情况— 辅助空间 viewSInsert(L, dlta[k]}//voidBubbleSort(SeqListR)intBooleanexchange;for(i=1;i<n;i++){exchange="FALSE;"j="n-1;j">=i;jR[i..n]自下向上扫描if(R[j+1].key<R[j].key){//R[0]=R[j+1];//R[0]exchange=TRUE;}if(!exchange)}//endfor(}22）快速排 算法演时间复杂度：平均情况— intintPartition(SqList&L,intlow,inthigh)LL.r[low..high]//并返回其所在位置，此时，在它之前（后）的记录均不大（小KeyTypeRedTypepivotkey=L.r[low].key; while(low<high){ while(low<high&&L.r[high].key>=pivotkey)-- 的记录交换到while <high&&L.r[low].key< }return }//intPartition(SqList&L,intlow,inthigh)LL.r[low..high]//并返回其所在位置，此时，在它之前（后）的记录均不大（小KeyTypeviewviewL.r[0]=L.r[low]; pivotkey= while(low<high){ while(low<high&&L.r[high].key>=pivotkey)--L.r[low]= while <high&& <L.r[high]= }L.r[low]= return }//voidQSort(SqList&L,intlow,inthigh)LL.r[low..high]intif pivotloc=Partition(L,low, QSort(L,low,pivotloc-1);，pivotlocQSort(L,pivotloc+1,high); }}//voidQuickSort(SqList&L) LQSort(L,1,三三、选择排1）简单选择排 算法演时间复杂度：平均情况— 辅助空间 view}//}//voidSelectSort(SqList&L)Lintfor(i=1;i<L.length;++i)ij=SelectMinKey(L, L.r[i..L.length]if(i!=j) iRedType}}}//2）堆排 算法演 返时间复杂度：平均情况— 情况— viewvoidHeapAdjust(HeapType&H,ints,intm)H.r[s..m]H.r[s].keyH.r[s]H.r[s..m]//（对其中记录的关键字而言intRedTyperc=for(j=2*s;j<=m;j*=2) key选if(jm&&H.r[j].keyH.r[j+1].key)++j;jkeyif(rc.key>=H.r[j].key)break; rcsH.r[s]= s=}H.r[s]= }//voidHeapSort(HeapType&H)HintRedTypefor(i=H.length/2;i>0;-- H.r[1..H.length]HeapAdjust(H,i,H.lengthfor(i=H.length;i>1;--i) //将堆顶记录和当前排序子Hr[1..i]HeapAdjust(H,1,i- H.r[1..i-1]}}//四四、归并排 算法演时间复杂度：平均情况—情况— viewvoidMerge(RedTypeSR[],RedTypeTR[],inti,intm,intn)SR[i..m]SR[m+1..n]intfor(j=m+1, i<=m&&j< ++k)SRifLQ(SR[i].key,SR[j].key)TR[k]=elseTR[k]=}if(i<=m) //TR[k..n]=SR[i..m]; TRwhile(k<=n&&i<=m)if(j< //将剩余的SR[j..n]到while(k<=n <=n)}//voidMSort(RedTypeSR[],RedTypeTR1[],ints,intt)SR[s..t]TR1[s..t]intRedTypeif(s==t)TR1[t]=else SR[s..t]平分为SR[s..m]SR[m+1..t] SR[s..m]归并为有TR2[s..m] SR[m+1..t]Merge(TR2,TR1,s,m,t);TR2[s..m]TR2[m+1..t]归TR1[s..t]}五五、基数排 算法演时间复杂度：平均情况—情况— 辅助空间 view}//voidMergeSort(SqList&L)LMSort(L.r,L.r,1,}//voidDistribute(SLList&L,inti,ArrType&f,ArrType&e)Lr(keys[0],...,keys[i-1])ikeys[i]RADIXkeys[i]相同。f[0..RADIX-1]intj,for(j=0;j<RADIX;++j)f[j]=0; for