王道C语言C++版排序算法总结
2021/11/22 22:11:27
本文主要是介绍王道C语言C++版排序算法总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- 直接插入排序
直接插入排序
//直接插入排序
#include <stdio.h> #include<stdlib.h>//malloc #include <stdbool.h> //直接插入排序 void InsertSort(int a[],int n){ int i,j; for(i=2;i<=n;i++){ if(a[i]<a[i-1]){ a[0]=a[i]; for(j=i-1;a[0]<a[j];j--) { a[j+1]=a[j]; } a[j+1]=a[0]; } } } int main(){ int a[11],i,key,k; //定义数组及变量为基木整甩 printf("请输入10个数据:\n"); for (i =1;i<=10;i++) scanf("%d",&a[i]); //接收从键盘输入的10个数据到数组a中 printf("原始顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将未排序前的顺序输出 InsertSort(a,10);//调用直接插入函数 printf("\n 插入数据排序后顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将排序后的数组输出 printf("\n"); }
- 折半插入排序
折半插入排序
//折半插入排序
#include <stdio.h> #include<stdlib.h>//malloc #include <stdbool.h> //折半插入排序 void InsertSortByHalf(int A[],int n) { int i,j,low,high,mid; for(i=2;i<=n;i++){ A[0]=A[i]; low=1;high=i-1; while(low<=high){ mid =(low+high)/2; if(A[mid]>A[0]){ high=mid-1; } else low=mid+1; } for(j=i-1;j>=high+1;j--) { A[j+1]=A[j]; } A[high+1]=A[0]; } } int main(){ int a[11],i,key,k; printf("请输入10个数据:\n"); for (i =1;i<=10;i++) scanf("%d",&a[i]); printf("原始顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将未排序前的顺序输出 InsertSortByHalf(a,10);//调用折半查找函数 InsertSortByHalf printf("\n 插入数据排序后顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将排序后的数组输出 printf("\n"); }
- 希尔排序
希尔排序
//希尔排序
#include <stdio.h> #include<stdlib.h>//malloc #include <stdbool.h> void ShellSort(int A[],int n){ int dk,i,j; for(dk=n/2;dk>=1;dk=dk/2){ for(i=dk+1;i<=n;i++){ if(A[i]<A[i-dk]){ A[0]=A[i]; for(j=i-dk;j>0&&A[0]<A[j];j-=dk){ A[j+dk]=A[j]; } A[j+dk]=A[0]; } } } } int main(){ int a[11],i,key,k; printf("请输入10个数据:\n"); for (i =1;i<=10;i++) scanf("%d",&a[i]); printf("原始顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将未排序前的顺序输出 ShellSort(a,10); //调用希尔排序ShellSort printf("\n 插入数据排序后顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将排序后的数组输出 printf("\n"); }
- 冒泡排序
冒泡排序
//冒泡排序
#include <stdio.h> #include<stdlib.h>//malloc #include <stdbool.h> //从左边向右冒泡 void BubbleSort (int a[],int n){ int i,j,temp; for( i=0;i<n-1;i++){ for(j=0;j<n-1-i;j++){ if(a[j]>a[j+1]){ temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } } //从右边向左边冒泡 void BubbleSort2(int a[],int n){ int i,j,temp; for(i=0;i<n-1;i++){ bool flag =false; for(j=n-1;j>i;j--){ if(a[j-1]>a[j]){ temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; flag = true; } } if(flag==false){ return; } } } int main(){ //测试冒泡 int A[]={3,1,4,5,2}; int n=sizeof(A)/sizeof(int); BubbleSort(A,n); BubbleSort2(A,n); for(int i=0;i<n;i++){ printf("%d",A[i]); } }
- 快速排序
快速排序
//快速排序
#include <stdio.h> #include<stdlib.h>//malloc #include <stdbool.h> int Partition (int A[],int low,int high){ int pivot=A[low]; while(low<high){ while(low<high&&A[high]>=pivot){ --high; } A[low]=A[high]; while(low<high&&A[low]<=pivot){ ++low; } A[high]=A[low]; } A[low]=pivot; return low; } void QuickSort(int A[],int low,int high){ if(low<high){ int pivotpos=Partition(A,low,high); QuickSort(A,low,pivotpos-1); QuickSort(A,pivotpos+1,high); } } 两种main int main(){ //测试选择 int A[]={3,1,4,5,2}; int n=sizeof(A)/sizeof(int); QuickSort(A,0,4); for(int i=0;i<n;i++){ printf("%d",A[i]); } } int main(){ int a[11],i,key,k; printf("请输入10个数据:\n"); for (i =1;i<=10;i++) scanf("%d",&a[i]); printf("原始顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将未排序前的顺序输出 QuickSort(a,1,10); printf("\n 插入数据排序后顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将排序后的数组输出 printf("\n"); }
- 简单选择排序
简单选择排序
//简单选择排序
#include <stdio.h> #include<stdlib.h>//malloc #include <stdbool.h> //简单选择排序 void SelectSort(int A[],int n){ int i,j,min,temp; for(i=0;i<n-1;i++){ min=i; for(j=i+1;j<n;j++) {if(A[j]<A[min]) min=j;} if(min!=j){ temp=A[i]; A[i]=A[min]; A[min]=temp; } } } int main(){ //测试选择 int A[]={3,1,4,5,2}; int n=sizeof(A)/sizeof(int); SelectSort(A,n); for(int i=0;i<n;i++){ printf("%d",A[i]); } }
8.堆排序
堆排序
//堆排序
#include <stdio.h> #include<stdlib.h>//malloc #include <stdbool.h> void AdjustDown(int A[],int k,int len){ A[0]=A[k]; for(int i=2*k;i<=len;i*=2){ if(i<len&&A[i]<A[i+1]){ i++; } if(A[0]>=A[i]) {break;} else{ A[k]=A[i]; k=i; } } A[k]=A[0]; } void BuildMaxHeap(int A[],int len){ for(int i=len/2;i>0;i--){ AdjustDown(A,i,len); } } void HeapSort(int A[],int len){ BuildMaxHeap(A,len); for(int i=len;i>1;i--){ //空出第一个位置来做交换 int temp=A[i]; A[i]=A[1]; A[1]=temp; AdjustDown(A,1,i-1); } } int main(){ int a[11],i,key,k; printf("请输入10个数据:\n"); for (i =1;i<=10;i++) scanf("%d",&a[i]); printf("原始顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将未排序前的顺序输出 HeapSort(a,10); printf("\n 插入数据排序后顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将排序后的数组输出 printf("\n"); }
9.归并排序
归并排序
//归并排序
//int a[10] 和 int *a = malloc(10 * sizeof(int)) 的效果是一样的。 //都是在内存中申请10个连续的、每个大小为sizeof(int)的内存 int B[]; //int *B=(int *)malloc((n+1)* sizeof(int)); void Merge(int A[],int low,int mid,int high){ int i,j,k; //int n=sizeof(A)/sizeof(int); //int B[n]; for( k=low;k<=high;k++){ B[k]=A[k]; } for( i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){ if(B[i]<=B[j]) A[k]=B[i++]; else A[k]=B[j++]; } while(i<=mid) A[k++]=B[i++]; while(j<=high) A[k++]=B[j++]; } void MergeSort(int A[],int low,int high){ if(low<high){ int mid=(low+high)/2; MergeSort(A,low,mid); MergeSort(A,mid+1,high); Merge(A,low,mid,high); } } int main(){ int a[11],i,key,k; printf("请输入10个数据:\n"); for (i =1;i<=10;i++) scanf("%d",&a[i]); printf("原始顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将未排序前的顺序输出 MergeSort(a,1,10);//调用归并排序MergeSort printf("\n 插入数据排序后顺序:\n"); for(i=1;i<11;i++) printf("%5d",a[i]); //将排序后的数组输出 printf("\n"); }
这篇关于王道C语言C++版排序算法总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升