数据结构—排序总结
数据结构—排序
数据结构这本书自己已经翻了好几遍,每次看都有不一样的收获,这几天花了些时间重新看了一下排序这一方面,虽然总的来说排序就那么几种,但是每一种排序代表了一种思想,还是要花时间认真看看的。
下面主要就是就是我学习的收获,下面贴的代码也主要是数据结构(严蔚敏)书上的,都是通过自己测试过的,通过写书上的代码也算是加深了一点认识吧!常用的内部排序算法主要分为五类:插入、交换、选择、归并、基数排序。这里也只分析内部排序不涉及到外部排序。
一、插入排序
在一个已经排好序的序列中,将未被排进的元素按照原先的规定插入到指定位置
1、直接插入排序
我觉得这是比较简单的排序方法,它的基本基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增加1的有序表。
void InsertSort(SqList &L){ /* 对顺序表L作直接插入排序。*/ int i,j; for(i=2;i<=L.length;++i) if LT(L.r[i].key,L.r[i-1].key) /* "<",需将L.r[i]插入有序子表 */ { L.r[0]=L.r[i]; /* 复制为哨兵 */ for(j=i-1;LT(L.r[0].key,L.r[j].key);--j) L.r[j+1]=L.r[j]; /* 记录后移 */ L.r[j+1]=L.r[0]; /* 插入到正确位置 */ }}
void BInsertSort(SqList &L){ /* 对顺序表L作折半插入排序。*/ int i,j,m,low,high; for(i=2;i<=L.length;++i) { L.r[0]=L.r[i]; /* 将L.r[i]暂存到L.r[0] */ low=1; high=i-1; while(low<=high) { /* 在r[low..high]中折半查找有序插入的位置 */ m=(low+high)/2; /* 折半 */ if LT(L.r[0].key,L.r[m].key) high=m-1; /* 插入点在低半区 */ else low=m+1; /* 插入点在高半区 */ } for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; /* 记录后移 */ L.r[high+1]=L.r[0]; /* 插入 */ }}
void P2_InsertSort(SqList &L){ /* 2_路插入排序 */ int i,j,first,final; RedType &d; d=(RedType*)malloc(L.length*sizeof(RedType)); /* 生成L.length个记录的临时空间 */ d[0]=L.r[1]; /* 设L的第1个记录为d中排好序的记录(在位置[0]) */ first=final=0; /* first、final分别指示d中排好序的记录的第1个和最后1个记录的位置 */ for(i=2;i<=L.length;++i) { /* 依次将L的第2个~最后1个记录插入d中 */ if(L.r[i].key<d[first].key) { /* 待插记录小于d中最小值,插到d[first]之前(不需移动d数组的元素) */ first=(first-1+L.length)%L.length; /* 设d为循环向量 */ d[first]=L.r[i]; } else if(L.r[i].key>d[final].key) { /* 待插记录大于d中最大值,插到d[final]之后(不需移动d数组的元素) */ final=final+1; d[final]=L.r[i]; } else { /* 待插记录大于d中最小值,小于d中最大值,插到d的中间(需要移动d数组的元素)*/ j=final++; /* 移动d的尾部元素以便按序插入记录 */ while(L.r[i].key<d[j].key) { d[(j+1)%L.length]=d[j]; j=(j-1+L.length)%L.length; } d[j+1]=L.r[i]; } } for(i=1;i<=L.length;i++) /* 把d赋给L.r */ L.r[i]=d[(i+first-1)%L.length]; /* 线性关系 */}
void ShellInsert(SqList &L,int dk){ /* 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比, */ /* 作了以下修改: */ /* 1.前后记录位置的增量是dk,而不是1; */ /* 2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。*/ int i,j; for(i=dk+1;i<=L.length;++i) if LT(L.r[i].key,L.r[i-dk].key) { /* 需将L.r[i]插入有序增量子表 */ L.r[0]=L.r[i]; /* 暂存在L.r[0] */ for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk) L.r[j+dk]=L.r[j]; /* 记录后移,查找插入位置 */ L.r[j+dk]=L.r[0]; /* 插入 */ }}
void bubble_sort(int a[],int n){ /* 将a中整数序列重新排列成自小至大有序的整数序列(起泡排序) */ int i,j,t; Status change; for(i=n-1,change=TRUE;i>1&&change;--i) { change=FALSE; for(j=0;j<i;++j) if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; change=TRUE; } }}
int Partition(SqList &L,int low,int high){ /* 交换顺序表L中子表L.r[low..high]的记录,使枢轴记录到位, */ /* 并返回其所在位置,此时在它之前(后)的记录均不大(小)于它。*/ RedType t; KeyType pivotkey; pivotkey=L.r[low].key; /* 用子表的第一个记录作枢轴记录 */ while(low<high) { /* 从表的两端交替地向中间扫描 */ while(low<high&&(*L).r[high].key>=pivotkey) --high; t=L.r[low]; /* 将比枢轴记录小的记录交换到低端 */ L.r[low]=L.r[high]; L.r[high]=t; while(low<high&&L.r[low].key<=pivotkey) ++low; t=L.r[low]; /* 将比枢轴记录大的记录交换到高端 */ L.r[low]=L.r[high]; L.r[high]=t; } return low; /* 返回枢轴所在位置 */}void QSort(SqList &L,int low,int high){ /* 对顺序表L中的子序列L.r[low..high]作快速排序。*/ int pivotloc; if(low<high) { /* 长度大于1 */ pivotloc=Partition(L,low,high); /* 将L.r[low..high]一分为二 */ QSort(L,low,pivotloc-1); /* 对低子表递归排序,pivotloc是枢轴位置 */ QSort(L,pivotloc+1,high); /* 对高子表递归排序 */ }}void QuickSort(SqList &L){ /* 对顺序表L作快速排序。*/ QSort(L,1,L.length);
int SelectMinKey(SqList L,int i){ /* 返回在L.r[i..L.length]中key最小的记录的序号 */ KeyType min; int j,k; k=i; /* 设第i个为最小 */ min=L.r[i].key; for(j=i+1;j<=L.length;j++) if(L.r[j].key<min) /* 找到更小的 */ { k=j; min=L.r[j].key; } return k;}void SelectSort(SqList &L){ /* 对顺序表L作简单选择排序。*/ int i,j; RedType t; for(i=1;i<L.length;++i) { /* 选择第i小的记录,并交换到位 */ j=SelectMinKey(&L,i); /* 在L.r[i..L.length]中选择key最小的记录 */ if(i!=j) { /* 与第i个记录交换 */ t=L.r[i]; L.r[i]=L.r[j]; L.r[j]=t; } }}
void HeapAdjust(HeapType &H,int s,int m) { /* 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义,本函数 */ /* 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言) */ RedType rc; int j; rc=H.r[s]; for(j=2*s;j<=m;j*=2) { /* 沿key较大的孩子结点向下筛选 */ if(j<m&<(H.r[j].key,H.r[j+1].key)) ++j; /* j为key较大的记录的下标 */ if(!LT(rc.key,H.r[j].key)) break; /* rc应插入在位置s上 */ H.r[s]=H.r[j]; s=j; } H.r[s]=rc; /* 插入 */}void HeapSort(HeapType &H){ /* 对顺序表H进行堆排序。*/ RedType t; int i; for(i=H.length/2;i>0;--i) /* 把H.r[1..H.length]建成大顶堆 */ HeapAdjust(H,i,H.length); for(i=H.length;i>1;--i) { /* 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换 */ t=H.r[1]; H.r[1]=H.r[i]; H.r[i]=t; HeapAdjust(H,1,i-1); /* 将H.r[1..i-1]重新调整为大顶堆 */ }}
void Merge(RedType SR[],RedType TR[],int i,int m,int n){ /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */ int j,k,l; for(j=m+1,k=i;i<=m&&j<=n;++k) /* 将SR中记录由小到大地并入TR */ if LQ(SR[i].key,SR[j].key) TR[k]=SR[i++]; else TR[k]=SR[j++]; if(i<=m) for(l=0;l<=m-i;l++) TR[k+l]=SR[i+l]; /* 将剩余的SR[i..m]复制到TR */ if(j<=n) for(l=0;l<=n-j;l++) TR[k+l]=SR[j+l]; /* 将剩余的SR[j..n]复制到TR */}void MSort(RedType SR[],RedType TR1[],int s, int t){ /* 将SR[s..t]归并排序为TR1[s..t]。*/ int m; RedType TR2[MAXSIZE+1]; if(s==t) TR1[s]=SR[s]; else { m=(s+t)/2; /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */ MSort(SR,TR2,s,m); /* 递归地将SR[s..m]归并为有序的TR2[s..m] */ MSort(SR,TR2,m+1,t); /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */ Merge(TR2,TR1,s,m,t); /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */ }}