本文共 4862 字,大约阅读时间需要 16 分钟。
插入排序方法:时间复杂度O(n^2)的稳定排序:
每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。
(1) 设置监视哨r[0],将待插入纪录的值赋值给r[0]; (3) 在数组中进行搜索,搜索中将第j个纪录后移,直至r[0].key≥r[j].key为止; 代码:void Insert_sort(int n) /* 对数组R中的记录R[1..n]按递增序进行插入排序 */ for(i=2;i<=n;i++) /* 依次插入R[2],…,R[n] */ {/* 若R[i]大于等于有序区中所有的R,则R[i] */ R[0]=R[i];j=i-1; /* R[0]是哨兵,且是R[i]的副本 */ do{ /* 从右向左在有序区R[1..i-1]中查找R[i]的插入位置 */ R[j+1]=R[j]; /* 将关键字大于R[i]的记录后移 */ }while(R[0]<R[j]); /* 当R[i]≥R[j]时终止 */ R[j+1]=R[0]; /* R[i]插入到正确的位置上 */
希尔排序法(缩小增量排序):时间复杂度与增量序列的选取有关,下限是n*log2n不稳定排序 void ShellPass(int d, int n) for(i=d+1;i<=n;i++) /* 将R[d+1..n]分别插入各组当前的有序区 */ R[0]=R[i];j=i-d; /* R[0]只是暂存单元,不是哨兵 */ R[j+d]=R[0]; /* 插入R[i]到正确的位置上 */ int increment=n; /* 增量初值,不妨设n>0 */ increment=increment/3+1; /* 求下一增量 */ ShellPass(increment,n); /* 一趟增量为increment的Shell插入排序 */ for(i=1;i<n;i++){ /* 最多做n-1趟排序 */ exchange=0; /* 本趟排序开始前,交换标志应为假 */ for(j=n-1;j>=i;j--) /* 对当前无序区R[i..n]自下向上扫描 */ if(R[j+1]<R[j]){/* 交换记录 */ R[0]=R[j+1]; /* R[0]不是哨兵,仅做暂存单元 */ exchange=1; /* 发生了交换,故将交换标志置为真 */ if(!exchange) /* 本趟排序未发生交换,提前终止算法 */ 基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以进行,以此达到整个数据变成有序
1)设置两个变量i、j,开始的时候:i=0,j=N-1; 2)以第一个数组元素作为关键数据,赋值给key,即key=A[0]; 3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换; 4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换; 5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
int Partition(int i,int j) {/* 调用Partition(R,low,high)时,对R[low..high]做划分,*/ int pivot=R[i]; /* 用区间的第1个记录作为基准 */ while(i<j){ /* 从区间两端交替向中间扫描,直至i=j为止 */ while(i<j&&R[j]>=pivot) /* pivot相当于在位置i上 */ j--; /* 从右向左扫描,查找第1个关键字小于pivot.key的记录R[j] */ if(i<j) /* 表示找到的R[j]的关键字<pivot.key */ R[i++]=R[j]; /* 相当于交换R[i]和R[j],交换后i指针加1 */ while(i<j&&R[i]<=pivot) /* pivot相当于在位置j上*/ i++; /* 从左向右扫描,查找第1个关键字大于pivot.key的记录R[i] */ if(i<j) /* 表示找到了R[i],使R[i].key>pivot.key */ R[j--]=R[i]; /* 相当于交换R[i]和R[j],交换后j指针减1 */ R[i]=pivot; /* 基准记录已被最后定位*/ void Quick_Sort(int low,int high) { /* 对R[low..high]快速排序 */ int pivotpos; /* 划分后的基准记录的位置 */ if(low<high){/* 仅当区间长度大于1时才须排序 */ pivotpos=Partition(low,high); /* 对R[low..high]做划分 */ Quick_Sort(low,pivotpos-1); /* 对左区间递归排序 */ Quick_Sort(pivotpos+1,high); /* 对右区间递归排序 */ } /* end of Quick_Sort */ for(j=i+1;j<=n;j++) /* 在当前无序区R[i..n]中选key最小的记录R[k] */ k=j; /* k记下目前找到的最小关键字所在的位置 */ R[0]=R[i]; R[i]=R[k]; R[k]=R[0]; /* R[0]作暂存单元 */ } /* end of Select_Sort */ void Heapify(int s,int m) { /*对R[1..n]进行堆调整,用temp做暂存单元 */ if (R[j]>R[j+1]&&j<m) j++; { /* 对R[1..n]进行堆排序,不妨用R[0]做暂存单元 */ BuildHeap(n); /* 将R[1-n]建成初始堆 */ { /* 对当前无序区R[1..i]进行堆排序,共做n-1趟。 */ R[0]=R[1]; R[1]=R[i];R[i]=R[0]; /* 将堆顶和堆中最后一个记录交换 */ Heapify(1,i-1); /* 将R[1..i-1]重新调整为堆,仅有R[1]可能违反堆性质 */ 第一步:申请空间,使其大小为两个已经序列之和,该空间用来存放合并后的序列 第二步:设定两个,最初位置分别为两个已经排序序列的起始位置 第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 void Merge(int low,int m,int high) {/* 将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的 */ int i=low,j=m+1,p=0; /* 置初始值 */ int *R1; /* R1是局部向量,若p定义为此类型指针速度更快 */ R1=(int *)malloc((high-low+1)*sizeof(int)); puts("Insufficient memory available!"); while(i<=m&&j<=high) /* 两子文件非空时取其小者输出到R1[p]上 */ R1[p++]=(R[i]<=R[j])?R[i++]:R[j++]; while(i<=m) /* 若第1个子文件非空,则复制剩余记录到R1中 */ while(j<=high) /* 若第2个子文件非空,则复制剩余记录到R1中 */ for(p=0,i=low;i<=high;p++,i++) R[i]=R1[p];/* 归并完成后将结果复制回R[low..high] */ void Merge_SortDC(int low,int high) {/* 用分治法对R[low..high]进行二路归并排序 */ mid=(low+high)/2; /* 分解 */ Merge_SortDC(low,mid); /* 递归地对R[low..mid]排序 */ Merge_SortDC(mid+1,high); /* 递归地对R[mid+1..high]排序 */ Merge(low,mid,high); /* 组合,将两个有序区归并为一个有序区 */ }/* end of Merge_SortDC */ 转载地址:http://qutmi.baihongyu.com/