插入排序：直接插入排序，折半插入排序，希尔排序
交换排序：冒泡排序，快速排序
选择排序：简单选择排序，堆排序
归并排序
基数排序
#include <stdio.h> #include <stdlib.h> void InsertSort(int A[],int n){ int B[7]; int i,j; for(int i=1;i<=n;i++){ B[i]=A[i]; }//生成一个新的数组保持原数组不变 for(i=2;i<=n;i++){ if(B[i]<B[i-1]){ B[0]=B[i]; for(j=i-1;B[0]<B[j];--j){ B[j+1]=B[j]; } B[j+1]=B[0]; } } printf("直接插入排序后的数组:"); for(int i=1;i<=n;i++){ printf("%d ",B[i]); } printf("\n"); }//直接插入排序 void BInsertSort(int A[],int n){ int low,high,mid; int i,j; int B[7]; for(int i=1;i<=n;i++){ B[i]=A[i]; } for(i=2;i<=n;i++){ B[0]=B[i]; low=1; high=i-1; while(low<=high){ mid=(low+high)/2; if(B[mid]>B[0]){ high=mid-1; } else{low=mid+1;} } for(j=i-1;j>=high+1;j--){ B[j+1]=B[j]; } B[high+1]=B[0]; } printf("折半插入排序后的数组:"); for(int i=1;i<=n;i++){ printf("%d ",B[i]); } printf("\n"); }//折半插入排序 void ShellSort(int A[],int n){ int B[7]; int i,j; for(int i=1;i<=n;i++){ B[i]=A[i]; } int dk=n/2;//记录前后位置的增量 while(dk>=1){ for(i=dk+1;i<=n;i++){ if(B[i]<B[i-dk]){ B[0]=B[i]; for(j=i-dk;j>0&&B[0]<B[j];j=j-dk){ B[j+dk]=B[j]; } B[j+dk]=B[0]; } } dk=dk/2; } printf("希尔排序后的数组:"); for(int i=1;i<=n;i++){ printf("%d ",B[i]); } printf("\n"); }//希尔排序 void BubbleSort(int A[],int n){ int B[7]; for(int i=1;i<=n;i++){ B[i]=A[i]; } for(int i=1;i<n-1;i++){ for(int j=n;j>i;j--){ if(B[j]<B[j-1]){ B[0]=B[j-1]; B[j-1]=B[j]; B[j]=B[0]; } } } printf("冒泡排序后的数组:"); for(int i=1;i<=n;i++){ printf("%d ",B[i]); } printf("\n"); }//冒泡排序 int Partition(int B[],int low,int high){ int piovt=B[low]; while(low<high){ while(low<high&&B[high]>=piovt){ high--; } B[low]=B[high];//找到比枢轴值小的，将其放在枢轴值的左边 while(low<high&&B[low]<=piovt){ low++; } B[high]=B[low];//找到比枢轴值大的，将其放在数值值的右边 } B[low]=piovt;//枢轴值最终确定的位置 return low; }//快速排序划分算法 void QuickSort(int B[],int low,int high){ if(low<high){ int pivotpos=Partition(B,low,high);//将数组划分为两部分的指针 QuickSort(B,low,pivotpos-1); QuickSort(B,pivotpos+1,high); } }//快速排序 void Qsort(int A[],int n){ int low=0,high=n-1; int B[6]; for(int i=1;i<=n;i++){ B[i-1]=A[i]; } QuickSort(B,low,high); printf("快速排序后的数组:"); for(int i=0;i<n;i++){ printf("%d ",B[i]); } printf("\n"); }//选择排序总体算法 void SelectSort(int B[],int n){ int min;//记录最小值的位置 int temp; for(int i=0;i<n-1;i++){ min=i; for(int j=i+1;j<n;j++){ if(B[j]<B[min]){ min=j; } } if(i!=min){ temp=B[i]; B[i]=B[min]; B[min]=temp; } } }//简单选择排序 void Ssort(int A[],int n){ int B[6]; for(int i=1;i<=n;i++){ B[i-1]=A[i]; } SelectSort(B,n); printf("简单选择排序后的数组:"); for(int i=0;i<n;i++){ printf("%d ",B[i]); } printf("\n"); }//简单选择排序总体算法 void AdjustDown(int B[],int k,int n){ B[0]=B[k]; for(int i=2*k;i<=n;i=i*2){ if(i<n&&B[i]<B[i+1]){ i++; } if(B[0]>=B[i]){break;} else{ B[k]=B[i]; k=i; } } B[k]=B[0]; }//将元素进行向下调整 void BuildMaxHeap(int B[],int n){ for(int i=n/2;i>0;i--){ AdjustDown(B,i,n);//反复调整堆，直至堆满足大根堆 } }//建立大根堆 void HeapSort(int A[],int n){ int B[7]; int temp; for(int i=1;i<=n;i++){ B[i]=A[i]; } BuildMaxHeap(B,n); for(int i=n;i>1;i--){ temp=B[i]; B[i]=B[1]; B[1]=temp;//堆顶和堆底元素互换 AdjustDown(B,1,i-1);//把剩下i-1个元素整理成堆 } printf("堆选择排序后的数组:"); for(int i=1;i<=n;i++){ printf("%d ",B[i]); } printf("\n"); }//堆排序 void Merge(int B[],int low,int mid,int high){ int T[7];//归并排序辅助数组 for(int k=low;k<=high;k++){ T[k]=B[k]; } int i=low; int j=mid+1; int k=i; while(i<=mid&&j<=high){ if(T[i]<=T[j]){B[k]=T[i++];} else {B[k]=T[j++];}//比较左右两端中元素，将最小者复制到B中 k++; } while(i<=mid){B[k++]=T[i++];}//若左边的元素未复制完 while(j<=high){B[k++]=T[j++];}//若右边的元素未复制完 }//将一个表的左右两端（各自有序），合成一个新的表 void MergeSort(int B[],int low,int high){ if(low<high){ int mid=(low+high)/2; MergeSort(B,low,mid); MergeSort(B,mid+1,high); Merge(B,low,mid,high); } } void MSort(int A[],int n){ int B[6]; int low=0; int high=n-1; for(int i=1;i<=n;i++){ B[i-1]=A[i]; } MergeSort(B,low,high); printf("归并排序后的数组:"); for(int i=0;i<n;i++){ printf("%d ",B[i]); } printf("\n"); } void main(){ int n=6; int A[7]={-1,4,5,1,2,6,3};//0号元素一般不放关键字,这里以-1代替 printf("当前数组:"); for(int i=1;i<=n;i++){ printf("%d ",A[i]); } printf("\n"); InsertSort(A,n); BInsertSort(A,n); ShellSort(A,n); BubbleSort(A,n); Qsort(A,n); Ssort(A,n); HeapSort(A,n); MSort(A,n); }转载于:https://www.cnblogs.com/Yshun/p/11545185.html
