CC排序算法之冒泡排序和选择法排序
文章首发于CSDN,博主HanSmileLiao「链接」原文链接:https://blog.csdn.net/NebulaChien/article/details/120436663
转眼大二了,突然感觉比大一还要迷茫(也可能是因为数模竞赛,评优都没有搞好,明年暑假的智能车也一点没有头绪23333),计二报的是Python(虽然没什么卵用,但是学校要我们搞非精准扶贫),在用多了自带的函数之后,突然想起去年让我相爱相杀的排序算法,emmm专业课刚好遇到了数据结构里面的各种排序,就想着过了一年再系统地整理一下,也是因为自己对于C太生疏了吧,虽然我不知道C学了个什么玩意儿,真正让自己有点感触的还是OOP,毕竟万物皆对象,行为皆方法。打算做一个系列,再回头看看自己曾经学过的东西,数电模电,线性代数高数等等。
打算以后多在CSDN、Github、头条丢一些大佬压根看不上的垃圾,说不定哪天大佬就出来教我做事了呢:(
本人超级菜,求求大佬们出来教我做事啊
打算做一个系列,专门整理一些算法,先从排序开始一、两种排序算法的基本思想
1、冒泡法(起泡排序):
用到for循环,round1的两次for循环分别确定List[0]和List[1],现在我们就得到了两个相邻的元素,按照期望的序列决定是较小的数上浮还是较大的数上浮,一直到List[length_List](以升序为例),此时相当于找到了序列0-length_List的最大值;round2的两次for循环分别确定List[1]和List[2],以此类推一直到List[length_List-1],此时找到了序列0-length_List-1的最大值…依次往后直到确定List[0]与List[1]大小关系,此时程序结束 ,如下所示:for(int j=len-1;j>i;j--) { if(name_List[j] # include # include
2.生成随机数
参考大佬的文章后用了动态生成随机数以及动态分配数组长度的方法: int *List=new int[length_List]; srand((unsigned int)time(NULL)); for(int index=0;index # include # include using namespace std; /* Bubble sort: Basic idea:Compare adjacent elements in turn,smaller go up(upwards sort) and bigger go down;or bigger go up(downwards sort) Each turn we compare position and position->next,if position and it"s next meet the requests,we don"t need to do it again So the algorithm can be optimized:Because each "Bubble" actually is switch the value We could set a BOOL value as a key,each compare initialize the key to false,and after comparing turn it to true After comparing check key value,if it"s value is false interrupt the program */ /* BubbleSort1 is upwards sort BubbleSort2 is downwards sort */ void Exchange(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } //Swap() is a place that is easy to ignore. Exchange values are exchanged addresses, or exchange their respective references (alias) void BubbleSort1(int name_List[],int length_List) { int m=0,n=0; int len=length_List; bool Flag; //Threshold(key), if a certain time has been sorted, there is no need to continue to traverse down for(int i=0;ii;j--) { if(name_List[j]i;j--) { if(name_List[j]>name_List[j-1]) { n++; Exchange(&name_List[j],&name_List[j-1]); Flag=true; } } if(!Flag) break; } cout<<"Sort the list with the format of down is :"<=10):"; cin>>length_List; if(length_List<10) { Flag=0; cout<<"Exit by fault input"<>Flag; } } return 0; }
选择法排序: /* Upwards First round,find minimum value of List[length_list],put it on first location index Second round,find minimum value of List[length_list],put it on first location index+1 ... Downwards First round,find maximum value of List[length_list],put it on first location index Second round,find maximum value of List[length_list],put it on first location index+1 ... */ # include # include # include using namespace std; void Exchange(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } /* SelectionSort1() is upwards SelectionSort2() is downwards */ void SelectionSort1(int name_List[],int length_List) { int len=length_List; int Index_min; int m=0,n=0; for(int i=0;iname_List[j]) { Index_min=j; } } if(Index_min!=i) { Exchange(&name_List[Index_min],&name_List[i]); } /* Suppose the sequence is :| 5 2 8 6 4 7 3 In first round the minimum is 2,i=0,put it on location 0,and the new sequence is :2 | 5 8 6 4 7 3 In second round the minimum is 3,i=1,put it on location 1,and the new sequence is 2 3 | 5 8 6 4 7 .... */ } cout<<"The upwards sort is :"<=10):"; cin>>length_List; if(length_List<10) { Flag=0; cout<<"Exit by fault input"<>Flag; } } return 0; }
以上就是第一篇关于最基础的两种排序算法的分享,大家还有什么想了解的可以打在评论区,我会逐一解答,以后也会多多分享这些资源。
要走的路还很长啊,共勉!
祝大家周末快乐![比心]