排序

#define MAXSIZE 20

typedef int Keytype;

typedef struct {

Keytype key;

infortype otherinfo;

}Redtype;

typedef struct{

Redtype r[MAXSIZE+1];

int length;

}Sqlist;

 

直接插入排序是一种简单的排序方法，它的基本操作是将一个记录插入到以排好序的有序记录表中，从而得到一个新的、记录数增1的有序表。时间复杂度O(n的平方)

void Insertsort(Sqlist &L)
{
for(i=2;i<=L.length;++i)
ifL.r[i].key<L.r[i-1].key){
L.r[0]=L.r[i];、、复制作为哨兵
L.r[i]=L.r[i-1];
for(j=i-2;L.r[0].key<L.r[j].key);--j)
  L.r[j+1]L.r[j];//记录后移
L.r[j+1]=L.r[0];//插入到正确位置
}
}

折半插入排序：在一个有序表中进行查找和插入。时间复杂度O(n的平方)

void Binsertsort(Sqlist &L){
for(i=2;i<=L.length;++i){
L.r[0]=L.r[i];//将L.r[i]暂存在L.r[0]
int low=1,high=i-1;
while(low<=high)//在r[low..high]中折半查找有序插入的位置
{
int m=(low+high)/2;
if(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];
}
}

希尔排序：先将整个待排记录序列分割成为若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序
快速排序：是对冒泡排序一种改进。通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，棵分别对这两部分继续继续进行排序，以达到整个序列有序。时间复杂度平均为O(n*logn/log2) 最差情况是O(n的平方)

int Partion(Sqlist &L,int low,int high){
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while(low<high){
 while(low<high && L.r[high].key >=pivotkey)
--high;
L.r[low]=L.r[high];//将比枢纽记录小的记录移动到低端
while(low<hig && L.r[low]<=pivotkey)
++low;
L.r[high]=L.r[low];//将比枢纽记录大的记录移动到高端
}
L.r[low]=L.r[0];
return low;
}

void Qsort(Sqlist &L, int low, int high){
if(low<high){
pivotloc=Partition(L,low,high);
Qsort(L,low,pivotloc-1);//对低子表递归排序，pivotloc是枢纽位置
Qsort(L,pivotloc+1,high);//对高子表递归排序
}
}

选择排序是每一堂n-i+1(i=1,2,3...n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。其中最简单且为读者最熟悉的是简单选择排序。

 

简单选择排序操作为通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，冰河第i个记录交换之。

void Selectsort(Sqlist &L){
for(i=1;i<L.length;++i)
{
j=SelectMinkey(L,i);
if(i!=j)
temp=L.r[i];
L.r[i]=L.r[j];
L.r[j]=temp;
}
}