排序题目1
2021/6/4 18:51:52
本文主要是介绍排序题目1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <stdio.h> #include <stdlib.h> typedef enum{RED,WHITE,BLUE} color; //交换函数 void Swap(color &a,color &b){ color temp; temp=a; a=b; b=temp; } //ShellSort(基本思想:将数组用不同的步长划分为不同的子表,对子表内部进行相关的排序,使得子表间有序,最后设置步长为1,进行一次直接插入排序) void ShellSort(int A[],int n){ int i,j,dk; //步长变化 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[j]>A[0];j-=dk) A[j+dk]=A[j]; A[j+dk]=A[0]; } } } } //ShellSort void ShellSort1(int A[],int n){ int i,j,dk; //步长变化 for(dk=n/2;dk>=1;dk=dk/2){ //遍历子表 for(i=dk+1;i<=n;i+=dk){ if(A[i]>A[i-dk]){ A[0]=A[i]; //后移元素 for(j=i-dk;j>0 && A[j]>A[0];j-=dk){ A[j+dk]=A[j]; } A[j+dk]=A[0]; } i++; } } } //BubbleSort(基本思路:将每个元素相邻位置比较,小的元素上升) void BubbleSort(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; } } //这趟没有比较直接,说明有序,直接return if(flag==false) return; } } void Print(int A[],int n){ for(int i=0;i<n;i++){ printf("%d\t",A[i]); } printf("\n"); } //QuickSort(基本思想:找到一个中枢元素作为分界点,将小于中枢元素的数值放在左边,大于中枢元素的数值放在右边) int Partition(int A[],int low,int high){ //设置中枢元素 int pivots=A[low]; //小于中枢元素的元素放在A[low]位置 while(low<high){ while(low<high && A[high]>=pivots) high--; A[low]=A[high]; while(low<high && A[low]<=pivots) low++; A[high]=A[low]; } A[low]=pivots; return low; } void QuickSort(int A[],int low,int high){ if(low<high){ int pivotspaos=Partition(A,low,high); QuickSort(A,low,pivotspaos-1); QuickSort(A,pivotspaos+1,high); } } //双向起泡(基本思路:分别从头部和尾部开始遍历,尾部为最大数值,头部为最小数值) void DoubleBubbleSort(int A[],int n){ int i,j,temp,low=0,high=n-1; bool flag=true; while(flag && low<high){ //设置标记 flag=false; //从前往后遍历 for(i=low;i<high;i++){ if(A[i]>A[i+1]){ temp=A[i]; A[i]=A[i+1]; A[i+1]=temp; flag=true; } } //让high--,表示有一个元素不需要比较了 high--; for(j=high;j>low;j--){ if(A[j-1]>A[j]){ temp=A[j-1]; A[j-1]=A[j]; A[j]=temp; flag=true; } } //low++ low++; } } //将数组中奇数放在偶数之前(基本思想:利用快速排序的思想,双指针遍历,从后面找奇数,从前面开始找偶数,然后分别交换) void Move(int A[],int n){ int i=0,j=n-1,temp; //当i<j while(i<j){ //前面开始找偶数 while(i<j && A[i]%2!=0) i++; //后面开始找奇数 while(i<j && A[j]%2==0) j--; if(i<j){ temp=A[i]; A[i]=A[j]; A[j]=temp; } i++; j--; } } //查找元素(利用快速排序和递归实现快速查找一个指定下标的元素) int kth_elem(int A[],int low,int high,int k){ //第一部分:快速排序 int pivots=A[low]; int low_temp=low,high_temp=high; while(low<high){ while(low<high && A[high]>=pivots) high--; A[low]=A[high]; while(low<high && A[low]<=pivots) low++; A[high]=A[low]; } A[low]=pivots; //第二部分:递归快排,找到对应的元素 if(k==low) return A[low]; else if(k<low) return kth_elem(A,low_temp,low-1,k); else return kth_elem(A,low+1,high_temp,k); } //荷兰国旗问题 void Flag_Arrange(color a[],int n){ int i=0,j=0,k=n-1; while(j<k){ //判断是什么颜色 switch (a[j]) { case RED:Swap(a[j],a[i]);i++;j++;break; case WHITE:j++;break; case BLUE:Swap(a[j],a[k]);k--; } } } int main() { int A[]={3,2,34,1,23,4,1}; Print(A,7); //QuickSort(A,0,6); //BubbleSort(A,7); //DoubleBubbleSort(A,7); //Move(A,7); printf("%d\n",kth_elem(A,0,6,34)); Print(A,7); return 0; }
这篇关于排序题目1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)