9种排序算法实现

#include<stdio.h> #include<stdlib.h> #include<math.h> void swap(int a[],int idx_i,int idx_j){ if(idx_i==idx_j) return; int t=a[idx_i];a[idx_i]=a[idx_j];a[idx_j]=t; } //选择 void SelectSort(int a[],int n){ for(int i=0;i<n-1;i++){ int k=i; for(int j=i+1;j<n;j++){ if(a[k]>a[j]){ k=j; } } swap(a,i,k); } } //冒泡 void BubbleSort(int a[],int n){ for(int i=0;i<n-1;i++){ for(int j=0;j<n-i-1;j++){ if(a[j]>a[j+1]){ swap(a,j,j+1); } } } } //插入 void InsertSort(int a[],int n){ for(int i=1;i<n;i++){ int k=a[i]; int j=i-1; for(;j>=0&&a[j]>k;j--){ a[j+1]=a[j]; } a[j+1]=k; } } //希尔排序,使用Hibbard增量序列 满分 void ShellSort(int a[],int n){ int k=log(n)/log(2); for(int D=pow(2,k)-1;D>0;D=pow(2,--k)-1){//希尔增量序列 for(int i=D;i<n;i++){//内层必须要用插入排序 int t=a[i]; int j=i-D; for(;j>=0&&a[j]>t;j-=D){ a[j+D]=a[j]; } a[j+D]=t; } } } //归并排序,使用两个有序序列的合并 void merge(int a[],int left,int right,int end,int temp[]){ int i=left,j=right+1; int idx=left; while(i<=right&&j<=end){ if(a[i]>a[j]){ temp[idx++]=a[j++]; }else{ temp[idx++]=a[i++]; } } while(i<=right){ temp[idx++]=a[i++]; } while(j<=end){ temp[idx++]=a[j++]; } for(int i=left;i<=end;i++){ a[i]=temp[i]; } } //归并排序递归实现 满分 void MergeSort1(int a[],int left,int right,int temp[]){ if(left==right) return; MergeSort1(a,left,(left+right)/2,temp); MergeSort1(a,(left+right)/2+1,right,temp); merge(a,left,(left+right)/2,right,temp); } //归并排序非递归实现 满分 void MergeSort2(int a[],int n,int temp[]){ for(int i=n,d=1;i>1;i=(i+1)/2,d*=2){ for(int j=0;j<n;j+=2*d){ if(j+d-1<n-1){ merge(a,j,j+d-1,j+2*d-1<n-1?j+2*d-1:n-1,temp); } } } } void MergeSort(int a[],int n){ int *temp=(int*)malloc(sizeof(int)*n); MergeSort2(a,n,temp); free(temp); } //堆排序 从小到大排序构建最大堆，并把首元素挪到最后，不断调整 //建立堆的线性算法：从第一个有孩子的节点开始往前 //后面的测试点均超时 int FindMax(int a[],int i,int n){ int idx=i; if(2*i+1<n&&a[i]<a[2*i+1]){ idx=2*i+1; } if(2*i+2<n&&a[idx]<a[2*i+2]){ idx=2*i+2; } return idx; } void BuildMaxHeap(int a[],int n){ int i=(n-2)/2; for(;i>=0;i--){ int idx=i; int temp=a[i]; int pos; while((pos=FindMax(a,idx,n))!=idx){ a[idx]=a[pos]; idx=pos; a[idx]=temp; } } } void HeapSort(int a[],int n){ while(n>1){ BuildMaxHeap(a,n); swap(a,0,n-1); n--; } } //快排 实现的细节主要是枢轴元素的选择，以及元素和枢轴相等时是否需要停顿 //满分 //找枢轴元素 int FindPivot(int a[],int left,int right){ int mid=(left+right)/2; //这里不用两数之差乘积小于0去判断是因为乘积之后的数字可能溢出 if((a[mid]-a[left])<=0&&(a[mid]-a[right])>=0||(a[mid]-a[left])>=0&&(a[mid]-a[right])<=0) return mid; if((a[left]-a[mid])<=0&&(a[left]-a[right])>=0||(a[left]-a[mid])>=0&&(a[left]-a[right])<=0) return left; if((a[right]-a[mid])<=0&&(a[right]-a[left])>=0||(a[right]-a[mid])>=0&&(a[right]-a[left])<=0) return right; } void quick_sort(int a[],int left,int right){ if(left>=right) return; int idx=FindPivot(a,left,right); int pivot=a[idx]; swap(a,idx,right); int i=left,j=right-1; while(1){ while(i<=right-1&&a[i]<pivot){i++;} while(j>=left&&a[j]>pivot){j--;} if(i<j){ swap(a,i,j); i++; j--; }else{ break; } } swap(a,i,right); quick_sort(a,left,i-1); quick_sort(a,i+1,right); } void QuickSort(int a[],int n){ quick_sort(a,0,n-1); } //表排序 只是其它排序方法的拓展，当元素本身很大时移动的代价比较大，考虑交换元素地址 //如果还需要物理排序，则将环路逐一调整 //这里用插入排序构建表排序 //满分 struct Node{ int data; int table; }; void TableSort(int a[],int n){ struct Node* Tabel=(struct Node*)malloc(sizeof(struct Node)*n); for(int i=0;i<n;i++){ Tabel[i].data=a[i]; Tabel[i].table=i; } //使用插入排序 for(int i=1;i<n;i++){ int j=i-1; for(;j>=0&&Tabel[Tabel[j].table].data>Tabel[i].data;j--){ Tabel[j+1].table=Tabel[j].table; } Tabel[j+1].table=i; } for(int i=0;i<n;i++){ a[i]=Tabel[Tabel[i].table].data; } //对Table进行物理排序，此步由实际情况决定 for(int i=0;i<n;i++){ if(Tabel[i].table!=i){ int t=Tabel[i].data; int j=i; int temp; for(;Tabel[j].table!=i;j=temp){ Tabel[j].data=Tabel[Tabel[j].table].data; temp=Tabel[j].table; Tabel[j].table=j; } Tabel[j].data=t; Tabel[j].table=j; } } // for(int i=0;i<n;i++) // printf("%d ",Tabel[i].data); // printf("\n"); free(Tabel); } //基数排序 基数排序来源于桶排序，基于多关键字的思想 //利用了数字或字符串每位上的取值有限 //需要排序的数字是非负数 typedef struct node{ int data; struct node *next; }Node; typedef struct bucket{ Node *head[10]; Node *end[10]; }Bucket; Bucket* BuildBucket(){ Bucket *bucket=(Bucket*)malloc(sizeof(Bucket)); for(int i=0;i<10;i++){ bucket->head[i]=(Node*)malloc(sizeof(Node)); bucket->head[i]->next=NULL; bucket->end[i]=bucket->head[i]; } return bucket; } void DestroyBucket(Bucket *bucket){ for(int i=0;i<10;i++){ Node*p,*q; q=bucket->head[i]; p=q->next; q->next=NULL; while(p){ q=p->next; free(p); p=q; } free(bucket->head[i]); } free(bucket); } void AddBucket(Bucket *bucket,int num,int base){ Node*node=(Node*)malloc(sizeof(Node)); node->data=num; node->next=NULL; int t=(int)(num/pow(10,base))%10; bucket->end[t]->next=node; bucket->end[t]=node; } //最大数的位数 int FindMaxLength(int a[],int n,int *delta){ int maxval,minval; maxval=minval=a[0]; for(int i=1;i<n;i++){ if(a[i]>maxval){ maxval=a[i]; } if(a[i]<minval){ minval=a[i]; } } if(minval<0){ *delta=-minval; maxval+=*delta; for(int i=0;i<n;i++){ a[i]+=*delta; } } int length=0; for(int i=maxval;i>0;length++,i/=10); return length; } //按照低位优先排序 这里每次都用新桶，如果旧桶原地操作会很麻烦 //第二组测试数据有问题，其余均对 void BaseSort(int a[],int n){ int delta=0; int length=FindMaxLength(a,n,&delta); Bucket *bucket=BuildBucket(); //放入桶中,相当于进行第一次基数排序 for(int i=0;i<n;i++){ AddBucket(bucket,a[i],0); } // for(int i=0;i<10;i++){ // Node*p=bucket->head[i]->next; // while(p){ // printf("p->data:%d ",p->data); // p=p->next; // } // printf("\n"); // } for(int base=1;base<length;base++){ Bucket *temp=BuildBucket(); for(int j=0;j<10;j++){ Node*p=bucket->head[j]->next; while(p){ AddBucket(temp,p->data,base); p=p->next; } } DestroyBucket(bucket); bucket=temp; // for(int i=0;i<10;i++){ // Node*p=bucket->head[i]->next; // while(p){ // printf("p->data:%d ",p->data); // p=p->next; // } // printf("\n"); // } } //将桶中所有元素装回数组 int idx=0; for(int i=0;i<10;i++){ Node*p=bucket->head[i]->next; while(p){ a[idx++]=p->data-delta; p=p->next; } } //销毁桶 DestroyBucket(bucket); } int main(){ int n=12; scanf("%d",&n); int *a=(int*)malloc(sizeof(int)*n); for(int i=0;i<n;i++){ scanf("%d",a+i); } //排序 BaseSort(a,n); for(int i=0;i<n-1;i++){ printf("%d ",a[i]); } printf("%d",a[n-1]); //销毁数组 free(a); return 0; }