文档介绍：数据结构-各类排序算法总结原文转自:(Sorting)是计算机程序设计中的一种重要操作,其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。有n个记录的序列{R1,R2,…,Rn},其相应关键字的序列是{K1,K2,…,Kn},相应的下标序列为1,2,…,n。经过排序,要求找出当前下标序列1,2,…,n的一种排列p1,p2,…,pn,使得相应关键字满足如下的非递减(或非递增)关系,即:Kp1≤Kp2≤…≤Kpn,这样就得到一个按关键字有序的记录序列{Rp1,Rp2,…,Rpn}。作为排序依据的数据项称为“排序码”,也即数据元素的关键码。若关键码是主关键码,则对于任意待排序序列,经排序后得到的结果是唯一的;若关键码是次关键码,排序结果可能不唯一。实现排序的基本操作有两个:(1)“比较”序列中两个关键字的大小;(2)“移动”记录。若对任意的数据元素序列,使用某个排序方法,对它按关键码进行排序:若相同关键码元素间的位置关系,排序前与排序后保持一致,称此排序方法是稳定的;而不能保持一致的排序方法则称为不稳定的。。仅有一个记录的表总是有序的,因此,对n个记录的表,可从第二个记录开始直到第n个记录,逐个向有序表中进行插入操作,从而得到n个记录按关键码有序的表。它是利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。注意直接插入排序算法的三个要点:(1)从R[i-1]起向前进行顺序查找,监视哨设置在R[0];[cpp]viewplaincopyR[0]=R[i];//设置“哨兵”for(j=i-1;R[0].key<R[j].key;--j)//从后往前找returnj+1;//返回R[i]的插入位置为j+1(2)对于在查找过程中找到的那些关键字不小于R[i].key的记录,能够在查找的同时实现向后移动,即:查找与移动同时进行.[cpp]viewplaincopyfor(j=i-1;R[0].key<R[j].key;--j){R[j+1]=R[j];}(3)i=2,3,…,n,实现整个序列的排序(从i=2开始).【算法如下】[cpp]viewplaincopy//C++代码,确保能够运行voidinsertionSort(int*R,intlength){for(inti=2;i<=length;++i){R[0]=R[i];//设为监视哨intj;for(j=i-1;R[0]<R[j];--j){R[j+1]=R[j];//边查找边后移}R[j+1]=R[0];//插入到正确位置}}【性能分析】(1)空间效率:仅用了一个辅助单元,空间复杂度为O(1)。只需R[0]做辅助.(2)时间效率:向有序表中逐个插入记录的操作,进行了n-1趟,每趟操作分为比较关键码和移动记录,而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。直接插入排序的最好情况的时间复杂度为O(n),平均时间复杂度为O(n^2)。(3)稳定性:直接插入排序是一个稳定的排序方法。总体来说:直接插入排序比较适用于带排序数目少,,插入位置的确定经过对有序表中记录按关键码逐个比较得到的。平均情况下总比较次数约为(n^2)/4。既然是在有序表中确定插入位置,能够不断二分有序表来确定插入位置,即一次比较,经过待插入记录与有序表居中的记录按关键码比较,将有序表一分为二,下次比较在其中一个有序子表中进行,将子表又一分为二。这样继续下去,直到要比较的子表中只有一个记录时,比较一次便确定了插入位置。折半插入排序是利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”。综上:折半插入排序只是减少了比较的次数,因此折半插入排序总的时间复杂度仍是O(n^2).,较直接插入排序和折半插入排序方法有较大的改进。直接插入排序算法简单,在n值较小时,效率比较高,在n值很大时,若序列按关键码基本有序,效率依然较高,其时间效率可提高到O(n)。希尔排序即是从这两点出发,给出插入排序的改进方法。希尔排序的基本思想是:先将待排序记录序列分割成若干个“较稀疏的”子序列,分别进行直接插入排序。经过上述粗略调整,整个序列中的记录已经基本有序,最后再对全部记录进行一次直接插入排序。具体实现时,首先选定两个记录间的距离d1,在整个待排序记录序列中将所有间隔为d1的记录分成一组,进行组内直接插入排序,然后再取两个记录间的距离d2<d1,在整个待排序记录序列中,将所有间隔为d2的记录分成一组,进行组内直接插入排序,直至选定两个记录间的距