本文共 3977 字,大约阅读时间需要 13 分钟。
值此期末复习阶段,回顾数据结构(C语言)第十章,内部排序汇总
设置哨兵
void InsertSort(RecType r[],int n){ int i,j; for(i=2;i<=n;i++){ //第一项可以认为已经排好,所以从第二项开始 r[0]=r[i]; //复制哨兵,可以防止数组越界的问题 j=i-1; while(r[0].keyr[j].key r[j+1]=r[0]; //将r[0]放回找到的位置 }}
分析:
最好情况:原来的n个记录递增有序
比较关键字n-1次
移动关键字2(n-1)次(复制哨兵后又将哨兵复制回来)
最坏情况:原来的n个记录递减有序
比较关键字次数 O(n2)
移动关键字次数 O(n2)
平均移动记录的次数约为:O(n2)
时间复杂度O(n2)
空间复杂度O(1)
该排序算法是稳定的
折半的前提:在一个有序序列中插入新的记录
折半插入排序的过程中的折半查找的目的是查询插入点
折半插入排序=折半查找+插入
void BInsertSort(){ //对顺序表L做折半查找 for(i=2;ihigh(low=high+1) m=(low+high)/2; if(L.r[0].key
缩小增量排序
插入排序中效率最高的一种排序方法
void ShellSort(int *a,int len){ //希尔排序 int temp=0; //中间值 int i=0; int j=0; int k=0; for(i=(len/2);i>0;i=i/2){ //分组后一个组的长度 for(j=i;j=0&&temp
分析:
空间复杂度:O(1)
只占用了一个暂存单元
时间复杂度:O(n(log2n)2)
希尔排序是一个不稳定的排序方法(*)
void bubble1(int a[],int n){ int i,j,temp; //temp作为中间量 for(int i=0;ia[j+1]){ temp=a[j]; //交换 a[j]=a[j+1]; a[j+1]=temp; } } }}
void bubblesort2(int a[],int n){ int i,j,flag,temp; for(int i=0;ia[j+1]){ temp=a[j]; //交换 a[j]=a[j+1]; a[j+1]=temp; flag=0; //如果有交换,那么没有排好序 } } if(flag==1) //如果没有交换,说明已经有序,不需要再比较,直接退出 break; }}
分析:
基本思想:首先在r[1…n]中,确定一个r[i],经过比较和移动,使得r[i]左边的所有记录的关键字小于等于r[i].key,r[i]右边所有记录的关键字大于等于r[i].key。以r[i]为界,将文件划分为左右两个子文件,继续下去,使得每个文件只有一个记录为止。
void quksort(int r[],int low,int high){ int x,i,j; if(lowx)i++;//从左端开始,找到第一个比x大的数 if(i
分析:
void SelectSort(int r[],int n){ int i,j,min; int x; for(i=1;i
分析:
树形选择排序又称锦标赛排序,是一种按照锦标赛的思想进行排序的方法,可以用一颗有n个叶子结点的完全二叉树表示
每个内点是它左右孩子中的最小值
分析:
需要另外开辟新的空间保存排序结果
需要额外的n-1个内部节点,增加了内存开销
将最小关键字改为极大数,再于兄弟结点比较属于多余
树形选择排序一般不是用来排序,而是证明某些问题
空间复杂度:O(n)
时间复杂度:
树形选择排序是不稳定的。
堆的定义(可以看作一个完全二叉树)
ki<=k2i且ki<=k2i+1 (小顶堆)
ki>=k2i且ki>=k2i+1 (大顶堆)
- 两个问题
- 如何初始化一个序列为堆
- 堆顶元素被替换后,调整剩余元素成一个新的堆
堆调整的算法:
void HeapAdjust(int r[],int s,int m){ //r中从1开始存放根节点,s是要调整的位置 rc=r[s]; //保存调整的元素,空出s的位置 for(j=2*s;j<=m;j*=2){ if(jr[j]) //如果rc比极大孩子的值还要大,那么就不能继续下沉 break; //也就是找到了要插入的位置 r[s]=r[j]; //没有找到要插入的位置,就将极大孩子值放到这个位置 s=j; } r[s]=rc; //将rc填入到正确的位置,符合堆的定义的位置}
把k个有序子文件合在一起,形成一个新的有序文件,同时归并k个有序子文件的过程称为k-路归并排序
2-路归并排序:归并2个有序子文件的排序
注:以下代码中,两个子文件在r中,由mid隔开
同时,这个算法在链表时使用过,当然也可以使用链式存储结构来尝试
void merge(int r[],int y[],int low,int mid,int high){ //归并两个有序子文件 int k=i=low,j=mid+1; while(i<=mid&&j<=high){ if(r[i]
基数排序进分析关键字自身每位的值,通过分配、回收进行处理。
从地位到高位,依次排序,产生有序序列
O(nlogn):快速排序、堆排序、归并排序
快排是被认为是最快的排序方法,后两者,比较,在n值较大的情况下,归并排序较堆排序更快
O(n2):插入排序、冒泡排序、选择排序
插入排序最为常用,选择排序过程中记录移动次数最少
O(n):基数排序
待排序的记录序列安关键字顺序有序时,应尽量避免快速排序
简单排序的三种方法中,冒泡排序效率最低
一般来说,排序的过程中所进行的比较操作和交换数据仅发生在相邻的记录之间,没有大布距的数据调整,则排序方法是稳定的
排序的记录个数较小时,选择插入排序法,如果一个记录的数据项较多,占用空间大,应该降低移动次数,选用选择排序法,但若有“有序”倾向时,慎用快速排序
快速排序和归并排序在n值较小时的性能不及直接插入排序
基数排序的时间复杂度是O(d*n),适合n很大,d较小的情况
如果安最次位优先进行排序时,必须宣统稳定的排序方法(也就是,含有多个关键字时)
转载地址:http://idzwb.baihongyu.com/