发布于:2018年7月17日 15:41
😑
关于排序最先学的就是后一个与前一个比较并交换的冒泡排序,记录下标的选择排序,这里就不多介绍了,只把它的代码贴出来,重点说一下快速排序。
一、冒泡,选择:
//冒泡 for(i=0;i<8;i++) for(j=0;j<8-i-1;j++) { if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } //选择 for(i=0;i<8;i++) for(j=i;j<8-1;j++) { if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } }
二、快速排序
(用c++的同学如果实在看不懂就不要看了,直接看 三。用纯c的话,你必须看懂)
既然叫快速排序,说明他是速度最快的。
快速排序首先选一个数组中的值作为参照,比他小的放在他的左边,大的放在右边。
然后对左半部分,同样选一个参照,比他小的放在他的左边,大的放在右边。
若此时左半部分的左边只有一个数,就对左半部分的右边做同样的操作。否则再对其(左半部分的左边)左边做同样操作。
左半部分完成后,对右半部分做和左半部分一样的操作。
具体过程如下:
一般选a[0]作为参照,假设数组为a[5],从小到大排
key=a[o];n=0;m=4;
① 然后把a[m]和key比较,如果a[m]<key就a[n]=a[m],
如果a[m]>=key,就m--,一直循环到a[m]<key或者m<n时结束循环。
(当然,若到循环结束也没找到一个a[m]大于key就说明数组是已经排好序的了。)
② 接下来把a[n]和key比较,如果a[n]>key就a[m]=a[n],如果a[n]<=key,就n++,一直循环到a[n]>key或者m<n时结束循环。
③ 接着把key放到a[n],此时a[n]左边一定比他小,右边比他大。
④ 然后对a[n]左边重复1,2,3步。
⑤ 然后对a[n]右边重复1,2,3步。
实现时,4,5步用一个递归就行。
代码如下:
void quick(int*a,int i,int j) { int n,m,key; key=a[i]; n=i; m=j; while(n<m) { while(a[m]>key&&m>n) {m--;} a[n]=a[m]; while(a[n]<key&&n<m) {n++;} a[m]=a[n]; } a[n]=key; if(n>i) quick(a,i,n-1); if(n<j) quick(a,n+1,j); } int main() { int a[5]={7,6,10,5,67}; quick(a,0,5-1); return 0; }
三、sort()函数
sort()函数在c++的头文件algorithm中
用法是sort(begin,end,排序规则)
sort()函数是用快速法排序,在不写排序规则的情况下,默认从小到大排序
代码如下:
#include<stdio.h> #include<iostream> #include<algorithm> usingnamespace std; intmain() { int a[5]={7,6,10,5,67}; sort(a,a+5); for(int i=0;i<5;i++) printf("%d ",a[i]); return 0; }
那么,从大到小该如何做呢?
#include<stdio.h> #include<iostream> #include<algorithm> usingnamespace std; boolcompare(int a,int b) {returna>b;} intmain() { int a[5]={7,6,10,5,67}; sort(a,a+5,compare); for(int i=0;i<5;i++) printf("%d ",a[i]); return 0; }
我们还可以用头文件functional里提供的函数
#include<stdio.h> #include<iostream> #include<algorithm> #include<functional> usingnamespace std; intmain() { int a[5]={7,6,10,5,67}; sort(a,a+5,greater<int>());//从大到小 sort(a,a+5,less<int>());//从小到大 return 0; }
发表评论 (对文章评论)