数据结构之排序的实现

1、插入排序

Cpp代码 收藏代码
void InsertSort(RecType R[],int n){
int i,j,k;
RecType temp;
for (i=1; i<n; i++) {
temp=R[i];
j=i-1;
while (j>=0&&temp.key<R[j].key) {
R[j+1]=R[j];
j–;
}
R[j+1]=temp;

printf(” i=%d “,i);
for (k=0; k<n; k++) {
printf(“%3d”,R[k].key);
}
printf(“\n”);
}

}
2、冒泡排序

Cpp代码 收藏代码
void BubbleSort(RecType R[],int n){
int i,j,k;
RecType temp;
for (i=0; i<n-1; i++) {
for (j=n-1; j>i; j–) {
if(R[j].key<R[j-1].key){
temp=R[j];
R[j]=R[j-1];
R[j-1]=temp;

}
}
printf(” i=%d: “,i);
for (k=0; k<n; k++) {
printf(“%2d”,R[k].key);
}
printf(“\n”);
}
}

3、选择排序

Cpp代码 收藏代码
void SelectSort(RecType R[],int n){
int i,j,k;
RecType temp;
for (i=0; i<n-1; i++) {
k=i;
for (j=i+1; j<n; j++) {
if(R[j].key<R[k].key){
k=j;
}
}
if(k!=i){
temp=R[i];
R[i]=R[k];
R[k]=temp;
}
printf(” i=%d: “,i);
for (k=0; k<n; k++) {
printf(“%2d”,R[k].key);
}
printf(“\n”);
}
}
4、希尔排序

Cpp代码 收藏代码
void ShellSort(RecType R[],int n){
int i,j,d,k;
RecType temp;
d=n/2;
while (d>0) {
for (i=d; i<n; i++) {
j=i-d;
while (j>=0&&R[j].key>R[j+d].key) {
temp=R[j];
R[j]=R[j+d];
R[j+d]=temp;
j=j-d;
}
}

printf(” d=%d: “,d);
for (k=0; k<n; k++) {
printf(“%3d”,R[k].key);
}
printf(“\n”);
d=d/2;
}
}

5、快速排序

Cpp代码 收藏代码
void QuickSort(RecType R[],int s,int t){
int i=s,j=t,k;
RecType temp;
if(s<t){
temp=R[s];
while(i!=j){
while(j>i&&R[j].key>temp.key)
j–;
if(i<j){
R[i]=R[j];
i++;
}
while(i<j&&R[i].key<temp.key)
i++;
if(i<j){
R[j]=R[i];
j–;
}
}
R[i]=temp;
printf(” “);
for(k=0;k<10;k++){
if(k==i){
printf(” [%d]“,R[k].key);
}else{
printf(“%4d”,R[k].key);
}
}
printf(“\n”);

QuickSort(R,s,i-1);
QuickSort(R,i+1,t);

}
}

6、堆排序

Cpp代码 收藏代码
void Sift(RecType R[],int low,int high){

int i=low,j=2*i;
RecType temp=R[i];
while(j<=high){
if(j<high&&R[j].key<R[j+1].key){
j++;
}
if(temp.key<R[j].key){
R[i]=R[j];
i=j;
j=2*i;
}else{
break;
}
}
R[i]=temp;
}
void HeapSort(RecType R[],int n){
int i;
RecType temp;
for(i=n/2;i>=1;i–)
Sift(R,i,n);
printf(“初始堆： “);DispHeap(R,1,n);printf(“\n”);
for (i=n; i>=2; i–) {
printf(“交换%d与%d,输出%d\n”,R[i].key,R[1].key,R[1].key);
temp=R[1];
R[1]=R[i];
R[i]=temp;
Sift(R,1,i-1);
printf(“筛选调整得到堆：”);
DispHeap(R,1,i-1);
printf(“\n”);
}

}

7、归并排序

Cpp代码 收藏代码
void Merge(RecType *R,int low,int m,int high)
{//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]
int i=low,j=m+1,p=0; //置初始值
RecType *R1; //R1是局部向量
R1=(RecType *)malloc((high-low+1)*sizeof(RecType));
if(!R1)return; //申请空间失败
while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上
R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];
while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中
R1[p++]=R[i++];
while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中
R1[p++]=R[j++];
for(p=0,i=low;i<=high;p++,i++)
R[i]=R1[p];//归并完成后将结果复制回R[low..high]
}

void MergeSort(RecType R[],int low,int high)
{//用分治法对R[low..high]进行二路归并排序
int mid;
if(low<high){//区间长度大于1
mid=(low+high)/2;//分解
MergeSort(R,low,mid);//递归地对R[low..mid]排序
MergeSort(R,mid+1,high); //递归地对R[mid+1..high]排序
Merge(R,low,mid,high);//组合，将两个有序区归并为一个有序区
}
}